Twoim celem jest napisanie idealnego gracza do gry Wythoff's Nim .

Zasady Nim Wythoffa

Wythoff's Nim to deterministyczna gra dla dwóch graczy, rozgrywana dwoma stosami identycznych znaczników. Gracze naprzemiennie tury, w których wykonują jedną z następujących czynności:

1. Usuń jeden lub więcej znaczników z pierwszego stosu
2. Usuń jeden lub więcej żetonów z drugiego stosu
3. Usuń taką samą liczbę liczników (jeden lub więcej), zarówno z pierwszego stosu, jak i drugiego stosu.

Oczywiście stosy nie mogą być ujemne, ale mogą osiągnąć wartość 0. Niezależnie od tego, który gracz usunie ostatni licznik, wygrywa grę.

Dla bardziej nastawionych geometrycznie, oto ekwiwalent gry, w którą możesz grać za pomocą tego apletu . Jedna królowa zaczyna na jakimś kwadracie nieskończonej szachownicy, której róg znajduje się w lewym dolnym rogu. Gracze naprzemiennie poruszają królową, która porusza się jak królowa szachów, ale ogranicza się do trzech kierunków:

1. Na dół
2. Lewo
3. Po przekątnej w dół i w lewo

Kto przenosi królową do rogu, wygrywa.

Przypisując współrzędne królowej (z rogiem (0,0)) do rozmiarów odpowiednich stosów, łatwo jest zauważyć, że obie gry są takie same.

Idealna gra

(Możesz to pominąć, jeśli znasz pojęcia doskonałej gry i zwycięskich ruchów.)

Ponieważ Wythoff's Nim jest skończoną i deterministyczną grą, ma idealną grę . Idealny gracz to strategia, która zawsze wygrywa z teoretycznie wygranej pozycji, co oznacza pozycję, w której istnieje strategia gwarantująca zwycięstwo.

Aby być zwycięską strategią, wystarczy przejść, aby zawsze przejść do teoretycznej zwycięskiej pozycji dla gracza, który właśnie się poruszył, a tym samym gracza, który nie pójdzie dalej. Pierwsze z tych zwycięskich pozycji (zwane również pozycjami zimnymi ) to (0,0), (1,2), (2,1), (3,5), (5,3). Zobacz artykuł w Wikipedii, aby uzyskać wyjaśnienie algorytmu znajdowania zwycięskiej strategii dla Wythoffa Nima, a także formułę generowania zwycięskich pozycji.

Wymagania programu

Napisz program lub funkcję przyjmuje pozycję jako dane wejściowe i wyprowadza zwycięski ruch w postaci pozycji po tym ruchu. Wygrywa najmniej bajtów.

Jeśli nie ma żadnego wygrywającego ruchu, tj. Pozycja jest teoretyczną stratą, Twój program powinien to zaznaczyć i przepadnąć.

Twój program musi zostać uruchomiony w rozsądnym czasie. Zatem wykładnicze rekurencyjne wyszukiwanie drzewa gry nie wystarczy. Jeśli chcesz wstępnie obliczyć i zaprogramować strategię, nie ma sprawy.

Wejście

Para (i,j)liczb nieujemnych reprezentujących rozmiary stosów, każda najwyżej 99. Mogą to być dwie liczby, krotka, lista lub dowolny inny kontener.

Wynik

Wydrukuj lub wyślij pozycję po swoim ruchu, ponownie jako dwie liczby lub ich pojemnik. To musi być legalne przejście do zwycięskiej pozycji. Jeśli jest wiele takich ruchów, każdy jest w porządku, ale tylko jeden.

Jeśli nie ma zwycięskiego ruchu, musisz to wskazać w wynikach. Wszelkie wyjścia jak False, None, 0, lub (-1,-1)zrobi, tak długo jak nie jest to sytuacja prawna, i jest taka sama dla każdego wejścia przegranej.

Przykład działa

f(5,0)   = (0,0)
f(2,2)   = (1,2)   # Or (2,1) or (0,0) 
f(1,2)   = False
f(13,9)  = (13,8)  # Or (10,6)
f(10,6)  = False
f(5,10)  = (5,3)
f(25,30) = (8,13)    

Haskell, 167 165 znaków

c p=o p:c(o p:p)
o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0
(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]
f x@(a,b)|a<b=f(b,a)|x?c[]!!0==x=(0,-1)|1>0=x?c[]!!0

Algorytm jest nieefektywny, ale nadal działa w ciągu sekundy (choć nie w interaktywnej konsoli) dla danych wejściowych <100.

Wyjaśnienie:

c p=o p:c(o p:p)

Lista pozycji zimnych z zestawem poprzednich pozycji zimnych to jedna pozycja zimna, a następnie lista pozycji zimnych z tą pozycją i poprzednimi (Nieskuteczność: ta pozycja jest generowana dwukrotnie)

o p=[(a,b)|a<-[0..],b<-[0..a],(a,b)?p==[]]!!0

Jedna zimna pozycja to pierwsza para, tak że nie ma dostępnych zimnych pozycji z tej pary (Nieefektywność: zamiast tego powinniśmy szukać z poprzedniej pary)

(a,b)?p=[y|y@(c,d)<-p,c==a||c==b||d==b||a+d==b+c]

Pozycje osiągalne z pary są takie, że ich pierwsze elementy pasują, ich drugie elementy pasują, ich różnice pasują lub mniejsza sterty przed usunięciem jest większą stertą po usunięciu.

f x@(a,b)|a<b=f(b,a)
         |x?c[]!!0==x=(0,-1)
         |1>0=x?c[]!!0

