¿Dónde puede estar el caballero en N movimientos?

21

Este es el hoyo 3 del Torneo de otoño de APL CodeGolf . Soy el autor original del problema allí y, por lo tanto, me permite volver a publicarlo aquí.


Dado:

  1. un número de turnos (indique si ningún movimiento es 0, de lo contrario asumiremos que se llama 1) y

  2. una lista de una o más posiciones iniciales (en cualquier forma, por ejemplo, 0 o 1 coordenadas indexadas o 64 números / caracteres consecutivos o A1 – H8 - indica cuál), en un tablero de ajedrez de 8 por 8,

devolver (en cualquier orden) la lista de posiciones únicas (en el mismo formato que la entrada) en las que pueden estar los caballeros después del número dado de turnos.

  • Cada caballero debe moverse con cada turno, pero no tiene que preocuparse de que múltiples caballeros ocupen el mismo cuadrado.

  • Un caballero solo puede moverse a las posiciones marcadas con X en relación con su posición actual, marcadas con ♞:
    donde un caballero puede moverse

Ejemplos (coordenadas indexadas 1)

1pasar de [[1,1]]: [[2,3],[3,2]]

2se mueve desde [[1,1]]: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]

1pasar de [[1,1],[5,7]]: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]

2se mueve desde [[1,1],[5,7]]: [[1,1],[1,3],[1,5],[1,7],[2,4],[2,6],[2,8],[3,1],[3,3],[3,5],[3,7],[4,2],[4,4],[4,6],[4,8],[5,1],[5,3],[5,5],[5,7],[6,4],[6,6],[6,8],[7,3],[7,7],[8,4],[8,6],[8,8]]

0se mueve desde [[3,4]]: [[3,4]]

Adán
fuente
¿Se pueden ingresar y generar espacios de ajedrez numerando 0-63 en lugar de [rango, archivo]?
Dave
@Dave Claro, ¿por qué no? Solo sea consistente con las E / S.
Adám
8
Juro que leí este HNQ como "Dónde se mueve el caballero en Ni"
Sidney
3
Juego de palabras: la notación para caballero es N.
Joshua
¿Podemos usar la indexación basada en 1 en la cantidad de pasos? Por ejemplo[[1,1]], 2 -> [[2,3],[3,2]]
Zgarb

Respuestas:

11

Wolfram Language (Mathematica) , 45 bytes

Como la otra solución es incorrecta (vea el comentario de Martin a continuación), decido publicar mi solución:

8~KnightTourGraph~8~AdjacencyList~#&~Nest~##&

Pruébalo en línea!

Notación de infijo definitiva ...

Toma 2 entradas, la primera es una lista de números dentro del rango que [1,64]describe las posiciones iniciales del caballero, la segunda es el número de pasos.

Esta solución se basa en la extrema comodidad de las funciones incorporadas de Mathematica:

  • AdjacencyListmay toma una lista de vértices en su lado derecho y devuelve una lista de vértices adyacentes a cualquiera de ellos, ya eliminados, duplicados y ordenados .
  • KnightTourGraphEs un incorporado. No es sorpresa
  • Nesttoma los argumentos en orden Nest[f, expr, n], que podemos salpicar ##sobre su lado derecho como Nest[f, ##].
  • Y, por último, Mathematica analiza a~b~c~d~ecomo (a~b~c)~d~e, por lo que no es necesario un corchete. Sin notación infija y aplanar ##, sería Nest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&.
usuario202729
fuente
1
No creo que haya nada malo en superar una solución existente.
Adám
1
¿Funciona esto con múltiples posiciones iniciales?
Adám
¡Asombroso! Ahora necesito descubrir cómo lees esto ...
Dave
Esto probablemente sería de 17 bytes en el hipotético lenguaje de golf Mthmca.
Michael Stern
7

JavaScript (ES7), 99 bytes

Formato de entrada / salida: índices cuadrados en [0 ... 63] .

f=(a,n)=>n--?f([...Array(64).keys()].filter(p=>!a.every(P=>(p%8-P%8)**2^((p>>3)-(P>>3))**2^5)),n):a

Casos de prueba

Este fragmento incluye dos funciones auxiliares para traducir desde y hacia el formato proporcionado por el OP.

¿Cómo?

