Eine spiralförmige Sequenz

29

Hintergrund

Die OEIS-Sequenz A272573 beschreibt eine Spirale auf einem hexagonalen Gitter wie folgt:

Beginnen Sie eine Spirale von Zahlen auf einer hexagonalen Kachelung, wobei das anfängliche Sechseck a (1) = 1 ist.

Die Sequenz beginnt

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

Hier ist eine Illustration des Spiralmusters: Bildbeschreibung hier eingeben

  • a(11) != 1 weil dann 3 und 1wäre an zwei Stellen nebeneinander.
  • a(11) != 2 weil dann 3 und 2wäre an zwei Stellen nebeneinander.
  • a(11) != 3 weil dann 3 wäre neben sich.
  • a(11) != 4 weil dann 3 und 4wäre an zwei Stellen nebeneinander.
  • Deshalb a(11) = 5 .

Herausforderung

Die Herausforderung besteht darin, ein Programm zu schreiben, das A272573 berechnet . Das ist , also gewinnt der kürzeste Code.

Peter Kagey
quelle
Ich kann das Bild nicht sehen, da es hier blockiert ist. Vielleicht fehlt mir etwas, aber Ihr Beispiel zeigt a (11) = 4, aber in Ihrer Sequenzliste ist a (11) 5.
Geobits
Nur ein Fehler - danke, dass Sie es verstanden haben.
Peter Kagey
7
Diese OEIS-Sequenz wurde anscheinend von Ihnen selbst eingereicht. Nett. :)
Arnauld
Was ist die Grenze für n? Gibt es eine zeitliche Begrenzung?
Setop
5
Warten auf Hexagony Antwort ...
Jonathan Allan

Antworten:

23

JavaScript (ES6),  267 .. 206  199 Bytes

Gibt ein Array zurück, das die N ersten Terme der Sequenz enthält.

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

Probieren Sie es online!

Wie?

Definitionen

Per Konvention werden wir nennen Ecke Zelle eine Zelle , die nur eine gemeinsame Kante mit der vorhergehenden Schicht der Spirale und hat Seiten Zelle eine Zelle , die zwei Ränder gemeinsam mit der vorherige Schicht aufweist. Wie vorgeschlagen von Ourous, können wir von ihnen als Auftrag-1 - Zellen und Ordnung-2 - Zellen denken auch, respectively.

Eckzellen sind unten in gelb dargestellt. Alle anderen Zellen sind Seitenzellen (mit Ausnahme der Mittelzelle, die ein Sonderfall ist).

Zelltypen

Über Zellnachbarn

Wir müssen nicht wirklich die Koordinaten der Zellen im Raster verfolgen. Das einzige, was wir wissen müssen, ist die Liste der Nachbarzellen für jede Zelle in der Spirale zu einem bestimmten Zeitpunkt.

In den folgenden Diagrammen werden Nachbarn in der vorherigen Ebene in hellem Schatten und zusätzliche Nachbarn in der aktuellen Ebene in dunklerem Schatten dargestellt.

Eine Zelle hat zwei Nachbarn unter den vorherigen Zellen, wenn:

  • Es ist die erste Seitenzelle einer neuen Ebene (wie 8 )
  • oder es ist eine Eckzelle, aber nicht die letzte der Ebene (wie 9 )

2 Nachbarn

Eine Zelle hat 3 Nachbarn unter den vorherigen Zellen, wenn:

  • es ist eine Seitenzelle, aber nicht die erste der Ebene (wie 10 )
  • oder es ist die letzte Eckzelle der aktuellen Ebene (wie 19 )

3 Nachbarn

Implementierung von Zellnachbarn

Der Index der aktuellen Zelle (beginnend mit 1) ist gespeichert in ich. Die Liste der Nachbarn einer Zellen ist gespeichert in EIN[n].

Aus undurchsichtigen Golfgründen berechnen wir zunächst die entgegengesetzten Offsets der Nachbarn. Zum Beispiel,1 meint -1, was die vorherige Zelle bedeutet .

[                    //
  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
]                    //

