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:
a(11) != 1
weil dann3
und1
wäre an zwei Stellen nebeneinander.a(11) != 2
weil dann3
und2
wäre an zwei Stellen nebeneinander.a(11) != 3
weil dann3
wäre neben sich.a(11) != 4
weil dann3
und4
wäre an zwei Stellen nebeneinander.- Deshalb
a(11) = 5
.
Herausforderung
Die Herausforderung besteht darin, ein Programm zu schreiben, das A272573 berechnet . Das ist Code-Golf , also gewinnt der kürzeste Code.
code-golf
sequence
hexagonal-grid
Peter Kagey
quelle
quelle
Antworten:
JavaScript (ES6),
267 .. 206199 BytesGibt ein Array zurück, das dieN ersten Terme der Sequenz enthält.
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).
Ü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:
Eine Zelle hat 3 Nachbarn unter den vorherigen Zellen, wenn:
Implementierung von Zellnachbarn
Der Index der aktuellen Zelle (beginnend mit1 ) ist gespeichert in ich . Die Liste der Nachbarn einer Zellen ist gespeichert in A [ n ] .
Aus undurchsichtigen Golfgründen berechnen wir zunächst die entgegengesetzten Offsets der Nachbarn. Zum Beispiel,1 meint - 1 , was die vorherige Zelle bedeutet .
Im obigen Code:
Wir verarbeiten dann einek in Indizes (i - k ) und verschieben Sie die aktuelle Zelle als neuen Nachbarn für alle Nachbarzellen, um die Nachbarschaftssymmetrie zu erzwingen.
map()
Schleife, die die Offsets konvertiertDen 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 berechnenk der Sequenz mit einer anderen rekursiven Hilfsfunktion.
Der Wert einer Zellen ist gespeichert in v [ n ] .
quelle
Sauber ,
284279272262 BytesProbieren 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:
Von dort aus ist das Bestimmen der Adjazenz trivial und tritt ein, wenn einer der folgenden Zustände vorliegt:
x1 == x2
undabs(y1-y2) == 1
y1 == y2
undabs(x1-x2) == 1
y1 == y2 - 1
undx2 == x1 - 1
y1 == y2 + 1
undx2 == x1 + 1
x1 == x2
undy1 == y2
Punktgenerierung
Beachten Sie, dass beim Durchqueren des Sechsecks in einer Spirale die Unterschiede für jede Schicht erneut auftreten
n
:n
Schritte von(1,0)
n-1
Schritte von(1,-1)
n
Schritte von(0,-1)
n
Schritte von(-1,0)
n
Schritte von(-1,1)
n
Schritte von(0,1)
Dadurch werden die Punkte in der richtigen Reihenfolge generiert, indem die Präfixsummen dieser Reihenfolge verwendet werden:
Bring es zusammen
Der Code, der tatsächlich die Sequenz aus der Frage findet, lautet einfach:
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:j
(i,j)
an deni
angrenztp
(p,q)
bei dem der Wertq
gleich istv
(u,v)
wou
ist zum aktuellen Punkt benachbartquelle