Jouez à un programme ou à une fonction qui donne l' emplacement du gnou qui commence à la case sur un échiquier infini numéroté dans une spirale carrée dans le sens inverse des aiguilles d'une montre, où le gnou visite toujours la case la moins numérotée elle peut arriver qu'elle n'a pas encore visité.$n^{\text{th}}$ 1$1$

Inspiration: Le chevalier pris au piège et OEIS A316667 .

Edit: Cette séquence est maintenant sur l'OEIS en tant que A323763 .

Le code peut produire l' emplacement , les premiers emplacements, ou générer la séquence sans aucune entrée.$n^{\text{th}}$$n$

N'hésitez pas à lui donner sa position après (ou jusqu'à) sauts, mais si c'est le cas, veuillez l'indiquer clairement dans votre réponse et assurez-vous qu'une entrée de donne (ou le cas échéant).$n$$n=0$1[1]

Il s'agit de code-golf , donc l'objectif est de produire du code de travail dans le moins d'octets possible dans la langue de votre choix.

Remarque: le gnou devient piégé (un peu comme le chevalier le fait à son emplacement en , carré , et le chameau le fait à son , carré ) chez elle emplacement sur le carré . Le comportement de votre code peut être indéfini pour plus grand que cela. (Merci à Deadcode pour le code C ++ qui l'a trouvé!)$2016^{\text{th}}$$2084$$3723^{\text{rd}}$$7081$$12899744968^{\text{th}}$$12851850258$$n$

Détail

Le tableau ressemble à ce qui suit et continue indéfiniment:

101 100  99  98  97  96  95  94  93  92  91
102  65  64  63  62  61  60  59  58  57  90
103  66  37  36  35  34  33  32  31  56  89
104  67  38  17  16  15  14  13  30  55  88
105  68  39  18   5   4   3  12  29  54  87
106  69  40  19   6   1   2  11  28  53  86
107  70  41  20   7   8   9  10  27  52  85
108  71  42  21  22  23  24  25  26  51  84
109  72  43  44  45  46  47  48  49  50  83
110  73  74  75  76  77  78  79  80  81  82
111 112 113 114 115 116 117 118 119 120 121

Un gnou est une pièce d'échecs féerique "gnu" - une pièce d'échecs non standard qui peut se déplacer à la fois en tant que chevalier (un -leaper) et en tant que chameau (un -leaper). En tant que telle, elle pourrait se déplacer vers l'un de ces emplacements à partir de son emplacement de départ :$(1,2)$( 1 , 3 ) 1$(1,3)$
$1$

  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .  35   .  33   .   .   .   .
  .   .   .   .  16   .  14   .   .   .   .
  .   .  39  18   .   .   .  12  29   .   .
  .   .   .   .   .  (1)  .   .   .   .   .
  .   .  41  20   .   .   .  10  27   .   .
  .   .   .   .  22   .  24   .   .   .   .
  .   .   .   .  45   .  47   .   .   .   .
  .   .   .   .   .   .   .   .   .   .   .

Le plus bas d'entre eux est et elle n'a pas encore visité ce carré, donc est le deuxième terme de la séquence.$10$$10$

Elle pouvait ensuite passer de à n'importe lequel de ces endroits:$10$

  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .   .   .  14   .  30   .   .
  .   .   .   .   .   .   3   .  29   .   .
  .   .   .   .   6   1   .   .   .  53  86
  .   .   .   .   .   .   . (10)  .   .   .
  .   .   .   .  22  23   .   .   .  51  84
  .   .   .   .   .   .  47   .  49   .   .
  .   .   .   .   .   .  78   .  80   .   .
  .   .   .   .   .   .   .   .   .   .   .

Cependant, elle a déjà visité la case , son troisième emplacement est donc la case , la plus basse qu'elle n'a pas encore visitée.$1$$3$

---

Les premiers termes du chemin du gnou sont:$100$

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85

Les premiers sauts sont des mouvements de chevalier, donc les premiers termes coïncident avec A316667 .$11$$12$

JavaScript (Node.js) ,  191 ... 166  164 octets

Enregistré 2 octets grâce à @grimy .

Renvoie le ^ème terme.$N$

n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').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! ou Voir une version formatée

Comment?

Indices en spirale

Afin de convertir les coordonnées en l'indice de spirale , nous calculons d'abord la couche avec:$(x,y)$$I$$L$

$$L=\max(|x|,|y|)$$

Qui donne:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&3&3&3&3&3&3&3\\ -2&3&2&2&2&2&2&3\\ -1&3&2&1&1&1&2&3\\ 0&3&2&1&0&1&2&3\\ +1&3&2&1&1&1&2&3\\ +2&3&2&2&2&2&2&3\\ +3&3&3&3&3&3&3&3 \end{array}$$

Nous calculons ensuite la position dans la couche avec:$P$

$$P=\begin{cases} 2L+x+y&\text{if }x>y\\ -(2L+x+y)&\text{if }x\le y \end{cases}$$

Qui donne:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&0&1&2&3&4&5&6\\ -2&-1&0&1&2&3&4&7\\ -1&-2&-1&0&1&2&5&8\\ 0&-3&-2&-1&0&3&6&9\\ +1&-4&-3&-2&-3&-4&7&10\\ +2&-5&-4&-5&-6&-7&-8&11\\ +3&-6&-7&-8&-9&-10&-11&-12 \end{array}$$

L'indice final est donné par:$I$

$$I=4L^2-P$$

NB: La formule ci-dessus donne une spirale indexée 0.

Dans le code JS, nous calculons en fait immédiatement avec:$4L^2$

i = 4 * (x * x > y * y ? x : y) ** 2

Et puis soustrayez avec:$P$

i -= (x > y || -1) * (i ** 0.5 + x + y)

Les mouvements des gnous

Compte tenu de la position actuelle , les 16 carrés cibles possibles du gnou sont testés dans l'ordre suivant:$(x,y)$

$$\begin{array}{c|cccccccc} &-3&-2&-1&x&+1&+2&+3\\ \hline -3&\cdot&\cdot&9&\cdot&11&\cdot&\cdot\\ -2&\cdot&\cdot&8&\cdot&10&\cdot&\cdot\\ -1&7&6&\cdot&\cdot&\cdot&12&13\\ y&\cdot&\cdot&\cdot&\bullet&\cdot&\cdot&\cdot\\ +1&5&4&\cdot&\cdot&\cdot&14&15\\ +2&\cdot&\cdot&2&\cdot&0&\cdot&\cdot\\ +3&\cdot&\cdot&3&\cdot&1&\cdot&\cdot \end{array}$$

Nous les parcourons en appliquant 16 paires de valeurs signées . Chaque paire est codée comme un seul caractère ASCII.$(dx,dy)$

 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated
----+-------+------------+-------+-------+-----------
  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)
  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)
  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)
  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)
  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)
  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)
  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)
  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)
  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)
  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)
 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)
 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)
 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)
 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)
 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)
 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)

