Contexte

La séquence OEIS A272573 décrit une spirale sur une grille hexagonale comme suit:

Commencez une spirale de nombres sur un pavage hexagonal, avec l'hexagone initial sous la forme a (1) = 1. a (n) est le plus petit entier positif non égal ou précédemment adjacent à ses voisins.

La séquence commence

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

Voici une illustration du motif en spirale:

• a(11) != 1car alors 3et 1serait adjacent à deux endroits.
• a(11) != 2car alors 3et 2serait adjacent à deux endroits.
• a(11) != 3car alors 3serait adjacent à lui-même.
• a(11) != 4car alors 3et 4serait adjacent à deux endroits.
• Par conséquent a(11) = 5.

Défi

Le défi consiste à écrire un programme qui calcule A272573 . C'est le code-golf , donc le code le plus court l'emporte.

JavaScript (ES6),  267 .. 206  199 octets

Renvoie un tableau contenant les premiers termes de la séquence.$N$

n=>(F=v=>++i<n?F([...v,(A=N[i]=[1,!j++||d+1,j%L?d:(j%=L*6)?++d:L++&&d++].map(k=>N[k=i-k].push(i)&&k),g=k=>v[E='every']((V,x)=>V-k|N[x][E](y=>A[E](z=>v[y]-v[z])))?k:g(-~k))()]):v)([L=1],N=[[i=j=d=0]])

Essayez-le en ligne!

Comment?

Définitions

Par convention, nous appellerons cellule de coin une cellule qui n'a qu'un seul bord en commun avec la couche précédente de la spirale et cellule latérale une cellule qui a deux bords en commun avec la couche précédente. Comme suggéré par Ourous, nous pouvons également les considérer comme des cellules d'ordre 1 et des cellules d'ordre 2, respectivement.

Les cellules d'angle sont représentées en jaune ci-dessous. Toutes les autres cellules sont des cellules latérales (sauf la cellule centrale qui est un cas spécial).

À propos des voisins de cellule

Nous n'avons pas vraiment besoin de suivre les coordonnées des cellules de la grille. La seule chose que nous devons savoir est la liste des cellules voisines pour chaque cellule de la spirale à un moment donné.

Dans les diagrammes suivants, les voisins de la couche précédente sont représentés en teinte claire et les voisins supplémentaires de la couche actuelle en teinte plus foncée.

Une cellule a 2 voisins parmi les cellules précédentes si:

• c'est la première cellule latérale d'une nouvelle couche (comme 8 )
• ou c'est une cellule d'angle, mais pas la dernière de la couche (comme 9 )

Une cellule a 3 voisins parmi les cellules précédentes si:

• c'est une cellule latérale, mais pas la première de la couche (comme 10 )
• ou c'est la dernière cellule de coin du calque courant (comme 19 )

Implémentation de voisins de cellule

L'index de la cellule courante (commençant à ) est stocké dans . La liste des voisins d'une cellule est stockée dans .$1$$i$$n$$A[n]$

Pour des raisons de golf obscures, nous calculons d'abord les décalages opposés des voisins. Par exemple, signifie , ce qui signifie la cellule précédente .$1$$-1$

[                    //
  1,                 // the previous cell is always a neighbor of the current cell
  !j++ || d + 1,     // if this is not the first cell of the layer, the cell at -(d + 1)
                     // is a neighbor (otherwise, we insert 1 twice; doing it that way
                     // saves bytes and having duplicate neighbors is not a problem)
  j % L ?            // if this is a side-cell:
    d                //   the cell at -d is a neighbor
  :                  // else (corner-cell):
    (j %= L * 6) ?   //   if this is not the last cell:
      ++d            //     insert the dummy duplicate neighbor at -(d + 1); increment d
    :                //   else (last cell):
      L++ && d++     //     the cell at -d is a neighbor; increment L; increment d
]                    //

Dans le code ci-dessus:

• $L$ est l'indice de la couche courante, commençant à (et sans compter la cellule centrale).$1$
• $j$ est l'indice de la cellule courante à l'intérieur de la couche courante, allant de à .$1$$6\times L$
• $d$ est la distance de la cellule actuelle à celles de la couche précédente. Il est incrémenté chaque fois que nous traversons une cellule d'angle.