Un movimiento de (x, y) a (X, Y) es un movimiento de caballero válido si tenemos:

  • | xX | = 1 y | aa | = 2 o
  • | xX | = 2 y | aa | = 1

Al cuadrar en lugar de usar valores absolutos, esto se puede expresar como:

  • (xX) ² = 1 y (yY) ² = 4 , o
  • (xX) ² = 4 y (yY) ² = 1

Como 1 y 4 son los únicos cuadrados perfectos que dan 5 cuando se hacen XOR juntos, tenemos un movimiento válido de caballero si:

(xX) ² XOR (yY) ² XOR 5 = 0

Aplicamos esta fórmula a cada cuadrado p = 8y + x en el tablero y a cada cuadrado de caballero P = 8Y + X para deducir los nuevos cuadrados posibles de objetivo de caballero, y repetimos este proceso de manera recursiva n veces.

Arnauld
fuente
5

Octava, 69 bytes

function a=f(a,n,b=~a)for k=1:n;a=b&imdilate(a,de2bi(")0#0)"-31));end

Demo en línea!

La entrada / salida es la configuración de la placa al inicio / final como una matriz binaria 8 * 8.

Explicación:

Para los npasos, repita la dilatación morfológica del tablero con la siguiente máscara:

01010
10001
00100
10001
01010
rahnema1
fuente
5

Retina , 147 102 bytes

