Introducción

Inspirado por el video muy reciente The Trapped Knight - Numberphile , se me ocurrió un desafío.

La secuencia de caballero atrapado es una secuencia entera finita de longitud 2016, a partir de 1, y tiene las siguientes reglas de construcción:

1. Escriba una espiral numérica de la siguiente manera:

17 16 15 14 13 ...
18  5  4  3 12 ...
19  6  1  2 11 ...
20  7  8  9 10 ...
21 22 23 24 25 ...

2. Coloca un caballero en 1.
3. Mueva al caballero a la cuadrícula con el número más pequeño posible que no haya sido visitado antes, de acuerdo con las reglas del ajedrez (es decir, 2 unidades verticalmente y 1 unidad horizontalmente, o viceversa).
4. Repita hasta que el caballero se atasque.

Aquí están los primeros tres pasos:

Paso 1

 17  [16]  15  [14]  13 
[18]   5    4    3  [12]
 19    6  < 1>   2   11 
[20]   7    8    9  [10]
 21  [22]  23  [24]  25 

Los movimientos posibles son 10, 12, 14, 16, 18, 20, 22, 24, entre los cuales el más pequeño es 10, por lo que el segundo término es 10.

Paso 2

  4  [ 3]  12  [29]  54
( 1)   2   11   28  [53] 
  8    9  <10>  27   52 
[23]  24   25   26  [51] 
 46  [47]  48  [49]  50 

Los movimientos posibles son 1 , 3, 23, 29, 47, 49, 51, 53, entre los cuales el más pequeño es 3, por lo que el tercer término es 3.

Paso 3

 35  [34]  33  [32]  31 
[16]  15   14   13  [30] 
  5    4  < 3>  12   29 
[ 6] ( 1)   2   11  [28] 
  7  [ 8]   9  (10)  27 

Los movimientos posibles son 6, 8, 10 , 16, 28, 30, 32, 34, entre los cuales el más pequeño es 6, por lo que el cuarto término es 6.

La secuencia comienza con:

1 10 3 6 9 4 7 2 5 8 11 14 ...

y termina con

... 2099 2284 2477 2096 2281 2474 2675 2884 3101 2880 2467 2084

Desafío

Escriba un programa o función más corto, recibiendo un número entero en el rango [1, 2016](o [0, 2015]si se usa 0 indexado) como entrada, emite el número en ese índice en la secuencia de caballero atrapado. Puede elegir indexar la secuencia con 0 indexado o 1 indexado, pero debe especificar qué esquema de indexación utiliza.

Casos de prueba (1 indexado)

n    | s(n)
-----+-----
   1 |    1
   2 |   10
   3 |    3
   6 |    4
  11 |   11
  21 |   23
  51 |   95
 101 |   65
 201 |  235
 501 |  761
1001 | 1069
2001 | 1925
2016 | 2084

Para todas las salidas posibles, consulte esta página .

Criterios ganadores

El código más corto de cada idioma gana. Se aplican restricciones a las lagunas estándar.

JavaScript (ES7),  182  181 bytes

f=(n,[x,y]=[2,1],a=[...Array(4e3)].map((_,n)=>[1,-1].map(s=>(i&1?-s:s)*(i+s*n-(n>0?n:-n)>>1),i=n**.5|0,n-=i*++i)))=>n--?f(n,a.find(([X,Y],j)=>(i=j,(x-X)*(y-Y))**2==4),a,a[i]=[]):i+1

Pruébalo en línea!

¿Cómo?

Una versión ligeramente modificada de mi respuesta a The Path Of The Wildebeest es definitivamente más corta (y más rápida) que eso. Pero quería probar un enfoque diferente. Por cierto, creo que podría ser más fácil implementar este método en algunos esolangs.

Algoritmo:

1. $3199$

2. $(X,Y)$

   $$((x-X)\times(y-Y))^2=4$$

   $(x,y)$

   $|x-X|=1$$|y-Y|=2$$|x-X|=2$$|y-Y|=1$

3. $(x,y)=(X,Y)$

4. Reiniciamos en el paso 2 o devolvemos el último índice que se encontró si hemos terminado.

Nodo.js , 155 bytes

n=>(g=(x,y)=>n--?g(Buffer('QHUbcdWJ').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))|H,V,g[m]=1):m+1)(1,2)

Pruébalo en línea!

05AB1E , 53 bytes

Xˆ0UF2D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯θ

32θ$n+1$

Pruébelo en línea o verifique algunos casos de prueba más (tiempo de espera para los casos de prueba más grandes).

Explicación:

Vea la explicación en mi respuesta vinculada El camino del ñu . Las únicas partes modificadas son:

2D(Ÿ    # Get a list in the range [-2,2]: [-2,-1,0,1,2]

y un final:

θ       # Only leave the last item of the list

EDITAR: Un puerto del enfoque de @Arnauld en su respuesta de JavaScript (ES7) es (actualmente):

05AB1E , 57 56 bytes

0D‚DˆUF64D(ŸãΣ·nàDtyÆ+yO·<.±*->}©ʒX-Pn4Q}¯¡˜2£DˆU}®J¯Jk>θ

Pruébelo en línea o verifique algunos casos de prueba más (tiempo de espera para los casos de prueba más grandes).

Explicación:

‚%                # Create a pair of zeros: [0,0]
                  # (by pairing the (implicit) input with itself,
                  #  and then using modulo (implicit) input)
  DˆU             # Set both variable `X` to this, and add it to the global_array
F                 # Loop the (implicit) input amount of times:
 64D(Ÿ            #  Create a list in the range [-64,64]
      ã           #  Create each possible pair of `x,y`-coordinates
       Σ·nàDtyÆ+yO·<.±*->}
                  #  Sort this list in a spiral
        ©         #  Save it in the register (without popping)
 ʒ      }         #  Filter the list of coordinates by:
  X-              #   Subtract the coordinate of variable `X`
    P             #   Take the product
     n            #   Take the square
      4Q          #   Check if its equal to 4
                  # Since 05AB1E cannot remove inner lists, we use a workaround:
         ¯¡       # Split this list on each coordinate in the global_array
           ˜      # Flatten the entire list
            2£    # Only leave the first two integers as `x,y`-coordinate
                  # (if 05AB1E could remove inner lists, this would've been `¯Kн` instead)
              DˆU # Replace variable `X` with this, and add it to the global_array
}®                # After the loop: push all coordinates sorted in a spiral from the register
  J               # Join each coordinate together to a string
   ¯J             # Push the global_array, and also join them together to a string
                  # (if 05AB1E could index inner lists, both `J` could have been removed)
     k            # Get the index of each item of the global_array in the spiral list
      >           # Increase the 0-indexed index by 1 to make it 1-based
       θ          # And only leave the last one (which is output implicitly)

Σ·nàDtyÆ+yO·<.±*->}$x,y$

MATL , 41 37 bytes

62lYLt1=i:"YYw(t5Mf'<@{}'ot_h+)X<y=])

La entrada está basada en 0.

Pruébalo en línea!