Urutan spiral

29

Latar Belakang

Urutan OEIS A272573 menggambarkan spiral pada kisi heksagonal sebagai berikut:

Mulai spiral angka pada ubin heksagonal, dengan heksagon awal sebagai a (1) = 1. a (n) adalah bilangan bulat positif terkecil yang tidak sama dengan atau sebelumnya berdekatan dengan tetangganya.

Urutannya dimulai

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

Berikut ilustrasi pola spiral: masukkan deskripsi gambar di sini

  • a(11) != 1karena itu 3dan 1akan berdekatan di dua tempat.
  • a(11) != 2karena itu 3dan 2akan berdekatan di dua tempat.
  • a(11) != 3karena dengan begitu 3akan berbatasan dengan dirinya sendiri.
  • a(11) != 4karena itu 3dan 4akan berdekatan di dua tempat.
  • Oleh karena itu a(11) = 5.

Tantangan

Tantangannya adalah menulis program yang menghitung A272573 . Ini , jadi kode terpendek menang.

Peter Kagey
sumber
Saya tidak dapat melihat gambar karena diblokir di sini, jadi mungkin saya kehilangan sesuatu, tetapi contoh Anda menunjukkan a (11) = 4, tetapi dalam daftar urutan Anda a (11) adalah 5.
Geobits
Hanya kesalahan — terima kasih sudah menangkapnya.
Peter Kagey
7
Urutan OEIS ini diajukan sendiri, tampaknya. Bagus. :)
Arnauld
berapa batas untuk n? apakah ada batasan waktu?
Setop
5
Menunggu jawaban Hexagony ...
Jonathan Allan

Jawaban:

23

JavaScript (ES6),  267 .. 206  199 byte

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

Cobalah online!

Bagaimana?

Definisi

Secara konvensional, kita akan menyebut sel sudut sebagai sel yang hanya memiliki satu sisi yang sama dengan lapisan spiral sebelumnya dan sel sisi memiliki sel yang memiliki dua sisi yang sama dengan lapisan sebelumnya. Seperti yang disarankan oleh Ourous, kita juga dapat menganggap mereka sebagai sel urutan-1 dan sel-2 pesanan.

Sel sudut ditunjukkan dengan warna kuning di bawah ini. Semua sel lain adalah sel samping (kecuali sel tengah yang merupakan kasus khusus).

jenis sel

Tentang tetangga sel

Kami tidak benar-benar perlu melacak koordinat sel di grid. Satu-satunya hal yang perlu kita ketahui adalah daftar sel tetangga untuk setiap sel dalam spiral pada waktu tertentu.

Dalam diagram berikut, tetangga di lapisan sebelumnya ditampilkan dalam warna terang dan tetangga tambahan di lapisan saat ini dalam warna lebih gelap.

Sebuah sel memiliki 2 tetangga di antara sel-sel sebelumnya jika:

  • ini adalah sel samping pertama dari layer baru (seperti 8 )
  • atau itu adalah sel sudut, tetapi bukan yang terakhir dari lapisan (seperti 9 )

2 tetangga

Sebuah sel memiliki 3 tetangga di antara sel-sel sebelumnya jika:

  • itu adalah sel samping, tetapi bukan yang pertama dari lapisan (seperti 10 )
  • atau itu adalah sel sudut terakhir dari lapisan saat ini (seperti 19 )

3 tetangga

Implementasi tetangga sel

1inA[n]

11

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

Dalam kode di atas:

  • L1
  • j16×L
  • d

map()kik

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

Menemukan istilah urutan selanjutnya

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
sumber
Penjelasan yang bagus. Satu kemungkinan peningkatan: membuat penjelasan di blok kode sepenuhnya terlihat tanpa perlu pengguliran horizontal (tidak masalah untuk kode golf). Melihat di Firefox, ada 5 kolom tersembunyi di blok kode penjelasan pertama, dan 6 kolom tersembunyi di kolom kedua.
trichoplax
@trichoplax Terima kasih atas komentar dan saran Anda. Bisakah Anda menentukan versi Firefox yang Anda gunakan dan di platform mana? Saya selalu mencoba memformat blok penjelasan sehingga tidak diperlukan pengguliran horizontal. Saya menggunakan Firefox 65 / Win10 sekarang dan saya tidak memiliki kolom tersembunyi.
Arnauld
Akan memeriksa versi Firefox ketika saya tiba di rumah, tetapi mungkin karena saya menggunakan Fedora. Akan memeriksa OS lain dan memberi tahu Anda
trichoplax
1
Tampaknya bervariasi menurut OS. Akan mengangkat ini pada MSE ketika saya memiliki kesempatan untuk mengumpulkan beberapa bukti (jika belum)
trichoplax
1
Saya telah mengangkat ini di MSE . Jangan ragu untuk mengedit jika ada yang melihat kombinasi OS / browser lain yang menunjukkan bilah gulir horizontal.
trichoplax
7

Bersih , 284 279 272 262 byte

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

Cobalah online!

Menghasilkan urutan selamanya.

Pemetaan Hexagon

Sebagian besar kode masuk ke pemetaan segi enam unik untuk (x,y)koordinat sehingga ada fungsi tunggal, sederhana untuk menentukan kedekatan yang berlaku untuk semua pemetaan titik.

Poin yang dipetakan terlihat seperti ini:

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

Dari sana, menentukan kedekatan adalah sepele, dan terjadi ketika salah satu dari:

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

Point Generation

Perhatikan bahwa ketika melintasi hexagon dalam spiral, perbedaannya berulang untuk setiap lapisan n:

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

Ini menghasilkan poin dalam urutan yang benar dengan mengambil sejumlah awalan dari urutan ini:

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

Menyatukannya

Kode yang benar-benar menemukan urutan dari pertanyaan itu adalah:

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

Yang pada gilirannya sebagian besar disaring oleh and[r<>j\\(u,v)<-m|c h u,(p,q)<-m|q==v,(i,j)<-m|c p i]

Filter ini mengambil poin dari m(daftar poin yang sudah dipetakan) dengan:

  • Mengabaikan bilangan asli yang sama dengan apa pun j
  • Untuk setiap (i,j)tempat iyang berdekatanp
  • Untuk setiap (p,q)tempat nilainya qsama denganv
  • Untuk setiap (u,v)tempat uyang berbatasan dengan titik saat ini
Suram
sumber