Anda berada di ruang bawah tanah satu lantai. Ada harta karun yang dilindungi oleh pintu yang terkunci. Pintu dapat dibuka dengan menemukan kunci yang sesuai. Tujuan Anda adalah menemukan jalan terpendek menuju harta.
Memasukkan
Input akan berupa grid dua dimensi yang mewakili tata letak awal ruang bawah tanah.
###########
#$ # g#
# # ####
###G## #
# ####C#
#c @ #
###########
Ini adalah Anda: @
Ini adalah dinding: #
Ini adalah harta: $
Pintu terkunci adalah huruf kapital: A
... Z
Setiap pintu memiliki kunci huruf kecil yang sesuai: a
...z
- Akan selalu ada satu
@
dan satu$
. - Penjara akan selalu berbentuk persegi panjang.
Tidak dijamin bahwa tepi luar penjara adalah dinding. Ini adalah penjara bawah tanah yang valid:
$ A## @ a
- Tidak dijamin bahwa harta itu bisa dijangkau. Beberapa ruang bawah tanah mungkin tidak dapat dipecahkan.
- Mungkin ada pintu tanpa kunci, dan mungkin ada kunci yang tidak membuka pintu apa pun.
- Tidak akan pernah ada pintu atau kunci duplikat.
Keluaran
Program Anda harus mencetak urutan R
, L
, U
, D
(atau 4 simbol yang berbeda lainnya) untuk mewakili terpendek jalan mungkin untuk harta karun. Di sini, RLUD
singkatan masing-masing, kiri, atas, dan bawah. Jika ada beberapa jalur terpendek, program Anda hanya perlu mencetak salah satunya.
- Anda tidak dapat pindah ke dinding.
- Anda tidak dapat bergerak di luar batas ruang bawah tanah.
- Anda tidak dapat pindah ke pintu tanpa mengambil kuncinya.
- Pindah ke tombol untuk mengambilnya.
- Tidak perlu membuka setiap pintu.
Jika tidak mungkin untuk mencapai harta karun melalui urutan bergerak yang valid, maka program Anda harus berakhir tanpa mencetak apa pun. (Baris baru tambahan dibolehkan.)
Mencetak gol
Ini adalah kode-golf sehingga jawabannya dengan jumlah byte terendah menang.
Uji Kasus
Setiap test case akan memiliki tinggi dan lebar ruang bawah tanah di baris pertama, dan satu jalur yang memungkinkan, dengan jumlah gerakan optimal, di baris terakhir.
1 2
@$
R (1)
3 3
$
#Z#
@ z
RRLUUR (6)
3 5
c#d#$
#C#D
@
UUDDRRUUDDRRUU (14)
7 16
c # b # ###@
### #
A ##### ####
d # e
B ## #####
### C ##
# a DE $
RDDDDDDL (8)
16 37
#####################################
# #ijk #a M ##m## # # R #
# # # # # ####
###J#### ############# ### # P b#
#e N h # ####
########## ########### ###### #
# # # $ # # # ####
# D H # # # Q f#
# EcF # #####A##### ###### ####
# G # #####B##### # #
# K #####C##### ############
# # #
########### # #### ##### ####
# # p # # n # #
# d # @ # o# r #
#################Z###################
UUULLLLLLDDLLLDLLLLLLRRRRRRRRRUUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLLLDDLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU (172)
Tidak mungkin untuk mencapai harta karun di ruang bawah tanah berikut. Untuk kasus uji ini, seharusnya tidak ada output.
1 3
@#$
7 11
#a#j#$#i#f#
# #E#F#c#H#
# #K#D#A#G#
# #
#C#J# #I#B#
#h#d# #L#g#
#l#e#@#b#k#
10 25
#########################
# fgh # # c B b # #
$ # # # # # #
###### # ##H###E## #
# #
# ######### ##e##
Z @ D y # # #
# ######### F C#
# G # Ad#
#########################
Cuplikan berikut dapat digunakan untuk memvalidasi jawaban.
function run() {var dungeonText = document.getElementById("dungeon").value;var dungeonLines = dungeonText.split("\n");var height = dungeonLines.length;var width = dungeonLines[0].length;var dungeon = new Array(height);for (i = 0; i < dungeon.length; i++) {var dungeonLine = dungeonLines[i];if (dungeonLine.length != width) {return error("The dungeon is not rectangular");} dungeon[i] = dungeonLines[i].split("");} var movesText = document.getElementById("moves").value;var moves = movesText.trim().split("");var moveCount = moves.length;var rowAt, colAt;for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == '@') {rowAt = r;colAt = c;}}} var treasure = false;while (moves.length > 0) {var move = moves[0];var row = rowAt,col = colAt;switch (move) {case 'R':col++;break;case 'L':col--;break;case 'U':row--;break;case 'D':row++;break;default:return print(dungeon, moves, "Invalid move");} if (row < 0 || col < 0 || row >= height || col >= width) {return print(dungeon, moves, "Out of bounds");} var target = dungeon[row][col];if (target.match(/[A-Z#]/)) {return print(dungeon, moves, "Path blocked");} if (target.match(/[a-z]/)) {var door = target.toUpperCase();for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == door) {dungeon[r][c] = ' ';}}}} if (target == '$') {treasure = true;} dungeon[row][col] = '@';dungeon[rowAt][colAt] = '.';rowAt = row;colAt = col;moves.shift();} if (treasure) {print(dungeon, moves, "Got the treasure in " + moveCount + " moves!");} else {print(dungeon, moves, "Failed to reach treasure");}} function error(message) {var result = document.getElementById("result");result.innerHTML = message;} function print(dungeon, moves, message) {var output = message + "\n";for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {output += dungeon[r][c];} output += "\n";} for (i = 0; i < moves.length; i++) {output += moves[i];} var result = document.getElementById("result");result.innerHTML = output;}
Dungeon:<br/><textarea id="dungeon" name="dungeon" rows="20" cols="40"></textarea><br/>Moves:<br/><textarea id="moves" name="moves" cols="40"></textarea><br/><button id="run" name="run" onclick="run();">Start</button><br/><br/>Result:<br/><textarea id="result" name="result" rows="20" cols="40" disabled></textarea><br/>
sumber
Jawaban:
Perl,
157152151 byteTermasuk +4 untuk
-p0
(tidak dapat dihitung hanya sebagai perpanjangan dari-e
karena digunakan'
di beberapa tempat)Jalankan dengan labirin di STDIN:
keymaze.pl
:Ganti
\n
dan^H
dengan versi literalnya untuk skor yang diklaim. Membutuhkan sekitar 1 jam dan sedikit kurang dari 2 Gigabytes di mesin saya untuk menyelesaikan labirin besar.sumber
Java 8 -
12821277126812591257 byteIni melewati semua tes. Namun, bagi beberapa dari mereka itu memberikan beberapa hasil yang sedikit berbeda (ketika ada lebih dari satu cara optimal, yang bukan masalah).
Untuk tes ke-4, ini memberikan ini:
Alih-alih ini:
Untuk tes ke-5, ini memberikan ini:
Alih-alih ini:
Versi golf:
Versi tidak disatukan
Fitur:
Mengambil input
Untuk menjalankannya, coba ini:
Atau jika Anda menjalankan versi ungolfed, ganti
G
denganTreasureHunt
.File tersebut harus berisi penjara bawah tanah. Masukan tidak boleh diakhiri dengan umpan baris. Lebih jauh, ia hanya menerima garis-ujung dalam
\n
format. Itu tidak akan bekerja dengan\r\n
atau dengan\r
.Juga, itu tidak memvalidasi atau membersihkan input. Jika input salah bentuk, maka perilaku tidak terdefinisi (cenderung untuk melemparkan pengecualian) Jika file tidak dapat ditemukan, maka pengecualian akan dibuang.
Komentar
Implementasi pertama saya di suatu tempat dekat 1100 byte tidak dapat memecahkan kasus uji 5 dalam waktu yang wajar. Alasan untuk itu adalah karena implementasi saya itu brute-memaksa semua permutasi yang mungkin dari barang koleksi (yaitu kunci dan harta karun) yang dapat diakses (yaitu tidak terkunci di ruang yang tidak dapat diakses).
Dalam kasus terburuk, dengan semua 26 kunci dan harta karun, ini akan menjadi 27! = 10.888.869.450.418.352.160.768.000.000 permutasi berbeda.
OP tidak menentukan bahwa jawabannya haruslah sesuatu yang dijalankan pada waktu yang wajar. Namun, saya menganggap bahwa ini adalah celah yang tidak ingin saya manfaatkan. Jadi, saya memutuskan untuk membuatnya berjalan pada waktu yang dapat diterima untuk semua kasus uji. Untuk mencapai itu, program saya yang telah direvisi menampilkan pemangkasan di jalur pencarian yang terbukti lebih buruk daripada beberapa solusi yang sudah tahu. Lebih lanjut, ini juga melakukan cache subsolusi (yaitu pemrograman dinamis) untuk menghindari penghitungan ulang banyak ruang bawah tanah yang identik yang mungkin muncul. Dengan itu, ia mampu menyelesaikan test case ke-5 hanya dalam satu menit di komputer saya.
Solusinya adalah rekursif. Idenya adalah pertama-tama untuk membawa petualang ke beberapa item (kunci atau harta karun). Dalam kasus kunci, setelah petualang mencapainya, penjara bawah tanah yang sama baru dihasilkan dengan kunci dan pintu dihapus dan petualang pindah ke tempat kunci itu. Dengan itu, ruang bawah tanah yang dihasilkan lebih sederhana diselesaikan secara rekursif sampai titik ketika harta karun tercapai atau algoritma menyimpulkan bahwa tidak ada barang yang dapat dijangkau. Urutan barang yang akan dikunjungi dibuat dengan paksa dengan pemangkasan dan caching seperti dijelaskan di atas.
Penemuan jalur antara petualang dan barang-barang dibuat dengan algoritma yang menyerupai penimbunan banjir dan Dijkstra.
Akhirnya, saya menduga bahwa masalah ini adalah NP-lengkap (baik, versi umum itu tanpa batasan pada jumlah pintu / kunci). Jika ini benar, jangan berharap solusi yang secara optimal menyelesaikan ruang bawah tanah yang sangat besar dengan pintu dan kunci miryad dalam waktu yang wajar. Jika jalur sub-optimal diizinkan, maka itu akan mudah ditelusuri dengan beberapa heuristik (hanya pergi ke harta jika mungkin, jika tidak pergi ke kunci terdekat).
sumber