Recientemente obtuve un tablero de ajedrez irregular realmente extraño. Sus cuadrados están por todas partes y ni siquiera todos están conectados. Al menos todavía están distribuidos en una cuadrícula regular. Quiero adaptar las reglas del ajedrez para poder jugar en el tablero, pero para empezar, necesito una pieza que realmente pueda ir a cualquier parte del tablero, y parece que un saltador es mi mejor apuesta para eso.

Los saltadores son la generalización del ajedrez de hadas de los caballeros. Los saltadores están parametrizados por dos números enteros m y n y pueden moverse m cuadrados en una dirección y luego otros n cuadrados en cualquier dirección perpendicular. Para el caballero estándar, tenemos (m, n) = (2, 1) . Todo el movimiento se considera un solo salto, de modo que ninguno de los cuadrados en el camino hacia el objetivo debe estar vacío o incluso existir.

El reto

Te dan un "tablero de ajedrez" en forma de una lista de coordenadas enteras 2D positivas que representan los cuadrados que forman parte del tablero. Su tarea es encontrar un saltador que, dados suficientes movimientos, pueda alcanzar cualquier casilla en el tablero.

Veamos algunos ejemplos. El tablero de ajedrez estándar utiliza una cuadrícula regular de cuadrados de 8x8 (tenga en cuenta que no distinguimos entre cuadrados blancos y negros para este desafío):

########
########
########
########
########
########
########
########

El caballero estándar puede alcanzar todos esos, por (2, 1)lo que sería una salida válida. Sin embargo, (1, 1)por ejemplo, no sería válido, ya que dicha pieza solo puede alcanzar la mitad de los cuadrados sin importar dónde comience. (1, 0)Por otro lado, también sería una salida válida, ya que todos los cuadrados están conectados ortogonalmente.

Ahora si tenemos un tablero irregular como:

#   #
 # # #
  # # #
 # #
    #

Entonces las posibles soluciones son (1, 1)y (3, 1). También podemos tener una placa con regiones completamente desconectadas como:

#### ####
#### ####
#### ####
#### ####

El caballero estándar (2, 1)aún puede alcanzar todos los cuadrados aquí, que de hecho es la única solución.

Y finalmente, ningún saltador puede alcanzar completamente el siguiente tablero simple:

#
 ##

Tenga en cuenta que el formato de entrada no será una representación ASCII, sino una lista de coordenadas. Por ejemplo, el segundo ejemplo anterior podría darse como:

[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]]

Reglas

Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).

Las coordenadas de entrada se pueden tomar en cualquier formato de lista conveniente (lista plana, lista de pares, lista de enteros complejos, cadena con separadores consistentes, etc.).

La salida debe ser los dos números enteros m y n que identifican la leaper si existe una solución (como dos enteros separados, una lista, una cadena con delimitador no numérico, etc.). Si no existe una solución, puede generar cualquier valor consistente que no pueda ser un saltador válido. Esto incluye el par de enteros (0, 0)en su formato normal, así como cualquier cosa que no sea un par de enteros no negativos.

Su programa necesita manejar cualquiera de los casos de prueba en un minuto . Esta es una restricción algo confusa, pero use el sentido común: si toma 2 minutos en su máquina, creo que podemos suponer que podría ejecutarse dentro de 1 en otra persona, pero si toma 20 es menos probable. No debería ser difícil resolver cada caso de prueba en cuestión de segundos, por lo que esta regla solo actúa para descartar la fuerza bruta ingenua.

Aplican reglas estándar de código de golf .

Casos de prueba

Cada caso de prueba es de la forma board => all valid leapers. Recuerde que solo necesita generar uno de esos. Si la lista de saltadores está vacía, asegúrese de devolver algo que no sea un saltador válido.

Examples above:
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]] => [[0, 1], [1, 2], [1, 4], [2, 3], [3, 4]]
[[1, 1], [5, 1], [2, 2], [4, 2], [6, 2], [3, 3], [5, 3], [7, 3], [2, 4], [4, 4], [5, 5]] => [[1, 1], [1, 3]]
[[1, 1], [2, 2], [3, 2]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => [[1, 2]]

Square boards:
[[1, 1], [1, 2], [2, 1], [2, 2]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]] => [[0, 1]]
[[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]] => [[0, 1], [1, 2]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [2, 3]]
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7]] => [[0, 1], [1, 2], [2, 3]]

Miscellaneous:
[[1, 1], [2, 1]] => [[0, 1]]
[[1, 1], [1, 2]] => [[0, 1]]
[[1, 1], [12, 35]] => [[11, 34]]
[[1, 1], [1, 2], [2, 1], [2, 2], [6, 1], [6, 2], [6, 3], [6, 4], [7, 1], [7, 2], [7, 3], [7, 4], [8, 1], [8, 2], [8, 3], [8, 4], [9, 1], [9, 2], [9, 3], [9, 4]] => []
[[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], [3, 5], [3, 6], [4, 1], [4, 2], [4, 5], [4, 6], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6]] => [[0, 1], [1, 2], [1, 4]]
[[2, 2], [2, 4], [2, 6], [2, 8], [4, 2], [4, 4], [4, 6], [4, 8], [6, 2], [6, 4], [6, 6], [6, 8], [8, 2], [8, 4], [8, 6], [8, 8]] => [[0, 2], [2, 4]]

