Tworzenie najkrótszy program, aby sprawdzić, kto wygrał w n d Tic Tac Toe gry.
Twój program powinien działać, gdy n
(szerokość) i d
(numer wymiaru) znajdują się w następujących zakresach:
n∈[3,6]∩ℕ ie a number from this list: 3,4,5,6
d∈[2,5]∩ℕ ie a number from this list: 2,3,4,5
n = 3; d = 2
(3 2 tj. 3 na 3):
[][][]
[][][]
[][][]
n = 3; d = 3
(3 3 tj. 3 na 3 na 3):
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
[][][]
n = 6; d = 2
(6 2 tj. 6 na 6):
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
I tak dalej.
Zwycięstwo (jeśli grałeś wystarczająco dużo wielowymiarowych kółek i krzyżyk, to tak samo.)
Aby wygrać, jeden gracz musi mieć wszystkie sąsiadujące pola wzdłuż linii. Oznacza to, że gracz musi mieć n
ruchy na linii, aby zostać zwycięzcą.
Sąsiadujący:
- każda płytka jest punktem; na przykład (0,0,0,0,0) to punkt w
d=5
- sąsiadujące płytki są płytkami, więc oba są punktami na tej samej jednostce d-cube. Innymi słowy, odległość Czebyszewa między płytkami wynosi 1.
- innymi słowy, jeśli punkt
p
przylega do punktuq
, wówczas każda współrzędna wp
odpowiedniej współrzędnej inq
różni się od niej nie więcej niż o jeden. Dodatkowo przynajmniej para współrzędnych różni się dokładnie o jeden.
Linie:
- Linie są definiowane przez wektory i kafelki. Linia to każda płytka dotknięta równaniem:
p0 + t
<
some vector with the same number of coordinates as p0>
Wejście :
Dane wejściowe będą na STDIN. Pierwszy wiersz danych wejściowych będzie składał się z dwóch liczb n
oraz d
w formie n,d
.
Następnie pojawi się linia składająca się ze współrzędnych określających wykonane ruchy. Współrzędne są wymienione w następującej postaci: 1,1;2,2;3,3
. Lewy górny róg jest punktem początkowym (0,0 dla 2D). W ogólnym przypadku ta lista będzie wyglądać tak, jakby 1,2,...,1,4;4,0,...,6,0;...
pierwsza liczba reprezentowała lewą prawą stronę, drugą górę-dół-ność, trzecią do trzeciego wymiaru itp. Zauważ, że pierwsza współrzędna to X
pierwsza kolej, druga jest O
pierwsza kolej, ....
Po wprowadzeniu pojawi się nowy wiersz.
Wyjście :
Wyjście będzie do STDOUT. Wystarczy wskazać, kto wygrał, jeśli ktoś wygrał, lub jeśli jest to remis. Jeśli nie jest to remis ani wygrana, nie wypisuj niczego.
Dodatkowo wskaż, czy doszło do zderzenia ruchu, to znaczy, czy w tym samym miejscu występują co najmniej dwa ruchy.
Jeśli przed zakończeniem wejścia było zwycięstwo / losowanie, Twój program może zrobić, co chce.
Przypadki testowe (ktoś chce coś jeszcze zasugerować?):
Wejście:
4,3
0,0,0;1,1,1;1,0,1;2,0,2;0,0,1;2,0,0;2,0,1;3,0,2;3,0,1
Przykładowe dane wyjściowe:
X wins
Kolejny możliwy wynik (wymaga wyjaśnienia):
1
źródło
n
aby wygrać, trzeba wykonać ruchy na linii. (Przepraszam, że nie opublikowałem tych uwag w piaskownicy, ale nawet nie miałem czasu, aby je tam zobaczyć, ponieważ zostały opublikowane tak szybko po piaskownicy.)Odpowiedzi:
Python,
745578 znakówWprowadziłem kilka zmian i trochę się zmniejszyłem. Zauważ, że powrót True oznacza, że x wygrał, False oznacza y wygrał, i oznacza, że wykonano nieprawidłowy ruch.
źródło
import *
naimport*
. Użyj1
dla Prawda i0
dla Fałsz (usuńT
iF
).return -1
może byćreturn-1
(sprawdź usuwanie spacji). Zmień nazwę swoich metod na metody jednoznakowe. Sprawdź wskazówki dotyczące dalszych optymalizacji.if l<>q:
zamiastif not l==q:
.Brak odpowiedzi - Java
Byłem ciekawy, jak wiele różnych sposobów można wygrać dla danego n, d, więc napisałem ten kod, aby wymienić je wszystkie.
Testowałem go ręcznie na n, d = 2..3,2..3 i wydaje się, że działa… po tym liczba możliwych sposobów na wygraną rośnie szybko, jak pokazano poniżej:
Po wygenerowaniu wszystkich zwycięskich zestawów, mogłem rozszerzyć program, aby sprawdzić dane wejściowe względem zwycięskich zestawów, ale oczywiście ta metoda nigdy nie wygrałaby golfa. Byłem zadowolony, mogąc się tutaj zatrzymać - tyle że wyglądało na to, że mogę znaleźć rozwiązanie w formie zamkniętej dla wielu sposobów na wygraną w funkcji ni d… Jest to liczba sposobów na wygraną = 0,5 ((n + 2) ^ d - n ^ d).
źródło
C ++ 794
849znakówDane wyjściowe to: „X” (X wygrywa), „O” (O wygrywa) lub „!” (próba nielegalnego ruchu).
To po prostu mapuje punkty do tablicy liniowej i sprawdza wszystkie możliwe podzbiory wielkości n, najpierw pod kątem stałej wartości w X lub O, a następnie pod kątem bycia w linii. Aby sprawdzić, czy są w linii, współrzędne punktów w każdym podzbiorze są sprawdzane pojedynczo; każdy z nich musi albo wzrastać od 0 do n-1, zmniejszać się od n-1 do 0, lub być stały. Punkty są naturalnie uporządkowane w szyku liniowym, więc warto nazwać współrzędną rosnącą lub malejącą dla danego zestawu punktów.
Dziękujemy Howardowi za wskazanie poważnego błędu w pierwszej wersji.
W ramach solidarności z Quincunx muszę zaznaczyć, że byłoby parodią, gdyby wygrała odpowiedź w C ++
źródło
X wins
aniO wins
. Jest całkowicie uzasadnione, aby generować1
lub2
(lub inną odmianę), o ile wyjaśnisz w odpowiedzi, co oznaczają. Jak powiedziałem (podkreślenie dodane): „ wskaż, kto wygrał”.