Hay un juego llamado Get Home que se juega en un tablero de ajedrez. En este juego hay una sola pieza que ambos jugadores mueven por turnos. Hay algunas reglas sobre cómo se puede mover la pieza. En un turno, un jugador debe hacer uno de los siguientes movimientos para obtener un n positivo .
n espacios arriba
n espacios a la izquierda
n espacios hacia arriba y hacia la izquierda (una diagonal)
El jugador que mueve la pieza a la esquina superior izquierda del tablero gana el juego.
Ahora definiremos el concepto de un cuadrado perdedor. En este video (de donde saqué la idea), una casilla perdedora se define como una casilla en la que cualquier jugador que comience su turno se verá obligado a hacer un movimiento que permita a su oponente forzar una victoria. El ejemplo más simple de un cuadrado perdedor sería el cuadrado en (1,2). Una pieza en (1,2) puede moverse a cualquiera de los siguientes lugares.
Todos los cuales tienen un camino directo a la victoria para el próximo jugador.
También se deduce que cualquier casilla que tenga un camino de un movimiento hacia una casilla perdedora le permite al jugador que comienza en esa casilla forzar una victoria. Esto significa que cualquier casilla que no esté a un movimiento de distancia de una casilla perdedora es también una casilla perdedora.
Esto nos lleva a esta definición bastante clara de un cuadrado perdedor:
Una casilla perdedora es una casilla desde la cual ningún movimiento puede llegar a otra casilla perdedora y (0,0) es una casilla perdedora.
Tarea
Dadas las coordenadas de un cuadrado en un tablero de ajedrez de tamaño arbitrario, determine si es un cuadrado perdedor. Emite dos valores, uno para perder cuadrados y otro para otros.
Este es el código de golf, por lo que las respuestas se puntuarán en bytes, siendo mejores menos bytes.
Casos de prueba
Aquí están todas las casillas perdedoras en un tablero de ajedrez regular de 8 por 8 (marcado con 0).
0 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 0
1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
Aquí hay una imagen de un tablero de 100 por 100 con cuadrados perdidos marcados en negro (cada cuadrado es de 2 píxeles por 2 píxeles).
fuente
10, 7
un cuadrado perdedor? Es10, 8
? ¿Qué hay de15, 11
?Respuestas:
Python 3 ,
112504642 bytes-4 bytes gracias a Jonathan Allan !
-2 bytes gracias a xnor !
Pruébalo en línea!
Basado en la fórmula para posiciones frías en el juego de Wythoff y haciendo algunas modificaciones para producir una fórmula explícita. Explicación entrante una vez que realmente termine una metodología adecuada para la derivación de la fórmula.
fuente
0<=x
ax>0
y guardar un byte o dos?<=
o>=
para incluir la posición0, 0
.lambda r,c:int(abs(r-c)*(5**.5+1)**2/4)==max(r,c)
/2//1
se ve igual que//2
.Jalea , 8 bytes
Pruébalo en línea! , o vea la parte superior izquierda de 60 por 60 como una cuadrícula .
¿Cómo?
Una posición fría en el juego de Wythoff es una posición perdedora. Las coordenadas
[n,m]
dan una posición fría cuandon = floor(kφ) = floor(mφ) - m
om = floor(kφφ) = ceil(nφ) = n + k
por algún número natural,k
y la proporción áurea,φ
. El primero se cumple cuandon
es menor quem
; este último cuandom
es menor quen
(ambos manteniéndose en0,0
).k
es por lo tanto la diferencia absoluta entren
ym
y sifloor(abs(n-m)φ)=min(n,m)
se cumple la condición.fuente
JavaScript (ES6), 64 bytes
Ahora veo que esta no es la mejor técnica, pero tuve que inventarla yo mismo porque perdí Internet poco después de cargar esta página. (Hubiera publicado hace un tiempo si no fuera por estos problemas de Internet ...)
En un mundo perfecto, la precisión de flotación no sería un problema y podría ahorrar 9 bytes:
Se podrían guardar 6 bytes más si JS admitiera el encadenamiento de comparación de Python:
fuente
Pyth, 39 bytes
Escribí esto con una función con nombre (ew), y era extremadamente vago con el golf. Planeando jugar un buen número de bytes más tarde esta noche
Pruébelo en línea, con mis propias pruebas generadas, destinadas a alternar verdadero / falso
Explicación:
Las diagonales de la matriz de solución tienen un cuadrado perdedor según la secuencia de números repetidos en OEIS A005206 . De
L
principio a fin;
es bastante fácil definir la notación polacay(b)=b-y(y(b-1))
.El resto de la explicación sigue
fuente
Lote, 204 bytes
Devoluciones a través del código de salida. Explicación: Dado que Batch solo tiene aritmética de enteros, tuve que idear una solución puramente aritmética. Excluyendo la
0,0
entrada, los pares de coordenadas cuadradas perdedoras siguen la siguiente regla: si el siguiente11
número binario libre es par, entonces suma de lo3,2
contrario suma2,1
. Una prueba para un11
número binario libre es si no hay acarreos cuando se multiplica por tres, en otras palabras, eso(i*2)+i==(i*2)^i
. Aquí están los primeros pocos11
números binarios libres y sus coordenadas:Misteriosamente, esta regla es suficiente para hacer que las secuencias sean complementarias. Luego queda calcular la secuencia hasta que alcanza la coordenada más grande, en cuyo punto podemos determinar si el cuadrado está perdiendo.
fuente