Nous gardons une trace de la valeur minimale rencontrée en et des coordonnées de la cellule correspondante en .$m$$(H,V)$

Une fois le meilleur candidat trouvé, nous le marquons comme visité en positionnant un drapeau dans l'objet , qui est également notre fonction récursive principale.$g$

À la première itération, nous commençons par et . Cela garantit que la première cellule sélectionnée est et que c'est la première cellule à être marquée comme visitée.$x=1$$y=2$$(0,0)$

Noix de coco , 337 276 octets

import math
def g((x,y))=
 A=abs(abs(x)-abs(y))+abs(x)+abs(y)
 int(A**2+math.copysign(A+x-y,.5-x-y)+1)
def f():
 p=x,y=0,0;s={p};z=[2,3,1,1]*2
 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)

Renvoie un générateur de valeurs. Pourrait probablement être joué au golf plus. ( En particulier , la séquence de tuples de différence.) De l' algorithme de prise en spirale cette réponse math.se .

Essayez-le en ligne!

05AB1E , 77 65 58 57 52 octets

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

-6 octets grâce à @Arnauld en utilisant un portage de sa formule.

Génère les valeurs sous forme de liste (de décimales).$n+1$

Essayez-le en ligne (le ïdans le pied de page supprime le .0pour rendre la sortie plus compacte, mais n'hésitez pas à le supprimer pour voir le résultat réel).

Explication du code:

Xˆ             # Put integer 1 in the global_array (global_array is empty by default)
0U             # Set variable `X` to 0 (`X` is 1 by default)
F              # Loop the (implicit) input amount of times:
 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]
     0K        #  Remove the 0: [-3,-2,-1,1,2,3]
       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]
        ʒ   }  #  Filter this list of pairs by:
         Ä     #   Where the absolute values of the pair
          1¢   #   Contains exactly one 1
               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])
 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list
 D             #  Duplicate this list of coordinates
  ε            #  Map each `x,y`-coordinate to:
   ·           #   Double both the `x` and `y` in the coordinate
    n          #   Then take the square of each
     à         #   And then pop and push the maximum of the two
   Dt          #   Duplicate this maximum, and take its square-root
     yÆ        #   Calculate `x-y`
       +       #   And add it to the square-root
   yO          #   Calculate `x+y`
     ·         #   Double it
      <        #   Decrease it by 1
       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)
   *           #   Multiply these two together
    -          #   And subtract it from the duplicated maximum
   >           #   And finally increase it by 1 to make it 1-based instead of 0-based
  }D           #  After the map: Duplicate that list with values
    ¯K         #  Remove all values that are already present in the global_array
      ß        #  Pop the list of (remaining) values and push the minimum
       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array
         k     #  Then get its index in the complete list of values
          è    #  And use that index to get the corresponding coordinate
           U   #  Pop and store this coordinate in variable `X` for the next iteration
}¯             # After the outer loop: push the global_array (which is output implicitly)

Explication générale:

Nous détenons tous les résultats (et donc les valeurs que nous avons déjà rencontrées) dans le global_array, qui est initialement démarré en tant que [1].
Nous détenons la coordonnée actuelle en variable , qui est initialement .$x,y$X[0,0]

La liste des coordonnées que nous pouvons atteindre en fonction des coordonnées actuelles est:$x,y$

[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]

La liste que je mentionne dans l'explication du code ci-dessus contient ces valeurs auxquelles nous pouvons accéder, après quoi le actuel (stocké dans une variable ) est ajouté.$x,y$X

Ensuite, il calculera les valeurs en spirale sur la base de ces coordonnées . Pour ce faire, il utilise la formule suivante pour une coordonnée donnée :$x,y$$x,y$

$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$ $${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$

C'est la même formule que @Arnauld utilise dans sa réponse , mais écrite différemment pour utiliser les fonctions internes de 05AB1E pour double, carré, -1, +1, etc.

(Si vous voulez voir uniquement cette partie en spirale du code en action: essayez-la en ligne .)

Après avoir obtenu toutes les valeurs que nous pouvons atteindre pour la coordonnée donnée , nous supprimons toutes les valeurs qui sont déjà présentes dans le , puis nous obtenons le minimum des valeurs (restantes). Ce minimum est ensuite ajouté à la variable, et est remplacé par la coordonnée de ce minimum.$x,y$x , yglobal_array
global_arrayX$x,y$

Après avoir bouclé le inputnombre de fois, le programme affichera cela global_arrayen résultat.