Gambar di atas menampilkan kisi heksagon segi enam. Setiap sel di grid diberi indeks, mulai dari pusat dan berputar berlawanan seperti yang ditunjukkan. Perhatikan bahwa kisi akan berlanjut tanpa batas - gambar di atas hanyalah bagian pertama. Segi enam berikutnya akan berdekatan dengan 60 dan 37.
Tugas Anda adalah menentukan apakah dua sel yang diberikan pada kisi ini berdekatan.
Tulis sebuah program atau fungsi yang, diberi dua indeks sel, mencetak / mengembalikan nilai kebenaran jika dua sel berdekatan, dan nilai palsu jika tidak.
Jika tidak dibatasi oleh alasan praktis, kode Anda secara teoritis harus berfungsi untuk input ukuran apa pun.
Kasus uji kebenaran:
0, 1
7, 18
8, 22
24, 45
40, 64
64, 65
Kasus uji Falsey:
6, 57
29, 90
21, 38
38, 60
40, 63
41, 39
40, 40
Ini adalah kode-golf sehingga jawaban tersingkat dalam byte menang. Penjelasan, bahkan untuk bahasa non-esoterik, dianjurkan.
sumber
MATL ,
4745444341 byteCobalah online! Atau verifikasi semua kasus uji .
Sebagai bonus, kode ini menghasilkan spiral heksagonal yang melacak posisi pusat sel, yang dapat dilihat secara grafis di MATL Online dengan memodifikasi bagian terakhir dari kode.
Penjelasan
Gagasan umum Kode pertama kali membangun spiral heksagonal yang cukup besar dengan unit step. Spiral didefinisikan sebagai vektor bilangan kompleks yang mewakili posisi pusat sel. Pengindeksan ke vektor itu dengan angka-angka input dan menghitung perbedaan absolut memberi jarak antara dua sel yang ditunjukkan. Sel berdekatan jika dan hanya jika hasilnya 1. Namun, karena ketidaktepatan titik apung, pembulatan diperlukan sebelum membandingkan dengan 1.
Membangun spiral Spiral akan memiliki jumlah "lapisan" yang sama dengan jumlah dari dua input. Ini (jauh) lebih besar dari yang diperlukan, dan memastikan bahwa sel-sel input akan hadir dalam spiral.
Untuk membangun spiral, bilangan kompleks j 2/3 (di mana j adalah unit imajiner) pertama kali dihitung. Menaikkan ini ke eksponen 1 hingga 6 memberikan satu set dasar perpindahan, sehingga mengikuti perpindahan itu agar dapat melacak hexagon. Heksagon ini akan membentuk lapisan spiral paling dalam, kecuali bahwa itu akan "tertutup". Sebenarnya, kami ingin hexagon itu "tumbuh" pada langkah terakhir dan kemudian kami melacak hexagon yang lebih besar, dengan dua kali lebih banyak poin (disejajarkan dalam kelompok dua), untuk membentuk lapisan spiral berikutnya; lihat ilustrasi di sini . Lapisan berikutnya akan memiliki tiga poin sebanyak poin pertama (dalam kelompok tiga); lihat di sini .
Untuk melakukan ini, perpindahan kelima dari perangkat dasar (yang menunjuk ke arah tenggara) dipilih sebagai langkah "tumbuh". Lapisan k dimulai dengan langkah itu, diikuti oleh lima langkah dasar pertama yang diulang k kali, diikuti oleh langkah keenam (arah timur) diulang k −1 kali. Mudah-mudahan ini menjadi lebih jelas dengan melihat dua angka yang terhubung di atas.
Vektor yang dihasilkan, termasuk semua lapisan, mewakili perpindahan kompleks yang akan melacak spiral. Jumlah kumulatif memberikan koordinat aktual dari pusat sel.
Terakhir, sel awal, yang terletak di 0, melekat pada ujung vektor ini. Ini karena MATL menggunakan pengindeksan berbasis 1 modular, dan indeks 0 merujuk pada entri terakhir array.
Menguji kedekatan Dua sel yang diberikan oleh nomor input dipilih, koordinatnya dikurangi, dan nilai absolutnya dibulatkan dan dibandingkan dengan 1.
Kode yang dikomentari
sumber
05AB1E (warisan) ,
302927 byteCobalah online!
Penjelasan kode:
Penjelasan matematika:
Saya "terbuang" sekitar 5 jam membuat golf ini. Singkatnya saya mulai membuat grafik input 2d, dan menggambar di
X
mana mereka berdekatan satu sama lain. Kemudian saya menemukan sebuah pola. Saya mencarinya di OEIS dan bingo! Saya menemukan urutan itu dan saya menggunakan formula yang diberikan di situs web.sumber
C (gcc) ,
175173 byteTerimakasih untuk Peter Taylor untuk menangkap bug.
Berkat ceilingcat untuk -2 byte. Itu ~ operator terus menjadi blindspot utama saya.
Cobalah online!
Pendekatan ini difokuskan pada menemukan baris dan kolom dari dua sel dan membandingkannya; tetangga tidak dapat memiliki koordinat yang sesuai berbeda lebih dari 1. Bergerak dari pusat ke luar, kami mengamati bahwa setiap lapisan memiliki 6 sel lebih banyak dari sebelumnya. Ini berarti bahwa "indeks" tertinggi di setiap lapisan L adalah pada bentuk 6 * (L * (L - 1) * (L - 2) ...), atau C = 6 * (L 2 + L) / 2 , di mana C adalah nomor sel "global". Mengacak-acak, kami mendapatkan L 2 + L - C / 3 = 0, yang memberikan kilas balik matematika sekolah menengah. Dari itu, kita mendapatkan formula ceil (sqrt (1/4 + C / 3) + 0,5). Memasukkan indeks sel global ke dalamnya, kami menerima lapisan mana sel masuk
Karena sel pertama di setiap lapisan secara alami lebih tinggi dari yang tertinggi dari lapisan sebelumnya, kami menemukan L start = (6 * (L - 1) 2 + (L - 1)) / 2, yang disederhanakan menjadi 3 * (L 2 - L). Dari yang kita dapatkan indeks lapisan L index = C - L start .
Selanjutnya, kita melihat bahwa setiap lapisan terdiri dari enam bagian, masing-masing panjang L. Mulai dari timur laut dan berlawanan arah jarum jam, kita melihat bahwa untuk dua bagian pertama (1 <= L indeks <= 2 * L) , kita mendapatkan kolom dari L - L indeks . Bagian selanjutnya L * 2 <L index <= L * 3 memiliki semua sel yang berbagi satu kolom -L. Dua bagian berikutnya adalah L * 3 <L indeks <= L * 5 dengan kolomnya sesuai dengan indeks L - L * 4. Dan terakhir, bagian keenam semuanya memiliki sel pada kolom L. Kita dapat menggeser batas atas satu langkah untuk menyimpan beberapa byte dalam kode.
Jadi, bagaimana dengan baris? Untuk menggunakan kembali kode, kita membalikkan kisi sehingga sel 44 lurus ke atas. Kemudian kita menjalankan logika yang sama dengan kolom tetapi memanggil hasil "baris" kali ini. Tentu saja, alih-alih benar-benar memutar grid, kita hanya berjalan 1/6 putaran di sekitarnya.
sumber
Python 3, 150 byte
Solusi saya pada dasarnya mengikuti garis pemikiran yang sama dengan Luis Mendo di atas. Jika ditulis lebih mudah dibaca, kode ini cukup jelas:
h
melakukan hal berikut:i
adalah nomor dering.l
adalah gabungan dari 6 daftar len (i) dikalikan step-vector, di mana step-vector adalah 1j ** (2/3) untuk suatu daya. Rentang ini tidak dimulai pada 0 tetapi pada 4, yang menyebabkan rotasi seluruh kisi. Ini memungkinkan saya untuk melakukan:l[0]+=1
pada baris 6, yang merupakan langkah dari satu cincin ke cincin berikutnya.L+=l
merangkai daftar lengkap dan daftar-dering.h(0,0)
atau h (0,1) dijaga secara implisit, karena jumlah daftar kosong adalah nol. Jika saya bisa yakin bahwaa<b
, yaitu argumen akan datang dalam rangka meningkatkan, saya bisa mencukur habis lagi 14 byte dengan menggantiL[min(a,b):max(a,b)]
denganL[a:b]
, tapi sayangnya!PS: Saya tidak tahu ini adalah tantangan lama, itu muncul di atas beberapa hari yang lalu, dan terus mengomel saya sejak :)
sumber
Mathematica,
111105104 bytePenjelasan:
r=Floor[(1+Sqrt[(4#-1)/3])/2]&
mendefinisikan fungsir
yang mengambil input#
dan menghitung jarak (dalam jumlah sel) ke sel 0. Ia melakukan ini dengan mengeksploitasi pola dalam sel terakhir dari setiap jarak / dering: 0 = 3 (0 ^ 2 + 0), 6 = 3 (1 ^ 2 + 1), 18 = 3 (2 ^ 2 + 2), 36 = 3 (3 ^ 2 + 3), ... dan membalikkan rumus untuk pola itu. Perhatikan bahwa untuk sel 0, sebenarnya dibutuhkan lantai (1/2) + i * (sqrt (3) / 6), yang menghitung komponen-bijaksana untuk mendapatkan 0 + 0 * i = 0.Dengan
r
didefinisikan,r@#
adalah cincin untuk sel#
(di dalam definisi fungsi lain).#+3r@#-3(r@#)^2&
tidak muncul dalam kode persis, tetapi dibutuhkan jumlah sel dan kurangi jumlah sel tertinggi di cincin dalam berikutnya, sehingga memberikan jawaban untuk pertanyaan "sel dari cincin mana saat ini?" Misalnya, sel 9 adalah sel ke-3 dari cincin 2, demikianr[9]
juga output 2 dan#+3r@#-3(r@#)^2&[9]
akan menghasilkan 3.Apa yang dapat kita lakukan dengan fungsi di atas adalah menggunakannya untuk menemukan sudut kutub , sudut berlawanan arah jarum jam dari sinar "sel 0, sel 17, sel 58" ke sel yang dimaksud. Sel terakhir dari setiap cincin selalu pada sudut Pi / 6, dan kami mengelilingi sebuah cincin dalam penambahan Pi / (3 * ring_number). Jadi, secara teori, kita perlu menghitung sesuatu seperti Pi / 6 + (which_cell_of_the_current_ring) * Pi / (3 * ring_number). Namun, rotasi gambar tidak memengaruhi apa pun, sehingga kami dapat membuang bagian Pi / 6 (untuk menghemat 6 byte). Menggabungkan ini dengan formula sebelumnya dan menyederhanakan, kami dapatkan
Pi(#/(3r@#)+1-r@#)&
Sayangnya, ini tidak terdefinisi untuk sel 0 karena nomor cincinnya adalah 0, jadi kita perlu menyiasatinya. Solusi alami akan seperti itu
t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&
. Tetapi karena kita tidak peduli dengan sudut untuk sel 0 dan karenar@#
diulang, kita sebenarnya dapat menyimpan byte di sinit=Limit[Pi(#/(3x)+1-x),x->r@#]&
Sekarang kita memiliki nomor cincin dan sudut, kita dapat menemukan posisi sel (tengah) sehingga kita dapat menguji kedekatan. Menemukan posisi yang sebenarnya mengganggu karena cincin itu heksagonal, tetapi kita bisa menganggap cincin itu lingkaran sempurna sehingga kita memperlakukan nomor cincin sebagai jarak ke pusat sel 0. Ini tidak akan menjadi masalah karena perkiraannya cukup dekat. Dengan menggunakan bentuk kutub dari bilangan kompleks , kita dapat mewakili posisi perkiraan ini di bidang kompleks dengan fungsi sederhana:
p = r@#*Exp[I*t@#] &;
Jarak antara dua bilangan kompleks pada bidang kompleks diberikan oleh nilai absolut dari selisihnya, dan kemudian kita dapat membulatkan hasilnya untuk menangani kesalahan apa pun dari perkiraan, dan memeriksa apakah ini sama dengan 1. Fungsi yang akhirnya apakah karya ini tidak memiliki nama, tetapi ada
Round@Abs[p@#-p@#2]==1&
.Anda dapat mencobanya secara online di kotak pasir Wolfram Cloud dengan menempelkan kode seperti berikut ini dan mengeklik Gear -> "Evaluate cell" atau menekan Shift + Enter atau numpad Enter:
Atau untuk semua kasus uji:
sumber