Menggambar segitiga Sierpinski telah dilakukan sampai mati . Ada hal menarik lain yang bisa kita lakukan dengannya. Jika kita menyipit cukup keras pada segitiga, kita dapat melihat segitiga terbalik sebagai simpul dari grafik fraktal. Ayo temukan jalan kita di sekitar grafik itu!
Pertama, mari kita berikan nomor untuk setiap node. Segitiga terbalik terbesar adalah simpul nol, dan kemudian kita turunkan lapis demi lapis (lebar-pertama), dengan menetapkan angka berurutan dalam urutan atas-kiri-kanan:
Klik untuk versi yang lebih besar di mana angka-angka kecil agak kurang buram.
(Tentu saja, pola ini terus tak terhingga di dalam segitiga biru.) Cara lain untuk menentukan penomoran adalah bahwa simpul pusat memiliki indeks 0
, dan anak-anak dari simpul i
(segitiga yang berdekatan dari-kecil selanjutnya skala) memiliki indeks 3i+1
, 3i+2
dan 3i+3
.
Bagaimana kita bergerak di sekitar grafik ini? Ada hingga enam langkah alami yang bisa diambil dari setiap segitiga:
- Satu selalu dapat bergerak melalui titik tengah dari salah satu tepi ke salah satu dari tiga anak dari simpul saat ini. Kami akan menunjuk gerakan ini sebagai
N
,SW
danSE
. Misalnya jika kita saat ini simpul2
, ini akan menyebabkan node7
,8
,9
, masing-masing. Bergerak lain melalui tepi (ke keturunan tidak langsung) dilarang. - Satu juga dapat bergerak melalui salah satu dari tiga sudut, asalkan tidak menyentuh tepi segitiga, baik ke induk langsung atau salah satu dari dua leluhur tidak langsung. Kami akan menunjuk gerakan ini sebagai
S
,NE
danNW
. Misal jika kita saat ini di node31
,S
akan mengarah ke10
,NE
akan menjadi tidak valid danNW
akan mengarah ke0
.
Tantangan
Diberi dua bilangan bulat non-negatif x
dan y
, cari jalur terpendek dari x
ke y
, hanya menggunakan enam gerakan yang dijelaskan di atas. Jika ada beberapa jalur terpendek, output salah satunya.
Perhatikan bahwa kode Anda harus berfungsi lebih dari 5 level yang digambarkan dalam diagram di atas. Anda mungkin menganggap itu x, y < 1743392200
. Ini memastikan bahwa mereka masuk di dalam integer bertanda 32-bit. Perhatikan bahwa ini sesuai dengan 20 level pohon.
Kode Anda harus memproses setiap input yang valid dalam waktu kurang dari 5 detik . Walaupun ini mengesampingkan pencarian brute force pertama, itu harus menjadi kendala yang cukup longgar - implementasi referensi saya menangani input sewenang-wenang untuk kedalaman 1000 dalam setengah detik (itu ~ angka 480-digit untuk node).
Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).
Output harus datar, daftar ambigu dari string N
, S
, NE
, NW
, SE
, SW
, menggunakan pemisah wajar (spasi, linefeeds, koma, ","
...).
Aturan standar kode-golf berlaku.
Uji Kasus
Beberapa kasus uji pertama dapat dikerjakan dengan tangan menggunakan diagram di atas. Yang lain memastikan bahwa jawabannya cukup efisien. Bagi mereka, mungkin ada solusi lain dengan panjang yang sama yang tidak terdaftar.
0 40 => N N N N
66 67 => S SW N N N
30 2 => NW NW -or- NE SW
93 2 => NE SW
120 61 => NW NW NW NW N SE SW N
1493682877 0 => S S NW NW
0 368460408 => SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130 1242824 => NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
520174 1675046339 => NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
312602548 940907702 => NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873 => NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
547211529 1386725128 => S S S NE NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199 => NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE
sumber
APL (Dyalog Unicode) ,
144132129118133132130124117 byte SBCSTerima kasih banyak kepada Ven dan ngn atas bantuan mereka dalam bermain golf di The APL Orchard , tempat yang bagus untuk belajar bahasa APL.
⎕IO←0
. Saran golf diterima.Sunting: -12 bytes berkat Ven dan ngn dengan mengubah cara
n
didefinisikan dan beralih dari pengindeksan 1 ke pengindeksan. -3 karena memperbaiki bug di mana tidak semuanya dialihkan ke pengindeksan 0. -11 byte karena mengubah caraP
danQ
didefinisikan. +15 byte karena memperbaiki masalah di mana algoritma saya salah dengan banyak terima kasih kepada ngn untuk bantuan dengan mencaris[⊃⍋|M-s]
bagian. -2 byte dari mengatur ulang metode untuk menemukan jalur backtracking dan +1 byte untuk memperbaiki bug. -2 byte terima kasih kepada Adám untuk mengatur ulang definisiI
. -6 byte terima kasih kepada Ngn dari mengatur ulang definisi'S' 'NE' 'NW' 'N' 'SW' 'SE'
dan dari mengatur ulang bagaimanat
didefinisikan (itu bukan lagi variabel yang terpisah). -7 byte berkat ngn dari golf bagaimanas
didefinisikan.Cobalah online!
Penjelasan bug dalam algoritma
Masalah mendasarnya adalah saya pergi berpikir bahwa jalan terpendek melewati langsung leluhur bersama, dan pada kenyataannya, tidak bisa melalui leluhur leluhur yang sama. Ini tidak benar karena contoh berikut akan menunjukkan.
Dari 66 hingga 5
Dari 299792458 hingga 45687
Penjelasan kode
Solusi alternatif menggunakan Dyalog Extended dan dfns
Jika kita menggunakan
⎕CY 'dfns'
'sadic
fungsi, menerapkan kami bijective dasar-n penomoran (yang merupakan inspirasi bagi saya gunakan versi) untuk byte jauh lebih sedikit. Beralih ke Dyalog Extended juga menghemat banyak byte dan jadi di sinilah kita. Terima kasih banyak kepada Adám atas bantuannya dalam bermain golf ini. Selamat datang saran bermain golf!Edit: -8 byte karena mengubah cara
P
danQ
didefinisikan. -14 byte karena beralih ke Dyalog Extended. -2 karena menggunakan program lengkap untuk menghapus tanda kurung dfn{}
. +17 byte karena memperbaiki masalah di mana algoritma saya salah dengan banyak terima kasih kepada ngn untuk bantuan dengan mencaris[⊃⍋|M-s]
bagian. +1 byte untuk memperbaiki bug. -2 byte terima kasih kepada Adám dari mengatur ulang definisiI
dan -1 byte dari mengingat untuk meletakkan golf saya di kedua solusi. -3 byte berkat ngn dengan mengatur ulang generasi arah mata angin, +1 byte dari mengoreksi golf buggy, dan -3 byte berkat ngn dengan mengatur ulang carat
didefinisikan (tidak lagi merupakan variabel terpisah). -7 byte berkat ngn dengan mengatur ulang caras
didefinisikan.APL (Dyalog Extended) ,
12311510199116117114109102 byteCobalah online!
sumber