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:

1. Gracz 1 umieszcza X w dowolnym miejscu na planszy (9 opcji)
2. Gracz 2 umieszcza O w dowolnym miejscu na planszy (8 wyborów)
3. Gracz 1 umieszcza X w dowolnym miejscu na planszy (7 opcji)
4. Gracz 2 może zostać zmuszony (1 wybór), jeśli nie, umieszcza O w dowolnym miejscu (6 opcji)
5. Ruch gracza 1 jest wymuszony (1 wybór)
6. 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)
7. 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 kprzedziału od 0 do 1727 i musisz zwrócić kgrę 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. 0123845Lub [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.

JavaScript (ES6), 266 308 317 334 341

Funkcja zwracająca ciąg znaków. Edytuj Znaleziono rozwiązanie arytmetyczne dla funkcji M (w końcu!)

F=(n,x=[],M=(a,b,t=-a-b)=>(a-b)%3?a<3&b<3?3+t:a>5&b>5?21+t:12+t:9+t+a%3*3)=>
[for(a of z='012345678')for(b of z)for(c of z)for(d of z) 
a-b&&c-a&&c-b&&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c)&&(
f=M(c,e=M(b,d)),g=M(a,e),g<f?[f,g]=[g,f]:0,r=a+b+c+d+e,x.push(r+f+g,r+g+f))]
&&x[n]

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

F=(n,x=[],
  M=(a,b,t=-a-b)=>(a-b)%3? 
     a<3&b<3?
       3+t // first row
       :a>5&b>5?
          21+t // last row
          :12+t // middle row and diags
     :9+t+a%3*3 // columns
  )=>
  [for(a of z='012345678') // enumerate the first 4 moves
     for(b of z)
       for(c of z)
         for(d of z) 
           a-b&&c-a&&c-b // avoid duplicates
           &&(b-(y=M(a,c))?d==y:d-a&&d-b&&d-c) // and check if d must block a-c or it's free
           &&(
             e=M(b,d), // forced to block b-d
             f=M(c,e),g=M(a,e),g<f?[f,g]=[g,f]:0, // f and g could be in the wrong order
             r=a+b+c+d+e, // start building a return string
             x.push(r+f+g,r+g+f) // store all values in x
  )]&&x[n] // return value at requested position

Oktawa, 467 369 363 309 297 znaków

297:

global t=0*(1:9)m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48 a;
function g(s,p)global a t m;
if nnz(s)<8&&any((t==1)*m>2)a=[a;s];return;end;q=t==3-p;
(r=sort(~q.*(1:9)*m(:,find([3 1]*([q;t==p]*m)==6)')))||(r=find(~t));
for i=r t(i)=p;g([s i+47],3-p);t(i)=0;end;end;g('',1);f=@(n)a(n+1,:);

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ę:

$ octave
octave:1>> source script.m
octave:2>> f(634)
ans = 3270148

Nieskluczony kod wygląda następująco:

 global t=0*(1:9);
 global m=dec2bin([15;113;897;1170;1316;1608;2370;2216;2580])-48;
 global allgames;
 allgames=[];

 function r=canbewon(by)
  global t m
  q=[t==by;t==(3-by)]*m;
  g=(find([3 1]*q==6))';
  r=sort((~(t==by).*(1:9)) * m(:,g));
 end

 function games_starting_with(s)
 global allgames t;
 if 7==numel(s) && any((t==1)*m==3) # it's 7th move and first player won
  allgames=[allgames;s];
  return;
 end;
 poss=(find(~t));                  # for now all free slots are possible
 player=1+mod(numel(s),2);
 moves = canbewon(3-player);
 if numel(moves) poss=moves; end;  # ... no, we must block the other player
 for i=poss
  t(i)=player;
  games_starting_with([s char(i+47)]);
  t(i)=0;
 end
end

games_starting_with('');
f=@(n)(allgames(n+1,:));