introduction

Inspiré par la vidéo très récente The Trapped Knight - Numberphile , j'ai trouvé un défi.

La séquence de chevalier piégé est une séquence entière finie de longueur 2016, à partir de 1, et a les règles de construction suivantes:

1. Écrivez une spirale numérique de la manière suivante:

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. Placez un chevalier sur 1.
3. Déplacez le chevalier sur la grille avec le plus petit nombre possible qui n'a pas été visité auparavant, selon les règles des échecs (c'est-à-dire 2 unités verticalement et 1 unité horizontalement, ou vice versa).
4. Répétez jusqu'à ce que le chevalier se coince.

Voici les trois premières étapes:

Étape 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 

Les mouvements possibles sont 10, 12, 14, 16, 18, 20, 22, 24, dont le plus petit est 10, donc le deuxième terme est 10.

Étape 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 

Les mouvements possibles sont 1 , 3, 23, 29, 47, 49, 51, 53, dont le plus petit est 3, donc le troisième terme est 3.

Étape 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 

Les mouvements possibles sont 6, 8, 10 , 16, 28, 30, 32, 34, parmi lesquels le plus petit est 6, donc le quatrième terme est 6.

La séquence commence par:

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

et se termine par

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

Défi

Écrivez un programme ou une fonction plus courte, en recevant un entier dans la plage [1, 2016](ou [0, 2015]si l'index 0 est utilisé) en entrée, sortez le nombre à cet index dans la séquence de chevalier piégé. Vous pouvez choisir d'indexer la séquence avec 0 ou 1, mais vous devez spécifier le schéma d'indexation que vous utilisez.

Cas de test (1 indexé)

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

Pour toutes les sorties possibles, veuillez vous référer à cette page .

Critères gagnants

Le code le plus court de chaque langue gagne. Des restrictions sur les échappatoires standard s'appliquent.

JavaScript (ES7),  182  181 octets

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

Essayez-le en ligne!

Comment?

Une version légèrement modifiée de ma réponse à The Path Of The Wildebeest est définitivement plus courte (et plus rapide) que cela. Mais je voulais essayer une approche différente. Soit dit en passant, je pense qu'il pourrait être plus facile de mettre en œuvre cette méthode dans certainsSoit dit passant esolangs.

Algorithme:

1. $3199$ ).

2. $(X,Y)$

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

   $(x,y)$ sont les coordonnées actuelles du chevalier.

   $|x-X|=1$$|y-Y|=2$$|x-X|=2$$|y-Y|=1$ , qui couvre tous les mouvements de chevalier possibles.

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

4. Nous redémarrons à l'étape 2 ou renvoyons le dernier index trouvé si nous avons terminé.

Node.js , 155 octets

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)

Essayez-le en ligne!

05AB1E , 53 octets

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

32θ$n+1$ éléments.

Essayez-le en ligne ou vérifiez d'autres cas de test (expire pour les plus grands cas de test).

Explication:

Voir l'explication dans ma réponse liée Le chemin des gnous . Les seules pièces modifiées sont:

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

et un suivi:

θ       # Only leave the last item of the list

EDIT: Un portage de l'approche @Arnauld dans sa réponse JavaScript (ES7) est (actuellement):

05AB1E , 57 56 octets

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

Essayez-le en ligne ou vérifiez d'autres cas de test (expire pour les plus grands cas de test).

Explication:

‚%                # 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 octets

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

L'entrée est basée sur 0.

Essayez-le en ligne!