Random boards:
[[1, 5], [1, 9], [2, 6], [2, 8], [2, 10], [2, 12], [3, 5], [3, 7], [3, 9], [3, 11], [3, 13], [4, 2], [4, 4], [4, 6], [4, 8], [4, 14], [5, 1], [5, 3], [5, 5], [5, 7], [6, 2], [6, 4], [7, 1], [8, 2]] => [[1, 1], [1, 3]]
[[1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 1], [2, 2], [2, 3], [2, 4], [2, 7], [3, 1], [3, 2], [3, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 3], [5, 4], [5, 6]] => [[0, 1], [1, 2]]
[[1, 8], [2, 6], [2, 10], [3, 3], [3, 4], [3, 8], [4, 1], [4, 11], [5, 3], [5, 9], [6, 12], [8, 11], [10, 10], [11, 12], [12, 6], [12, 8], [13, 6], [13, 8], [13, 10], [13, 11], [14, 5], [14, 7], [14, 8], [14, 13], [14, 14], [15, 7], [15, 9], [15, 11], [15, 12], [16, 6], [16, 7], [16, 9], [16, 13], [16, 14], [17, 10], [17, 12], [18, 8], [18, 12], [20, 9], [21, 11], [22, 13], [23, 10], [23, 11], [23, 15], [24, 12]] => [[1, 2]]
[[1, 17], [1, 21], [3, 11], [3, 15], [3, 19], [3, 23], [5, 13], [5, 21], [7, 11], [7, 15], [7, 19], [9, 1], [9, 13], [9, 17], [11, 3], [11, 7], [11, 15], [11, 19], [13, 5], [13, 9], [13, 13], [13, 17], [13, 21], [15, 11], [15, 15], [15, 19], [17, 13], [17, 17]] => [[2, 2], [2, 6], [2, 10]]
[[1, 3], [2, 4], [2, 5], [3, 6], [4, 1], [5, 3], [5, 6], [5, 7], [6, 12], [6, 14], [6, 21], [7, 9], [7, 19], [8, 9], [8, 15], [8, 17], [8, 18], [8, 24], [9, 12], [9, 19], [10, 12], [10, 14], [10, 17], [10, 21], [11, 22], [12, 15], [12, 17], [12, 24], [13, 16], [14, 20], [14, 21], [14, 26], [15, 13], [15, 19], [16, 18], [16, 23], [17, 16], [17, 24]] => [[2, 3]]
[[1, 11], [3, 13], [4, 10], [6, 14], [8, 12], [9, 9], [9, 15], [12, 8], [13, 5], [13, 19], [13, 21], [14, 8], [15, 1], [15, 17], [16, 4], [16, 14], [16, 18], [16, 20], [17, 21], [18, 2], [18, 16], [18, 18], [19, 9], [19, 13], [19, 15], [20, 12], [21, 1], [21, 17], [22, 4], [22, 10], [23, 7]] => [[1, 3]]
[[1, 39], [6, 37], [8, 32], [10, 27], [11, 31], [11, 35], [12, 22], [16, 21], [16, 29], [16, 33], [18, 34], [21, 3], [21, 9], [21, 19], [23, 8], [23, 14], [23, 22], [23, 24], [23, 36], [24, 6], [25, 13], [25, 17], [26, 1], [26, 11], [28, 6], [28, 20], [28, 26], [28, 30], [28, 34], [30, 11], [30, 15], [30, 21], [32, 6], [33, 28], [33, 32], [35, 13], [35, 23]] => [[2, 5]]

Como caso especial, tenga en cuenta que para una placa que consta de una sola celda, cualquier saltador funciona, pero su salida debe corresponder a un saltador real, por [0, 0]lo que no es una salida válida.

Pyth 41 35

hfqQu@+G+VM*s_BM*F_BMTGQ]hQ)maVhQdt

Sale por error si no hay saltadores válidos, dando la cadena vacía si se ignora STDERR.

Pruébelo aquí o ejecute un Test Suite

¡Guardado 6 bytes gracias a isaacg ! Básicamente solo encuentra todos los candidatos de saltador seleccionando cada saltador válido del primer mosaico al otro mosaico. Luego, para cada uno de estos, realiza las ocho configuraciones de [x, y]compensaciones que el saltador podría tomar. Luego encuentra todos los movimientos comenzando desde el primer mosaico que sigue después del movimiento, y descarta los que no están en la entrada. Sigue haciendo esto hasta que el resultado no cambie. Si esta lista final es la misma que la entrada, entonces el saltador era válido.

El tablero de ajedrez estándar tardó más cuando estaba probando, tardó aproximadamente 3 segundos en mi computadora no muy impresionante.