Im obigen Code:

  • L ist der Index der aktuellen Ebene, beginnend mit 1 (und die mittlere Zelle nicht mitzählen).
  • j ist der Index der aktuellen Zelle in der aktuellen Ebene, von der aus 1 zu 6×L.
  • dist der Abstand der aktuellen Zelle zu denen der vorherigen Ebene. Es wird jedes Mal erhöht, wenn wir durch eine Eckzelle gehen.

Wir verarbeiten dann eine map()Schleife, die die Offsets konvertiertk in Indizes (ich-k) und verschieben Sie die aktuelle Zelle als neuen Nachbarn für alle Nachbarzellen, um die Nachbarschaftssymmetrie zu erzwingen.

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

Den nächsten Term der Sequenz finden

Jetzt, da wir eine aktuelle Liste der Nachbarn für alle Zellen haben, können wir endlich den nächsten Begriff berechnen k der Sequenz mit einer anderen rekursiven Hilfsfunktion.

Der Wert einer Zelle n ist gespeichert in 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)
Arnauld
quelle
Tolle Erklärung. Eine mögliche Verbesserung: Die Erklärungen in den Codeblöcken vollständig sichtbar zu machen, ohne dass horizontal gescrollt werden muss (spielt für den Golfcode keine Rolle). In Firefox gibt es 5 versteckte Spalten im ersten Erklärungscodeblock und 6 versteckte Spalten im zweiten.
Trichoplax
@ Trichoplax Vielen Dank für Ihren Kommentar und Vorschlag. Können Sie angeben, welche Firefox-Version Sie verwenden und auf welcher Plattform? Ich versuche immer, Erklärungsblöcke so zu formatieren, dass kein horizontales Scrollen erforderlich ist. Ich bin gerade auf Firefox 65 / Win10 und habe keine versteckte Spalte.
Arnauld
Überprüft die Firefox-Version, wenn ich zu Hause bin, aber möglicherweise, weil ich auf Fedora bin. Überprüft ein anderes Betriebssystem und teilt es Ihnen mit
trichoplax
1
Es scheint von Betriebssystem zu Betriebssystem zu variieren. Ich werde dies auf MSE ansprechen, wenn ich Gelegenheit hatte, Beweise zu sammeln (falls dies noch nicht
geschehen ist
1
Ich habe dies bei MSE angesprochen . Fühlen Sie sich frei zu bearbeiten, wenn jemand andere OS / Browser-Kombinationen sieht, die horizontale Bildlaufleisten anzeigen.
Trichoplax
7

Sauber , 284 279 272 262 Bytes

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]])[]

Probieren Sie es online!

Erzeugt die Sequenz für immer.

Hexagon-Zuordnung

Der größte Teil des Codes wird verwendet, um Sechsecke eindeutig auf (x,y)Koordinaten abzubilden, sodass eine einzige, einfache Funktion zum Bestimmen der Adjazenz für alle Punktzuordnungen verfügbar ist.

Die abgebildeten Punkte sehen folgendermaßen aus:

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

Von dort aus ist das Bestimmen der Adjazenz trivial und tritt ein, wenn einer der folgenden Zustände vorliegt:

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

Punktgenerierung

Beachten Sie, dass beim Durchqueren des Sechsecks in einer Spirale die Unterschiede für jede Schicht erneut auftreten n:

  1. n Schritte von (1,0)
  2. n-1 Schritte von (1,-1)
  3. n Schritte von (0,-1)
  4. n Schritte von (-1,0)
  5. n Schritte von (-1,1)
  6. n Schritte von (0,1)

Dadurch werden die Punkte in der richtigen Reihenfolge generiert, indem die Präfixsummen dieser Reihenfolge verwendet werden:

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]]

Bring es zusammen

Der Code, der tatsächlich die Sequenz aus der Frage findet, lautet einfach:

$[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]]

Die wiederum filtert meist nach and[r<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]

Dieser Filter bezieht Punkte aus m(der Liste der bereits zugeordneten Punkte) nach:

  • Ignorieren von natürlichen Zahlen, die gleich sind j
  • Für jeden, (i,j)an den iangrenztp
  • Für jeden, (p,q)bei dem der Wert qgleich istv
  • Für jeden (u,v)wo uist zum aktuellen Punkt benachbart
Οurous
quelle