.$
$*	
¶
 ¶
{s`((?<=N(....|.{11}|.{13})?.{7})|(?=.{8}(....|.{11}|.{13})?N))\S(?=.*	)
n
Ts`	Nn`_:N`.*¶	

Pruébalo en línea! Toma la entrada como una tabla de 8x8 de :s con los caballeros marcados con Ns, con un dígito para el número de vueltas en la siguiente línea (no tiene sentido tener más de 9 vueltas, pero si insiste, puedo apoyarlo por un extra byte). Tenga en cuenta que la salida contiene espacio en blanco adicional. Editar: Guardado 45 bytes gracias a @MartinEnder. Explicación: La primera etapa convierte el número de turnos a unario, pero usando caracteres de tabulación, para que no se emparejen más tarde por accidente, mientras que la segunda etapa agrega algunos espacios a la derecha del tablero para evitar que las expresiones regulares se envuelvan el borde. La tercera etapa reemplaza todos Nlos :sys que se alejan de un caballero Ncon un ntiempo, mientras que la cuarta etapa elimina cualquier Ns restante , cambia elnsaNs, y resta 1 del conteo de movimientos. Esto se repite hasta que el conteo de movimientos es cero.

Neil
fuente
Esto es lo más impresionante. ¡Definitivamente no es la herramienta adecuada para el trabajo!
Adám
4

Jalea , 29 bytes

+þ1,2Œ!×þ1,-p`¤¤Ẏ¤Ẏ⁼%8$$ÐfQµ¡

Pruébalo en línea!

Coordenadas indexadas a 0. Casi seguro que esto es subóptimo.

-1 byte gracias al usuario202729

Explicación

+þ1,2Œ!×þ1,-p`¤¤Ẏ¤Ẏ⁼%8$$ÐfQµ¡  Main Link
+þ                             Addition Table (all pairs using + as combining function) with
  1,2Œ!×þ1,-p`¤¤Ẏ¤             All knight moves:
  1,2                          [1, 2]
     Œ!                        All permutations ([1, 2], [2, 1])
       ×þ                      Product Table (all pairs using × as combining function) with
         1,-p`¤                [1, 1], [1, -1], [-1, 1], [-1, -1]
         1,-                   [1, -1]
            p`                 Cartestian Product with itself
               ¤               All knight moves (in a nested array) as a nilad
                Ẏ¤             Tighten (flatten once); all knight moves in a (semi-)flat array
                        Ðf     Keep elements where
                   ⁼%8$$       The element equals itself modulo 8 (discard all elements out of the range)
                          Q    Remove Duplicates
                           µ   Start new monadic chain (essentially, terminates previous chain)
                            ¡  Repeat n times; n is implicitly the second input (right argument)
Hiperneutrino
fuente
1
¿Jalea indexada 0?
Adám
1
@ Adám facilita el filtrado: P
HyperNeutrino
2
Espero que Jelly pueda hacer esto en menos de 15 bytes, debido a que el poseedor del registro actual en APL lo hace en 24 caracteres.
Adám
Cuando tiene> = 3 $, es probable que pueda moverlo al enlace anterior y consultarlo nuevamente Ç.
user202729
@ user202729 Oh sí, es verdad, gracias.
HyperNeutrino
3

05AB1E , 27 25 bytes

¡Gracias a Emigna por guardar 2 bytes!

Utiliza coordenadas indexadas 1.

Código:

F•eĆ•SÍü‚Dí«δ+€`Ùʒ{`9‹*0›

Utiliza la codificación 05AB1E . Pruébalo en línea!

Explicación:

F                          # Do the following <input_1> times..
 •eĆ•SÍ                    #   Push [-1, -2, 1, 2, -1]
       ü‚                  #   Pairwise pairing: [[-1, -2], [-2, 1], [1, 2], [2, -1]]
         D                 #   Duplicate the array
          í                #   Reverse each element
           «               #   Concatenate to the previous array

Esto nos da la siguiente matriz:

[[-1, -2], [-2, 1], [1, 2], [2, -1], [-2, -1], [1, -2], [2, 1], [-1, 2]]

Cuáles son los deltas de los movimientos del caballero.

            δ+             #   Addition vectorized on both sides
              €`           #   Flatten each element
                Ù          #   Uniquify
                 ʒ         #   Keep elements which..
                  {`9‹     #     Has a maximum element smaller than 9
                      *0›  #     And a minimum element larger than 0
Adnan
fuente
Puede usar en •eĆ•SÍü‚lugar de Ƶ‡4в2ô<D(«guardar 2 bytes.
Emigna
@Emigna Ahh, eso es inteligente, ¡gracias!
Adnan
2

Python 3, 105 bytes

p=lambda g,i:i and list(set(p([x+y for x in g for y in[6,10,15,17,-6,-10,-15,-17]if 0<=x+y<64],i-1)))or g

Tiene que usar una lambda con nombre para la recursión. No estoy seguro si eso es descalificador. Pase en posiciones iniciales como lista de números cuadrados indexados a 0. 0 cuenta como sin movimientos.

mypetlion
fuente
2

Java (OpenJDK 8) , 124 bytes

(m,p)->{for(;m-->0;)for(long a=p,i=p=0,j;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}

Pruébalo en línea!

Formato de entrada / salida

La entrada / salida se representa como bits en a long(64 bits): los bits establecidos significan que hay un caballo, los bits no establecidos significan que no hay caballo. Ejemplo:

// [[0, 0]]
0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001L

Explicaciones

(m, p) -> {                          // Lambda. No currying because m and p are modified
 for(;m-->0;)                        // For each move
  for(long a=p,i=p=0,j;i<64;i++)     // Declare variables, move p to a, create a new p and loop on bits of a.
   for(j=64;j-->0;)                  // Loop on bits of p.
    p |=                             // Assign to p a value.
     (p=i%8-j%8)*p+(p=i/8-j/8)*p==5  // If i -> j is a valid horse move, see Arnauld's JavaScript answer for full explanations
      ? (a>>i&1)<<j                  // Assign the presence of the horse (i-th bit of a) to the resulting board (j-th bit of p).
      : 0;                           // Else it's not a valid horse move
 return p;
}

Créditos

  • ¡19 bytes guardados gracias a Nevay!
  • Reutilizó el (X-x)²+(Y-y)²==5truco de la respuesta de JavaScript de Arnauld
  • ¡1 byte más guardado gracias a Nevay en el nuevo algoritmo!
  • 7 bytes más guardados gracias a Nevay nuevamente al cambiar de int[]64 bits long.
Olivier Grégoire
fuente
1
169 bytes:(m,p)->{for(;m-->0;){int i=64,a[]=p,x,y,u[]={1,3,5,9,15,19,21,23};for(p=new int[i];i-->0;)for(int z:u)if((((x=i/8+z/5-2)|(y=i%8+z%5-2))&-8)==0)p[x*8+y]|=a[i];}return p;}
Nevay
1
-1 byte:(m,p)->{for(int i,j,a[],x;m-->0;)for(a=p,p=new int[i=64];i-->0;)for(j=64;j-->0;)p[j]|=(x=i%8-j%8)*x+(x=i/8-j/8)*x==5?a[i]:0;return p;}
Nevay
Gracias @Nevay! ¡Agregar código para eliminar paréntesis / bloques siempre es bueno! ;-)
Olivier Grégoire
1
-7 bytes reemplazando int[]con long:(m,p)->{for(long i,j,a;m-->0;)for(a=p,p=i=0;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}
Nevay
Saludos, ¡ni siquiera pensé en hacer eso! Buen trabajo, @Nevay ;-)
Olivier Grégoire
2

Jalea , 29 28 bytes

8Rp`
“¦Ʋƈ2’D_2ṡ2+€µẎ
ÇƓ¡f1£Q

Pruébalo en línea!

El número de turnos es a través de STDIN, y los cuadrados son un argumento.

Esto vincula la solución Jelly de @ HyperNeutrino, pero con un enfoque diferente.

¡Ahora venciendo a @HyperNeutrino por 1 byte entero!

¡Se necesitan sugerencias para eliminar algunos bytes!

Enlace 1 (El tablero de ajedrez)

8Rp`
8R   = The list [1,2,3,4,5,6,7,8]
  p` = cartesian multiplied with itself (this results in the chessboard)

Enlace 2 (generación de movimiento)

“¦Ʋƈ2’D_2ṡ2+€µẎ
“¦Ʋƈ2’          = the number 103414301
      D         = converted into a list of digits
       _2       = subtract two from each element
         ṡ2     = overlapping pairs
           +€   = add to the list of squares
             µ  = Make sure the next part isn't treated as a right argument
              Ẏ = Tighten the list (Reducing the depth by one)

Enlace 3 (verificación cuadrada)

ÇƓ¡f1£Q
ÇƓ¡     = Repeat link #2 the requested amount of times
   f1£  = Remove everything not a member of link #1 (not on the chess board)
      Q = Make sure squares don't appear more than once
Zacharý
fuente
1

Casco , 18 bytes

u!¡ṁö`fΠR2ḣ8=5ṁ□z-

Utiliza la indexación basada en 1 de cuadrados y pasos. Pruébalo en línea!

Explicación

u!¡ṁö`fΠR2ḣ8=5ṁ□z-  Implicit inputs, say P=[[1,1],[5,7]] and n=2
  ¡                 Iterate on P:
   ṁö               Map the following function, then concatenate:
                     Argument is a pair, say p=[5,7].
          ḣ8         The range [1,2,..,8]
       ΠR2           Repeat twice, take cartesian product: [[1,1],[1,2],..,[8,8]]
     `f              Filter with this predicate:
                      Argument is a pair, say q=[3,8].
                z-    Zip p and q with difference: [-2,1]
              ṁ□      Sum of squares: 5
            =5        Is it 5? Yes, so [3,8] is kept.
 !                  Take n'th step of the iteration.
u                   Remove duplicates, implicitly print.
Zgarb
fuente
1

R , 145 183 134 bytes

Este es el resultado del excelente juego de golf de Giuseppe de mi algo inicial no demasiado golfista (vea el comentario a continuación)

function(x,n){x=x%/%8*24+x%%8
t=c(49,47,26,22)
t=c(t,-t)
for(i in 1:n)x=intersect(v<-outer(1:8,0:7*24,"+"),outer(x,t,"+"))
match(x,v)}

Pruébalo en línea!

La entrada y la salida están basadas en 1 ... 64. Toma un vector de posición usando la notación 1 ... 64. Lo asigna a una notación de 1: 576, que es un súper tablero compuesto de nueve tableros. En esta notación, en cada iteración, cada caballero debería poder moverse en +/- 22,26,47,49 Devolver posiciones futuras de nuevo en la notación 1 ... 64, excluyendo aquellas que caen del tablero central. El ejemplo TIO muestra el resultado usando una matriz de 8x8.

NofP
fuente
Esto parece fallar en el primer caso de prueba (devuelve 4 coordenadas en lugar de 2).
Zgarb
Gracias por señalarlo Zgarb, creo que solucioné el problema ahora
NofP
154 bytes
Giuseppe
o 148 bytes si lo tomas en [0...63]notación en su lugar.
Giuseppe
1
134 bytes , [1..64]para entrada y salida. +1, sin embargo, esta es una excelente respuesta.
Giuseppe