Spiralna sekwencja

29

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: wprowadź opis zdjęcia tutaj

  • 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 , więc wygrywa najkrótszy kod.

Peter Kagey
źródło
Nie widzę obrazu, ponieważ jest tutaj zablokowany, więc może coś mi brakuje, ale twój przykład pokazuje (11) = 4, ale na twojej liście sekwencji a (11) to 5.
Geobits
To tylko pomyłka - dziękuję, że ją złapałeś.
Peter Kagey,
7
Ta sekwencja OEIS została najwyraźniej przesłana przez ciebie. Miły. :)
Arnauld,
jaki jest limit dla n? czy jest limit czasowy?
Setop,
5
Oczekiwanie na odpowiedź Hexagony ...
Jonathan Allan,

Odpowiedzi:

23

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

typy komórek

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 )

2 sąsiadów

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 )

3 sąsiadów

Realizacja sąsiadów komórek

1inA[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:

  • L1
  • j16×L
  • d

map()kik

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

Znajdowanie następnego terminu w sekwencji

k

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
źródło
Świetne wyjaśnienie. Jedna możliwa poprawa: pełne wyjaśnienie objaśnień w blokach kodu bez potrzeby przewijania w poziomie (nie ma znaczenia dla kodu golfowego). W przeglądarce Firefox znajduje się 5 ukrytych kolumn w pierwszym bloku kodu wyjaśniającego i 6 ukrytych kolumn w drugim.
trichoplax
@trichoplax Dziękujemy za komentarz i sugestie. Czy możesz określić, której wersji Firefox używasz i na jakiej platformie? Zawsze staram się formatować bloki wyjaśnień, aby przewijanie w poziomie nie było potrzebne. Jestem teraz w przeglądarce Firefox 65 / Win10 i nie mam żadnej ukrytej kolumny.
Arnauld
Sprawdzę wersję Firefoksa, kiedy wrócę do domu, ale może to być spowodowane tym, że korzystam z Fedory. Sprawdzi inny system operacyjny i powiadomi Cię
trichoplax
1
Wygląda na to, że różni się w zależności od systemu operacyjnego. Podniosę to na MSE, gdy będę miał okazję zebrać jakieś dowody (jeśli jeszcze tego nie było)
trichoplax
1
Mam poruszył to na MSE . Możesz edytować, jeśli ktoś zobaczy inne kombinacje OS / przeglądarki, które pokazują poziome paski przewijania.
trichoplax
7

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
Obrzydliwe
źródło