To wyzwanie dotyczy gry Kółko i krzyżyk, ale rozgrywane jest na torusie.
Jak grać
Aby stworzyć niezbędną planszę, zaczynasz od zwykłej planszy Kółko i krzyżyk. Najpierw złóż go do cylindra, łącząc lewą i prawą krawędź. Następnie złóż go w torus, łącząc górną i dolną krawędź. Oto prosta wizualizacja takiej planszy z kilkoma zagranymi ruchami (umiejętności Malowania chorych!).
Zasady gry w kółko i krzyżyk na torusie są takie same jak w przypadku zwykłego kółka i krzyżyka. Każdy gracz umieszcza naprzemiennie X i OS. Pierwszy z 3 takimi samymi symbolami w rzędzie, kolumnie lub w przekątnej wygrywa.
Ponieważ torus jest dość trudny do wizualizacji, po prostu rzutujemy tablicę z powrotem na papier. Teraz możemy grać w tę grę jako zwykły Kółko i krzyżyk. Jedyną różnicą jest to, że możesz wygrać również za pomocą 3 takich samych symboli w złamanej przekątnej. Na przykład Gracz 1 (X) wygrywa następną planszę. Możesz to łatwo zobaczyć, zmieniając nieco widok torusa.
Jeśli jesteś zainteresowany, możesz zagrać w Kółko i krzyżyk na torusie w Torus Games . Istnieje wersja Windows, Mac i Android.
Optymalne gry
W tym wyzwaniu zainteresowane były optymalne gry. Optymalna gra to gra, w której obaj gracze grają w optymalną strategię. Na zwykłej planszy kółko i krzyżyk optymalne gry zawsze kończą się remisem. Fascynująco na planszy torusa zawsze wygrywa pierwszy gracz. W rzeczywistości gra na planszy torusa nigdy nie może zakończyć się remisem (także jeśli gracze nie grają optymalnie).
Optymalna strategia jest naprawdę łatwa:
- Jeśli możesz wygrać, umieszczając swój symbol, zrób to.
- W przeciwnym razie, jeśli twój przeciwnik ma dwa symbole w jednym rzędzie / kolumnie / agonal przekątnej, spróbuj go zablokować. W przeciwnym razie rób, co chcesz.
- W przeciwnym razie rób, co chcesz.
Każda optymalna gra składa się z dokładnie 7 ruchów, które można opisać w następujący sposób:
- Gracz 1 umieszcza X w dowolnym miejscu na planszy (9 opcji)
- Gracz 2 umieszcza O w dowolnym miejscu na planszy (8 wyborów)
- Gracz 1 umieszcza X w dowolnym miejscu na planszy (7 opcji)
- Gracz 2 może zostać zmuszony (1 wybór), jeśli nie, umieszcza O w dowolnym miejscu (6 opcji)
- Ruch gracza 1 jest wymuszony (1 wybór)
- Gracz 2 zostaje złapany w rozwidlenie (Gracz 1 może wygrać na dwa różne sposoby), więc Gracz 2 musi zablokować Gracza 1 w jeden sposób (2 opcje)
- Gracz 1 umieszcza swój ostatni ruch i wygrywa (1 wybór)
Na naszej planszy jest 9 * 8 * 1 * 6 * 1 * 2 * 1 + 9 * 8 * 6 * 1 * 1 * 2 * 1 = 1728 różnych optymalnych gier. Tutaj możesz zobaczyć jedną typową optymalną grę:
Jeśli oznaczymy każdą komórkę planszy cyframi 0-8
, możemy opisać tę grę cyframi 3518207
. Najpierw X to miejsca w komórce 3 (środkowy rząd, lewa kolumna), niż O w komórce 5 (środkowy rząd, prawa kolumna), a następnie X w komórce 1 (górny rząd, środkowa kolumna), ...
Za pomocą tej notacji cyfrowej automatycznie wygenerowaliśmy zamówienie. Teraz możemy posortować wszystkie 1728 optymalnych gier i otrzymamy listę:
Game 0000: 0123845
Game 0001: 0123854
Game 0002: 0124735
Game 0003: 0124753
Game 0004: 0125634
...
Game 0674: 3518207
...
Game 1000: 5167423
Game 1001: 5167432
Game 1002: 5168304
...
Game 1726: 8765034
Game 1727: 8765043
Wyzwanie
Ta lista jest częścią twojej pracy. Otrzymasz jeden numer z k
przedziału od 0 do 1727 i musisz zwrócić k
grę w notacji cyfrowej posortowanej listy.
Napisz funkcję lub program, który otrzyma liczbę k
(liczbę całkowitą) obliczającą odpowiednią grę. Możesz odczytać dane wejściowe za pomocą STDIN, argumentu wiersza poleceń, argumentu zachęty lub funkcji i wydrukować wynik (7 cyfr) w czytelnym formacie (np. 0123845
Lub [0, 1, 2, 3, 8, 4, 5]
) lub zwrócić za pomocą łańcucha (format czytelny dla człowieka) lub liczby całkowitej (zawierającej wszystkie cyfry w bazie 10) lub w dowolnym formacie tablicy / listy.
Typ wyzwania to golf kodowy. Dlatego wygrywa najkrótszy kod.
źródło
Odpowiedzi:
JavaScript (ES6), 266
308 317 334 341Funkcja zwracająca ciąg znaków. Edytuj Znaleziono rozwiązanie arytmetyczne dla funkcji M (w końcu!)
Bardzo naiwny
, można go skracać na wiele sposobów. Po prostu wylicza wszystkie możliwe wartości prawne i zwraca to, co znajduje się w miejscu n. Funkcja M zwraca pozycję między dwiema komórkami, czyli ruch obowiązkowy, aby zablokować przeciwnego gracza.Bardziej czytelny
źródło
Oktawa,
467 369 363 309297 znaków297:
Jedyną istotną zmianą jest to, że nigdy nie sprawdzamy, czy aktualny gracz może wygrać, tylko sprawdzamy, czy przeciwnik może wygrać następną turę . Ponieważ jedyną turą, którą gracz 1 może wygrać, jest tura 7 , jest to jedyne miejsce, w którym algorytm stworzyłby grę, która nie jest optymalna, ale bardzo łatwo jest odfiltrować taką sytuację. Po prostu weryfikujemy każdą wygenerowaną grę, jeśli wygrywa ją gracz 1 - jeśli nie, ruch z kolei 7 był nieprawidłowy, więc nie dodajemy tej gry do optymalnego stołu do gry.
(Dokładnie połowa gier generowanych przez tę zasadę jest fałszywa, tj. W 7. turze gracz 1 ma zawsze dwie możliwości zablokowania gracza dwa, ale tylko jedna spowoduje, że wygra natychmiast).
Posługiwać się:
Nieskluczony kod wygląda następująco:
źródło