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) != 1ponieważ wtedy 3i 1będą przylegać w dwóch miejscach.
• a(11) != 2ponieważ wtedy 3i 2będą przylegać w dwóch miejscach.
• a(11) != 3ponieważ wtedy 3przylegałyby do siebie.
• a(11) != 4ponieważ wtedy 3i 4bę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.

JavaScript (ES6),  267 .. 206  199 bajtów

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

Wypró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:

• to pierwsza komórka boczna nowej warstwy (jak 8 )
• lub jest to komórka narożna, ale nie ostatnia warstwa (jak 9 )

Komórka ma 3 sąsiadów spośród poprzednich komórek, jeśli:

• to komórka boczna, ale nie pierwsza z warstwy (jak 10 )
• lub jest to ostatnia komórka narożna bieżącej warstwy (np. 19 )

Realizacja sąsiadów komórek

$1$$i$$n$$A[n]$

For obscure golfing reasons, we first compute the opposite offsets of the neighbors. For instance, $1$ means $-1$, which means the previous cell.

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

W powyższym kodzie:

• $L$$1$
• $j$$1$$6\times L$
• $d$

map()$k$$i-k$

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

Znajdowanie następnego terminu w sekwencji

$k$

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

Czysty , 284 279 272 262 bajtów

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

Wypró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:

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

Stamtąd określenie przylegania jest banalne i występuje, gdy:

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

Generowanie punktów

Zauważ, że podczas przemierzania sześciokąta po spirali różnice powtarzają się dla każdej warstwy n:

1. n kroki z (1,0)
2. n-1 kroki z (1,-1)
3. n kroki z (0,-1)
4. n kroki z (-1,0)
5. n kroki z (-1,1)
6. n kroki z (0,1)

To generuje punkty we właściwej kolejności, biorąc sumy prefiksów tej sekwencji:

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

Łącząc to razem

Kod, który faktycznie znajduje sekwencję z pytania, to po prostu:

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

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:

• Ignorowanie liczb naturalnych, które są równe dowolnemu j
• Do każdego (i,j)miejsca iprzylegap
• Dla każdego, (p,q)gdzie wartość qjest równav
• Dla każdego (u,v)miejsca usąsiaduje z bieżącym punktem