Saatnya untuk tantangan labirin lain, tetapi tidak seperti yang Anda tahu.
Aturan untuk tantangan ini sedikit berbeda dari kebanyakan tantangan labirin. Jenis ubin didefinisikan sebagai berikut:
S
: Lokasi di labirin tempat Anda memulaiE
: Lokasi yang Anda coba tuju0
: Dinding yang tidak bisa Anda lewati+
: Lantai yang bisa Anda lewati
Anda dapat melakukan perjalanan di salah satu dari enam arah: ke kiri, ke kanan, kiri, kanan, kiri bawah, atau kanan bawah.
\ /
-S-
/ \
Labirin tidak terbungkus. Tujuannya adalah untuk menemukan string jalur terpendek untuk didapatkanS
ke E
.
Memasukkan:
Input adalah spasi yang dipisahkan garis seperti labirin yang ditampilkan. Tidak ada spasi tambahan yang akan mengikuti garis.
Keluaran:
Serangkaian R
, L
dan F
di mana
R
memutar Anda ke kanan (searah jarum jam) 60 derajatL
memutar Anda ke kiri (berlawanan arah jarum jam) 60 derajatF
menggerakkan Anda satu ruang ke arah yang Anda tunjuk
Anda mulai menunjuk left-up
Jalur terpendek dihitung oleh panjang string yang dihasilkan, bukan jumlah posisi yang dikunjungi. Program Anda harus mencetak jalur terpendek sebagai solusinya.
Jika labirin tidak dapat dipecahkan, Anda harus menampilkannya Invalid maze!
.
( >>>
adalah output)
0 0 0 0
0 + 0 + 0
0 0 0 + + 0
0 + 0 + 0 + 0
0 0 + + 0 0 + 0
0 0 + 0 + 0 0 + 0
E 0 + 0 0 + + 0
+ + 0 + 0 + 0
0 0 0 0 0 +
+ 0 + + +
0 S 0 0
>>>RFRFFLFLFRFFLFFFLFLFFRFLFLFRFRFRF
+ 0 0 0 0 0 0
0 0 0 0 0 + + 0
0 0 E 0 + 0 0 + 0
0 0 0 0 0 0 0 +
0 + 0 0 + + +
0 0 + + 0 0
S + 0 0 0
>>>Invalid maze!
0 E S
>>>LF
E + 0
0 + + +
0 0 S
+ +
>>>FFLF
E
0 +
0 + +
0 +
S
>>>RFFLFF
0 E + 0 0
0 + 0 0 + +
+ 0 + + + 0
+ 0 + 0 + 0
+ + + 0 S
>>>FFLFLFFRFRFFRFF
E 0 + + 0
0 + 0 + + 0
+ + + 0 + 0
+ 0 0 0 0 0
+ + + + 0
+ 0 S 0
>>>FLFFRFFRFLF
(Perhatikan bahwa beberapa labirin memiliki solusi lain yang panjangnya sama tetapi tidak tercantum di sini)
sumber
Jawaban:
Python 2, 291 byte
Fungsi,,
f
mengambil labirin sebagai daftar baris, dan mengembalikan solusi, jika ada.Penjelasan
Lakukan pencarian luas pertama pada grafik pasangan posisi / arah untuk menemukan jalur terpendek dari
S
keE
.Yang menarik adalah menemukan cara yang ringkas untuk mewakili posisi dan arah pada kisi heksagonal, yang mengakui "loncatan" sederhana (yaitu, bergerak ke arah tertentu) dan rotasi. Sangat menggoda untuk menggunakan bilangan kompleks di sini, untuk mewakili koordinat pada kisi heksagonal "nyata", tetapi ini bukan ide yang bagus untuk sejumlah alasan, yang paling serius adalah kenyataan bahwa kita perlu memasukkan in3 suatu tempat untuk membuatnya bekerja (sin 60 ° = √3 / 2), yang, ketika menggunakan angka floating-point, adalah jalan keluar jika kita membutuhkan presisi absolut (misalnya, untuk melacak keadaan yang telah kita kunjungi;) Anda dapat mencoba menjalankan konsol JavaScript dan mengetik
Math.sqrt(3)*Math.sqrt(3) == 3
dan melihat sendiri.Tapi, kita bisa menggunakan sedikit trik! Alih-alih menggunakan bilangan kompleks, mari kita mendefinisikan bilangan heksagonal dalam nada yang sama, sebagai pasangan bilangan real a + bh , di mana h memainkan peran yang mirip dengan i imajiner ketika berhadapan dengan bilangan kompleks. Sama seperti dengan bilangan kompleks, kita dapat mengaitkan pasangan ( a , b ) dengan titik pada bidang, di mana sumbu nyata menunjuk ke kanan, sumbu imajiner menunjuk 60 ° ke atas, dan keduanya memotong unit segi enam reguler ketika nyata dan bagian imajiner sama dengan 1, masing-masing. Memetakan sistem koordinat ini ke sel-sel labirin sepele.
Tidak seperti i , konstanta h didefinisikan oleh hubungan h 2 = h - 1 (penyelesaian untuk h mungkin mengungkapkan beberapa wawasan.) Dan hanya itu! Bilangan heksagonal dapat ditambahkan dan dikalikan, menggunakan relasi di atas, seperti bilangan kompleks: ( a + bh ) + ( c + dh ) = ( a + c ) + ( b + d ) h ,
dan ( a + bh ) · ( c + dh ) = ( ac - bd) + ( iklan + bc + bd ) h . Operasi-operasi ini memiliki interpretasi geometris yang sama dengan rekan-rekan mereka yang kompleks: penjumlahan adalah penjumlahan vektor, dan perkalian adalah penskalaan dan rotasi. Secara khusus, untuk memutar bilangan heksgonal 60 ° berlawanan arah jarum jam, kami mengalikannya dengan h :
( a + bh ) · h = - b + ( a + b ) h , dan untuk memutar angka yang sama 60 ° searah jarum jam, kami membagi oleh h :
( a + bh ) / h = ( a +bh ) · (1 - h ) = (a + b) - ah . Misalnya, kita dapat mengambil angka heksagonal satuan yang menunjuk ke kanan, 1 = (1, 0), lingkaran penuh, berlawanan arah jarum jam, dengan mengalikannya dengan h enam kali:
(1, 0) · h = (0, 1 ); (0, 1) · h = (-1, 1); (-1, 1) · h = (-1, 0); (-1, 0) · h = (0, -1); (0, -1) · h = (1, -1);
(1, -1) · h = (1, 0).
Program ini menggunakan angka heksagonal dalam mode ini untuk mewakili posisi saat ini di labirin dan arah saat ini, untuk maju dalam arah yang ditentukan, dan untuk memutar arah ke kiri dan ke kanan.
sumber
Hexagony , 2437 byte
Program yang ditunggu-tunggu ada di sini:
Cobalah online!
Versi "Dapat dibaca":
Diuji pada Esoteric IDE: TIO mungkin mengalami time out pada beberapa kasus uji yang lebih besar tetapi semua diverifikasi. Terima kasih banyak kepada Timwi, ini tidak akan mungkin terjadi tanpa IDE.
Ada sedikit ruang kosong, jadi saya mungkin bisa memasukkan ini ke segi enam sisi-panjang (bukan sisi-panjang 29) tapi itu akan menjadi tugas besar jadi saya mungkin tidak akan mencobanya.
Penjelasan Dasar
Klik gambar untuk versi yang lebih besar dan lebih detail.
Fungsi
Catatan: Divisi umumnya benar tetapi kadang-kadang bisa menjadi dugaan kasar.
Kode ini cukup "fungsional" - sebanyak yang dimungkinkan oleh Hexagony. Ada delapan fungsi utama dalam kode ini yang berlabel pada diagram di atas, dinamai dengan angka yang dipanggil (jadi nomor penunjuk instruksi mereka adalah nomor mod 6). Dalam urutan panggilan (kasar), mereka adalah (nama yang dikutip adalah lokasi dalam memori yang akan dijelaskan kemudian):
F
,R
danL
siap untuk pemrosesan utama. Instruksi penunjuk 0 bergerak ke fungsi 0 sementara eksekusi bergerak ke fungsi 1.+
2 gerakan yang pertama kali dicapai. Kembali berfungsi 1.F
. Kembali berfungsi 1.F
,R
atauL
ditambahkan. Kembali berfungsi 1.FFLF
), Lalu menghentikan program.Invalid maze!
dan berakhir.Ingatan
Catatan: Berkat IDE Esoterik lagi untuk diagram
Memori terdiri dari tiga bagian utama:
0
atau tempat yang valid yang diakses lebih banyak bergerak dari yang dibutuhkan untuk keluar dari tempat itu ke arah mana pun.+
yang belum tercapai.-1
s dengan satu-2
di sebelah kiri, memungkinkan penunjuk memori dengan cepat kembali ke area pemrosesan inti.F
,R
,L
sebagai1
,2
,3
masing-masing-1
tepat lalu nilai y naik (meskipun y = 0 diproses sebagai 1 untuk keperluan memisahkan rel dari data referensi)Lokasi memori penting lainnya:
E
disimpan di sini.sumber
Python 3, 466 byte
Mungkin akan berakhir lebih kecil jika saya menggunakan pencarian kedalaman-pertama atau sesuatu. Monstrositas ini menggunakan Dijkstra dan cukup cepat, tetapi sangat panjang.
Kode mendefinisikan fungsi
S
yang mengambil string multiline dengan labirin dan mengembalikan hasilnya.Ini adalah tes kode.
Tidak disatukan
sumber
L,,R
.Groovy, 624 byte. Depan!
Waktu waktu bola bergulir dengan yang besar. Mengambil string multi-line sebagai arg
Q
Versi tidak disatukan:
sumber
C #,
600574 byteProgram lengkap, menerima input dari STDIN, output ke STDOUT.
Sunting: ada bug dalam penanganan bungkus (tidak merusak salah satu kasus uji yang diberikan) yang akan menambahkan 1 byte, jadi saya melakukan sedikit lebih banyak golf untuk mengimbangi.
Dimulai dengan membaca di peta, menambahkan
(
ke setiap baris sehingga tahu di mana itu berakhir, dan dapat kembali dan menambahkan banyak ruang untuk membuat peta persegi panjang, dan dengan deretan ruang di sepanjang sisi kanan (ini menghemat kami melakukan pembungkus cek seperti yang akan dijelaskan di bawah). Ini berfungsi lebar persegi panjang di beberapa titik dalam hal ini, dan memastikan panjang total Peta.Selanjutnya, ini menginisialisasi segalanya untuk Breadth-First-Search. Dua array biggish dibuat, satu untuk menyimpan semua negara yang perlu kita jelajahi dalam pencarian kita, yang lain untuk mencatat rute yang kita ambil untuk sampai ke masing-masing negara. Keadaan awal ditambahkan ke array karena, dengan pointer kepala dan ekor diatur sebelumnya di atas. Semuanya terindeks 1.
Kami kemudian beralih sampai ekor menabrak kepala, atau setidaknya itu tampaknya telah menabrak kepala. Untuk setiap keadaan yang telah kami kunjungi, kami berupaya menambahkan keadaan baru di posisi yang sama dengan kami diputar ke kiri atau ke kanan, dan kemudian ke tempat di mana kami telah bergerak maju. Arah diindeks, dengan arah awal (default ke
0
) sesuai dengan "kiri atas".Ketika kami mencoba untuk mengantri keadaan, itu terikat diperiksa, tetapi tidak membungkus diperiksa, karena kolom ruang di sisi kanan, yang diambil oleh "apakah kita diizinkan berada di sini?" centang (Anda tidak diizinkan berada di spasi). Jika keadaan antri, kami kemudian memeriksa apakah ada di
E
sel, dan jika ya, kami mengatur kepala antrian menjadi minus itu sendiri, yang menyebabkan loop utama keluar, dan memberi tahu baris terakhir program untuk mencetak keluar rute yang sesuai, bukan pesan kegagalan (yang menunjukkan jika kita kehabisan negara untuk memperluas (ekor menabrak kepala)).Seperti kebanyakan Pencarian Grafik saya di situs ini, saya memanfaatkan C # struct, yang standarnya dibandingkan dengan nilai literal.
sumber
Python 2, 703 byte
Tidak sebagus dua versi lainnya, tetapi setidaknya ini berfungsi haha. Set
M
ke labirin.Karena saya tidak punya pengalaman dalam memecahkan labirin, itu hanya berjalan dengan pendekatan brute force, di mana ia akan menemukan semua solusi yang dapat dilakukan yang tidak melibatkan menyeberang kembali dengan sendirinya. Ini menghitung belokan dari yang terpendek, dan kemudian memilih hasil terpendek dari itu.
Versi ungolfed berantakan:
sumber
if heading != required_heading: while heading != required_heading:
denganwhile heading != required_heading: