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:
a(11) != 1
karena itu3
dan1
akan berdekatan di dua tempat.a(11) != 2
karena itu3
dan2
akan berdekatan di dua tempat.a(11) != 3
karena dengan begitu3
akan berbatasan dengan dirinya sendiri.a(11) != 4
karena itu3
dan4
akan berdekatan di dua tempat.- Oleh karena itu
a(11) = 5
.
Tantangan
Tantangannya adalah menulis program yang menghitung A272573 . Ini kode-golf , jadi kode terpendek menang.
code-golf
sequence
hexagonal-grid
Peter Kagey
sumber
sumber
Jawaban:
JavaScript (ES6),
267 .. 206199 byteCobalah 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).
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:
Sebuah sel memiliki 3 tetangga di antara sel-sel sebelumnya jika:
Implementasi tetangga sel
Dalam kode di atas:
map()
Menemukan istilah urutan selanjutnya
sumber
Bersih ,
284279272262 byteCobalah 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:
Dari sana, menentukan kedekatan adalah sepele, dan terjadi ketika salah satu dari:
x1 == x2
danabs(y1-y2) == 1
y1 == y2
danabs(x1-x2) == 1
y1 == y2 - 1
danx2 == x1 - 1
y1 == y2 + 1
danx2 == x1 + 1
x1 == x2
dany1 == y2
Point Generation
Perhatikan bahwa ketika melintasi hexagon dalam spiral, perbedaannya berulang untuk setiap lapisan
n
:n
langkah-langkah(1,0)
n-1
langkah-langkah(1,-1)
n
langkah-langkah(0,-1)
n
langkah-langkah(-1,0)
n
langkah-langkah(-1,1)
n
langkah-langkah(0,1)
Ini menghasilkan poin dalam urutan yang benar dengan mengambil sejumlah awalan dari urutan ini:
Menyatukannya
Kode yang benar-benar menemukan urutan dari pertanyaan itu adalah:
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:j
(i,j)
tempati
yang berdekatanp
(p,q)
tempat nilainyaq
sama denganv
(u,v)
tempatu
yang berbatasan dengan titik saat inisumber