tło
Sekwencja OEIS A272573 opisuje spiralę na sześciokątnej siatce w następujący sposób:
Rozpocznij spiralę liczb na sześciokątnym kafelku, z początkowym sześciokątem jako a (1) = 1. a (n) jest najmniejszą liczbą całkowitą dodatnią, która nie jest równa sąsiednim sąsiadom.
Sekwencja się zaczyna
1, 2, 3, 4, 5, 6, 7, 4, 6, 8, 5, 9, 8, 10, 2, 11, ...
Oto ilustracja spiralnego wzoru:
a(11) != 1
ponieważ wtedy3
i1
będą przylegać w dwóch miejscach.a(11) != 2
ponieważ wtedy3
i2
będą przylegać w dwóch miejscach.a(11) != 3
ponieważ wtedy3
przylegałyby do siebie.a(11) != 4
ponieważ wtedy3
i4
będą przylegać w dwóch miejscach.- W związku z tym
a(11) = 5
.
Wyzwanie
Wyzwanie polega na napisaniu programu, który oblicza A272573 . To jest golf golfowy , więc wygrywa najkrótszy kod.
code-golf
sequence
hexagonal-grid
Peter Kagey
źródło
źródło
Odpowiedzi:
JavaScript (ES6),
267 .. 206199 bajtówWypróbuj online!
W jaki sposób?
Definicje
Umownie nazywamy komórkę narożną komórką, która ma tylko jedną krawędź wspólną z poprzednią warstwą spirali, a komórka boczna komórką, która ma dwie krawędzie wspólne z poprzednią warstwą. Jak sugeruje Ourous, możemy również myśleć o nich odpowiednio o komórkach rzędu 1 i komórkach rzędu 2.
Komórki narożne pokazano poniżej na żółto. Wszystkie pozostałe komórki są komórkami bocznymi (z wyjątkiem komórki środkowej, która jest przypadkiem specjalnym).
O sąsiadach komórek
Tak naprawdę nie musimy śledzić współrzędnych komórek na siatce. Jedyne, co musimy wiedzieć, to lista sąsiednich komórek dla każdej komórki w spirali w danym momencie.
Na poniższych schematach sąsiedzi w poprzedniej warstwie są pokazani w jasnym odcieniu, a inni sąsiedzi w bieżącej warstwie w ciemniejszym odcieniu.
Komórka ma 2 sąsiadów spośród poprzednich komórek, jeśli:
Komórka ma 3 sąsiadów spośród poprzednich komórek, jeśli:
Realizacja sąsiadów komórek
For obscure golfing reasons, we first compute the opposite offsets of the neighbors. For instance,1 means - 1 , which means the previous cell.
W powyższym kodzie:
map()
Znajdowanie następnego terminu w sekwencji
źródło
Czysty ,
284279272262 bajtówWypróbuj online!
Generuje sekwencję na zawsze.
Mapowanie sześciokątne
Większość kodu
(x,y)
służy do mapowania sześciokątów unikatowo na współrzędne, dzięki czemu istnieje jedna, prosta funkcja określająca przyleganie, które obowiązuje dla wszystkich mapowań punktów.Mapowane punkty wyglądają następująco:
Stamtąd określenie przylegania jest banalne i występuje, gdy:
x1 == x2
iabs(y1-y2) == 1
y1 == y2
iabs(x1-x2) == 1
y1 == y2 - 1
ix2 == x1 - 1
y1 == y2 + 1
ix2 == x1 + 1
x1 == x2
iy1 == y2
Generowanie punktów
Zauważ, że podczas przemierzania sześciokąta po spirali różnice powtarzają się dla każdej warstwy
n
:n
kroki z(1,0)
n-1
kroki z(1,-1)
n
kroki z(0,-1)
n
kroki z(-1,0)
n
kroki z(-1,1)
n
kroki z(0,1)
To generuje punkty we właściwej kolejności, biorąc sumy prefiksów tej sekwencji:
Łącząc to razem
Kod, który faktycznie znajduje sekwencję z pytania, to po prostu:
Co z kolei jest głównie filtrowane
and[r<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]
Ten filtr pobiera punkty z
m
(listy już zmapowanych punktów) według:j
(i,j)
miejscai
przylegap
(p,q)
gdzie wartośćq
jest równav
(u,v)
miejscau
sąsiaduje z bieżącym punktemźródło