Tu objetivo es escribir un jugador perfecto para el juego de Wythoff's Nim .

Reglas de Nim de Wythoff

Wythoff's Nim es un juego determinista de dos jugadores que se juega con dos montones de fichas idénticas. Los jugadores alternan turnos, en los que hacen uno de estos:

1. Retire uno o más contadores de la primera pila
2. Eliminar uno o más contadores de la segunda pila
3. Retire un número igual de contadores (uno o más), tanto del primer montón como del segundo montón.

Por supuesto, las pilas no pueden ir negativas, pero pueden llegar a 0. El jugador que quite el último contador en general gana el juego.

Para los de mentalidad más geométrica, aquí hay una formulación equivalente del juego que puedes jugar en este applet . Una sola reina comienza en un cuadrado de un tablero de ajedrez de un cuarto de infinito cuya esquina está en la esquina inferior izquierda. Los jugadores alternan moviendo a la reina, que se mueve como una reina del ajedrez pero restringida a tres direcciones:

1. Abajo
2. Izquierda
3. Diagonalmente abajo y a la izquierda

El que mueve a la reina a la esquina gana.

Al asociar las coordenadas de la reina (con la esquina (0,0)) a los tamaños de las pilas respectivas, es fácil ver que ambos juegos son iguales.

Juego perfecto

(Puede omitir esto si está familiarizado con las nociones de juego perfecto y movimientos ganadores).

Dado que Nim de Wythoff es un juego finito y determinista, tiene una noción de juego perfecto . Un jugador perfecto es una estrategia que siempre ganará desde una posición teóricamente ganada, lo que significa una posición en la que existe una estrategia que garantiza una victoria.

Para ser una estrategia ganadora, es suficiente moverse para moverse siempre a una posición ganadora teórica para el jugador que acaba de moverse y, por lo tanto, el jugador no sigue. La primera de estas posiciones ganadoras (también llamadas posiciones frías ) son (0,0), (1,2), (2,1), (3,5), (5,3). Consulte el artículo de Wikipedia para obtener una explicación de un algoritmo para encontrar una estrategia ganadora para Nim de Wythoff, así como una fórmula para generar posiciones ganadoras.

Requisitos del programa

Escribir un programa o función toma una posición como entrada y genera un movimiento ganador en la forma de la posición después de ese movimiento. Pocos bytes ganan.

Si no existe un movimiento ganador, es decir, la posición es una pérdida teórica, su programa debe indicarlo y perderlo.

Su programa debe ejecutarse dentro de un período de tiempo razonable. Por lo tanto, una búsqueda de árbol de juego recursiva exponencial no será suficiente. Si desea calcular previamente y codificar una estrategia, está bien.

Entrada

Un par (i,j)de números no negativos que representan tamaños de pila, cada uno como máximo 99. Pueden ser dos números, una tupla, una lista o el contenedor que prefiera.

Salida

Imprima o imprima la posición después de su movimiento, nuevamente como dos números o un contenedor de los mismos. Esto debe ser un movimiento legal a una posición ganadora. Si hay múltiples movimientos de este tipo, cualquiera está bien, pero solo uno.

Si no hay movimiento ganador, debe indicarlo en la salida. Cualquier salida como False, None, 0, o (-1,-1)lo hará, siempre y cuando no sea una posición legal, y es el mismo para cada entrada perdedor.

Ejecuciones de ejemplo

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 caracteres

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

El algoritmo es ineficiente, pero aún se ejecuta en un segundo (aunque no en la consola interactiva) para entradas <100.

Explicación:

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

La lista de posiciones frías dado un conjunto de posiciones frías anteriores es una posición fría seguida de la lista de posiciones frías dada esta posición y las anteriores (Ineficiencia: esta posición se genera dos veces)

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

Una posición fría es el primer par, de modo que no hay posiciones frías accesibles desde ese par (ineficiencia: en su lugar, deberíamos buscar desde el par anterior)

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

Las posiciones accesibles desde un par son aquellas en las que sus primeros elementos coinciden, sus segundos elementos coinciden, sus diferencias coinciden o el montón más pequeño antes de la eliminación es el montón más grande después de la eliminación.

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

(método principal) Si los montones están en el orden incorrecto, cámbielos. De lo contrario, si la primera posición fría a la que se puede acceder desde una posición es la posición misma, indique el fallo (idealmente, uno volvería en su Maybe (Int,Int)lugar). De lo contrario, devuelva esa posición fría (Ineficiencia: dicho par se busca dos veces. Peor aún, la lista de posiciones frías se genera dos veces)

GolfScript ( 63 57 bytes)

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

Espera la entrada de stdin en el formulario [a b]y deja la salida en stdout en ese formulario o 0si es una posición perdedora. Demostración en línea

Visión general

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

calcula una lista de posiciones en frío (incluida la versión invertida [b a]para cada posición en frío [a b]) utilizando la propiedad de secuencia Beatty .

Luego ?busca la primera posición fría que satisface el bloque creado por

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

que básicamente comprueba que la posición es accesible desde la posición de entrada mediante el cálculo de la diferencia vectorial y luego verificar que se trata de ya sea [0 x], [x 0]o [x x]por alguna x > 0. En mi opinión, esa prueba es el bit más inteligente: 0|$obliga a cualquier matriz en uno de esos formatos a la forma [0 x]mientras se asigna [0 0]a [0], [a b]donde ni ani bes 0a una matriz de tres elementos, [-x 0]ni [-x -x]a [-x 0]. Luego (!*,1=comprueba que tenemos [0 x].

Finalmente 0]0=`hace el caso de reserva y el formato para la salida.

Pyth 57 58 61 62

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

Pruébalo en línea.

Bastante similar a otras respuestas, pero esa página de wikipedia no dio mucho más para continuar;) El número mágico 39es el número de posiciones frías con valores < 99.

Define una función a la gque puede llamar like g 30 25. Devoluciones []por fracaso, [(13,8)]por éxito.

Explicación

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 bytes

Minified

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)

Expandido

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
);

Algoritmo agradable y rápido. Se ejecuta en O (n), pero se ejecutaría en tiempo constante si no fuera por un ciclo de ahorro de bytes. El bucle se implementa como un incrementador recursivo, por lo tanto, el script eventualmente fallará con un error de recursión para n en cientos o miles. Utiliza la misma propiedad de secuencia de Beatty que menciona el Sr. Taylor, pero en lugar de calcular la secuencia, simplemente avanza al término o términos correctos.

Se ejecuta correctamente en todas las entradas de prueba y en muchas docenas además de las que probé.

La función a invocar es f. Devuelve una matriz en caso de éxito y una 0al rendirse.

Perl 5 - 109 (con 2 banderas)

#!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}}$_=$$_

Uso:

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

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

Simplemente calcula la solución para cada posible entrada y luego solo realiza una búsqueda.