(główna metoda) Jeśli stosy są w niewłaściwej kolejności, zamień je. W przeciwnym razie, jeśli pierwszą zimną pozycją osiągalną z pozycji jest sama pozycja, wskaż awarię (najlepiej Maybe (Int,Int)zamiast tego powróci ). W przeciwnym razie zwróć tę zimną pozycję (Brak wydajności: wspomniana para jest dwukrotnie sprawdzana. Gorzej, lista zimnych pozycji jest generowana dwukrotnie)

GolfScript ( 63 57 bajtów)

{\]zip{~-}%0|$(!*,1=}+1,4*{..,,^[(.@,2/+.2$]+}38*2/?0]0=`

Oczekuje danych wejściowych z wejścia standardowego w formularzu [a b]i pozostawia dane wyjściowe ze standardowego wejścia w tej formie lub 0jeśli jest to pozycja tracąca. Demo online

Przegląd

,4*{..,,^[(.@,2/+.2$]+}38*2/

oblicza listę zimnych pozycji (w tym wersję odwróconą [b a]dla każdej zimnej pozycji [a b]) przy użyciu właściwości sekwencji Beatty .

Następnie ?wyszukuje pierwszą zimną pozycję spełniającą blok utworzony przez

{\]zip{~-}%0|$(!*,1=}+

które zasadniczo sprawdza, czy pozycja jest osiągalny ze stanowiska wejściowego poprzez obliczenie różnicy wektorowej, a następnie sprawdzenie, czy to albo [0 x], [x 0]albo [x x]dla niektórych x > 0. IMO, że test jest najmądrzejszym bitem: 0|$zmusza dowolną tablicę w jednym z tych formatów do formy [0 x]podczas mapowania[0 0] do [0], [a b]gdzie ani anie bjest 0do tablicy trzech elementów, a [-x 0]lub [-x -x]na [-x 0]. Następnie (!*,1=sprawdza, które mamy [0 x].

Wreszcie 0]0=`jest to przypadek zastępczy i formatowanie danych wyjściowych.

Pyt 57 58 61 62

K1.618Jm,s*dKs*d*KKU39M<smf|}TJ}_TJm,-Ghb-Hebt^,0hk2U99 1

Wypróbuj online.

Całkiem podobne do innych odpowiedzi, ale ta strona Wikipedii nie dała wiele do zrobienia;) Magiczna liczba 39to liczba zimnych pozycji z wartościami < 99.

Definiuje funkcję g, którą możesz wywołaćg 30 25 . W []przypadku niepowodzenia zwraca się w przypadku niepowodzenia [(13,8)].

Wyjaśnienie

K1.618                            : K=phi (close enough for first 39 values)
      Jm,s*dKs*d*KKU39            : J=cold positions with the form (small,big)
M<s                              1: Define g(G,H) to return this slice: [:1] of the list below 
   mf|}TJ}_TJ                     : map(filter: T or reversed(T) in J, where T is each member of..
             m,-Ghb-Hebt^,0hk2    : [(G H) - (0 x+1),(x+1 0) and (x+1 x+1)]
                              U99 : for each x from 0 - 98

JavaScript ES6 - 280 bajtów

Zminimalizowane

r=x=>~~(x*1.618);g=(y,x)=>y(x)?g(y,x+1):x;s=A=>A?[A[1],A[0]]:A;f=(a,b)=>j([a,b])||j([a,b],1);j=(A,F)=>l(A,F)||s(l(s(A),F));l=(A,F)=>([a,b]=A,c=(F&&a+b>=r(b)&&(e=g(x=>a+b-2*x-r(b-x),0))?[a-e,b-e]:(e=g(x=>r(a+x)-2*a-x,0))+a<b?[a,a+e]:(e=r(b)-b)<a?[e,b]:0),c&&r(c[1]-c[0])==c[0]?c:0)

Rozszerzony

r = x => ~~(x*1.618);
g = (y,x) => y(x) ? g(y,x+1) : x;
s = A =>A ? [A[1],A[0]] : A;
f = (a,b) => j([a,b]) || j([a,b],1);
j = (A,F) => l(A,F) || s(l(s(A),F));
l = (A,F) => (
    [a,b] = A,
    c = (
        F && a+b >= r(b) && (e = g( x => a+b - 2*x - r(b - x), 0 )) ? [a-e,b-e] :
        (e = g( x => r(a+x) - 2*a - x, 0)) + a < b ? [a,a+e] :
        (e = r(b) - b) < a ? [e,b] : 0
    ),
    c && r(c[1] - c[0]) == c[0] ? c : 0
);

Ładny i szybki algorytm. Działa w O (n), ale działałby w stałym czasie, gdyby nie pętla zapisująca bajty. Pętla została zaimplementowana jako inkrementator inkrementalny, dlatego skrypt ostatecznie zawiedzie z błędem rekurencji dla nw setkach lub tysiącach. Wykorzystuje tę samą właściwość sekwencji Beatty, o której wspomina pan Taylor, ale zamiast obliczać sekwencję, po prostu zbliża się do właściwego terminu (-ów).

Działa poprawnie na wszystkich wejściach testowych i wielu innych poza tym, co testowałem.

Funkcja do wywołania to f. Zwraca tablicę po sukcesie i 0po poddaniu się.

Perl 5-109 (z 2 flagami)

#!perl -pl
for$a(@v=0..99){for$b(@v){$c=$a;$d=$b;${$:="$a $b"}||
map{$$_||=$:for++$c.$".++$d,"$a $d","$c $b"}@v}}$_=$$_

Stosowanie:

$ perl wyt.pl <<<'3 5'

$ perl wyt.pl <<<'4 5'
1 2

Po prostu oblicza rozwiązanie dla każdego możliwego wejścia, a następnie wykonuje tylko jedno wyszukiwanie.