Nous traitons ensuite une map()boucle qui convertit les décalages en indices ( ) et poussons la cellule actuelle comme nouveau voisin pour toutes les cellules voisines, pour imposer la symétrie de voisinage.$k$$i-k$

.map(k =>
  N[k = i - k].push(i) && k
)

Recherche du prochain terme de la séquence

Maintenant que nous avons une liste à jour des voisins pour toutes les cellules, nous pouvons enfin calculer le prochain terme de la séquence, en utilisant une autre fonction d'aide récursive.$k$

La valeur d'une cellule est stockée dans .$n$$v[n]$

( g =                 // g = recursive function taking
  k =>                // the candidate value k
    v.every((V, x) => // for each previous cell of value V at position x, make sure that:
      V - k           //   V is not equal to k
      |               //   OR
      N[x].every(y => //   for each neighbor y of x:
        A.every(z =>  //     for each neighbor z of the current cell:
          v[y] - v[z] //       the value of y is not equal to the value of z
        )             //     end
      )               //   end
    )                 // end
    ?                 // if the above conditions are fulfilled:
      k               //   stop recursion and return k
    :                 // else:
      g(-~k)          //   try again with k + 1
)()                   // initial call to g with k undefined (this will cause V - k to be
                      // evaluated as NaN and force the 1st iteration to fail)

Propre , 284 279 272 262 octets

import StdEnv
l=[0,-1,-1,0,1,1]
c(u,v)(p,q)=(u-p)^2+(v-q)^2<2||(u-p)*(q-v)==1
$[h:t]m=hd[[e: $t[(h,e):m]]\\e<-[1..]|and[e<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]]

$(scan(\(a,b)(u,v)=(a-u,b-v))(0,0)[(i,j)\\n<-[1..],i<-[1,1:l]&j<-l,_<-[max(~j<<i)1..n]])[]

Essayez-le en ligne!

Génère la séquence pour toujours.

Cartographie hexagonale

La plupart du code est utilisé pour mapper des hexagones uniquement aux (x,y)coordonnées de sorte qu'il existe une fonction simple et simple pour déterminer la contiguïté qui s'applique à tous les mappages de points.

Les points mappés ressemblent à ceci:

              ---
        --- < 2,-2> ---       x-axis ___.X'
  --- < 1,-2> === < 2,-1> ---  /__.X'
< 0,-2> === < 1,-1> === < 2, 0>'
  === < 0,-1> === < 1, 0> ===
<-1,-1> === < 0, 0> === < 1, 1>
  === <-1, 0> === < 0, 1> ===
<-2, 0> === <-1, 1> === < 0, 2>.__
  --- <-2, 1> === <-1, 2> ---  \  'Y.___
        --- <-2, 2> ---       y-axis    'Y.
              ---

À partir de là, la détermination de l'adjacence est triviale et se produit lorsque l'un des éléments suivants:

• x1 == x2 et abs(y1-y2) == 1
• y1 == y2 et abs(x1-x2) == 1
• y1 == y2 - 1 et x2 == x1 - 1
• y1 == y2 + 1 et x2 == x1 + 1
• x1 == x2 et y1 == y2

Génération de points

Notez que lors de la traversée de l'hexagone en spirale, les différences se reproduisent pour chaque couche n:

1. n étapes de (1,0)
2. n-1 étapes de (1,-1)
3. n étapes de (0,-1)
4. n étapes de (-1,0)
5. n étapes de (-1,1)
6. n étapes de (0,1)

Cela génère les points dans le bon ordre en prenant des sommes de préfixes de cette séquence:

scan(\(a,b)(u,v)=(a-u,b-v))(0,0)[(i,j)\\n<-[1..],i<-[1,1:l]&j<-l,_<-[max(~j<<i)1..n]]

Le rassembler

Le code qui trouve réellement la séquence de la question est juste:

$[h:t]m=hd[[e: $t[(h,e):m]]\\e<-[1..]|and[e<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]]

Qui à son tour est principalement filtré par and[r<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]

Ce filtre prend des points de m(la liste des points déjà mappés) par:

• Ignorer les nombres naturels égaux à tout j
• Pour chaque (i,j)où iest adjacent àp
• Pour chaque (p,q)où la valeur qest égale àv
• Pour chaque (u,v)où uest adjacent au point actuel