Une séquence en spirale

29

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: entrez la description de l'image ici

  • 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 , donc le code le plus court l'emporte.

Peter Kagey
la source
Je ne peux pas voir l'image car elle est bloquée ici, alors peut-être que je manque quelque chose, mais votre exemple montre un (11) = 4, mais dans votre liste de séquences, un (11) est 5.
Geobits
Juste une erreur - merci de l'avoir attrapé.
Peter Kagey
7
Cette séquence OEIS a été soumise par vous-même, apparemment. Agréable. :)
Arnauld
quelle est la limite pour n? y a-t-il un délai?
Setop
5
En attente d'une réponse Hexagony ...
Jonathan Allan

Réponses:

23

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).

types de cellules

À 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 )

2 voisins

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 )

3 voisins

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 .1jenUNE[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 à .16×L
  • 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.kje-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 .nv[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)
Arnauld
la source
Grande explication. Une amélioration possible: rendre les explications dans les blocs de code entièrement visibles sans avoir besoin de défilement horizontal (peu importe pour le code joué). Dans Firefox, il y a 5 colonnes cachées dans le premier bloc de code d'explication et 6 colonnes cachées dans le second.
trichoplax
@trichoplax Merci pour votre commentaire et suggestion. Pourriez-vous spécifier quelle version de Firefox vous utilisez et sur quelle plateforme? J'essaie toujours de formater les blocs d'explication afin qu'aucun défilement horizontal ne soit nécessaire. Je suis sur Firefox 65 / Win10 en ce moment et je n'ai aucune colonne cachée.
Arnauld
Vérifie la version de Firefox à mon retour, mais c'est peut-être parce que je suis sur Fedora. Va vérifier sur un autre OS et vous le
fera
1
Cela semble varier selon le système d'exploitation. Soulèvera ceci sur MSE quand j'aurai eu l'occasion de rassembler des preuves (si ce n'est pas déjà fait)
trichoplax
1
J'ai soulevé cette question sur MSE . N'hésitez pas à modifier si quelqu'un voit d'autres combinaisons OS / navigateur qui affichent des barres de défilement horizontales.
trichoplax
7

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)iest adjacent àp
  • Pour chaque (p,q)où la valeur qest égale àv
  • Pour chaque (u,v)uest adjacent au point actuel
Οurous
la source