Kamu adalah tikus. Teman-teman mouse Anda semuanya telah ditangkap, dan tidak sadar dan terjebak dalam labirin yang hanya memiliki satu pintu masuk / keluar. Anda memiliki peta labirin yang sempurna, sehingga Anda dapat merencanakan solusi untuk bergegas masuk dan membawa semuanya ke tempat yang aman. Namun, labirin dijaga dengan sistem keamanan yang akan memicu peringatan jika ambang batas 1000
tercapai, menyebabkan Anda ditangkap dan gagal dalam misi penyelamatan Anda.
Dari penyelidikan sebelumnya pada labirin, setiap kotak yang Anda langkahkan (yaitu, setiap gerakan horizontal atau vertikal - tikus tidak dapat bergerak secara diagonal ) menambah 1
penghitung sistem keamanan. Namun, jika Anda membawa beban (baik blok dinamit atau teman mouse yang tidak sadar), itu malah menambah 2
karena mendeteksi tekanan tambahan. Alur masuk / keluar tidak memiliki sistem keamanan ini, jadi tidak menambah konter.
Anda memiliki persediaan dinamit yang tidak terbatas yang telah Anda bawa ke pintu masuk, sehingga Anda dapat meledakkan semua dinding untuk membebaskan teman-teman Anda. Tetapi Anda harus berhati-hati dengan melakukannya, karena setiap ledakan menambah 50
konter dari tekanan concussive. Selain itu, Anda hanya dapat membawa satu barang pada satu waktu, baik satu mouse atau satu blok dinamit. Karena setiap blok dinamit hanya dapat meledakkan satu ruang dinding, ini berarti bahwa jika ada beberapa dinding berturut-turut, Anda perlu melakukan perjalanan dengan tangan kosong kembali ke pintu masuk untuk mengambil lebih banyak.
Contoh yang dikerjakan
Misalkan labirin kita terlihat seperti berikut:
######
#M# E#
######
Saya akan gunakan c
untuk konter. Kami mulai di E
ntrance, bergerak satu persegi kiri sambil membawa dinamit c=2
,. Kami meledakkan dinamit untuk meledakkan tembok c=52
,. Kami memindahkan dua kotak ke kiri, dengan tangan kosong, untuk mendapatkan c=54
, dan kami sekarang berdiri di atas kotak mouse. Kami menjemput teman kami, dan memindahkan 3 kotak kembali ke E
xit, tetapi kotak terakhir tidak dihitung karena tidak memiliki sensor, jadi itu hanya 2 kotak dengan sesuatu di punggung kami. Itu berarti bahwa ketika kita mencapai pintu keluar dengan mouse terakhir c=58
, yang kurang dari 1000
, dan karenanya misi berhasil.
Tantangan
Diberikan labirin input, hasilkan apakah Anda, pahlawan mouse, dapat berhasil menyelamatkan semua tikus yang terperangkap dalam batasan yang diuraikan di atas, atau apakah misinya gagal.
Memasukkan
- Labirin 2D dalam format apa pun yang dapat diterima (string multiline, array string, dll.).
- Untuk tantangan ini, saya akan menggunakan
#
untuk dinding interior dan eksterior,M
untuk teman-teman mouse, danE
untuk pintu masuk. - Pintu masuk tidak akan pernah berbatasan langsung dengan dinding interior (akan selalu ada setidaknya satu ruang untuk bergerak bebas).
- Anda dapat mengganti karakter ASCII yang dapat dicetak yang Anda inginkan asalkan konsisten. Ini tidak memungkinkan Anda untuk menggunakan dua simbol yang berbeda untuk dinding interior vs dinding eksterior, asalkan Anda menjaga konsistensi (misalnya, jika Anda memilih untuk menggunakan
@
untuk dinding interior sebaliknya, dan cuti#
untuk eksterior, setiap dinding interior harus@
dan setiap dinding eksterior#
). - Labirin akan selalu dibatasi sepenuhnya oleh dinding, tetapi tidak harus persegi panjang. Jika diinginkan, Anda dapat mengasumsikan bahwa labirin diisi dengan spasi untuk membuat input persegi panjang (opsional).
- Labirin mungkin memiliki bagian yang tidak dapat dijangkau tanpa dinamit.
- Anda tidak dapat mengubah dinding eksterior labirin.
Keluaran
Nilai kebenaran / kepalsuan . Sejujurnya untuk "Ya, mouse dapat menyelamatkan setiap mouse lainnya" atau Falsey untuk "Tidak, sistem alarm akan tersandung."
Aturan
- Program lengkap atau fungsi dapat diterima.
- Celah standar dilarang.
- Ini adalah kode-golf sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.
Contohnya
Contoh yang benar, dipisahkan oleh garis kosong.
#####
#M E#
#####
######
#M# E#
######
########
#E # M#
# # #
# # #
# #
########
#############################
# ## # # #
# M ## M # # #
# ## # M # E #
#M ## # # #
#############################
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMM MM#
#MMMMMMMMMMMME#
###############
Contoh Falsey, dipisahkan oleh garis kosong
#############################
#M ## ## ## #
# M ## M ## ## #
# ## ## M ## E #
#M ## ## ## #
#############################
#############################
########
########
# # #
# M # M#
########
#####
# M #
#####
#####
#####
#####
###################
# # # ## ## # # #
#M#M#M## E ##M#M#M#
# # # ## ## # # #
###################
#######
######
#####
####
# M#
####
###############
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMMM#
#MMMMMMMMMMMME#
###############
sumber
Jawaban:
Perl,
216215 byteTermasuk +2 untuk
-0p
Berikan masukan pada STDIN. Gunakan
%
untuk dinding eksternal,#
untuk dinding internal,0
untuk ruang kosong,8
untuk tikus danr
untuk posisi awal. Seluruh papan harus empuk sehingga membentuk persegi panjang. Anda dapat mengubah dan menjalankan contoh sebagai:dynamite.pl
:Ganti
\xhh
lolos untuk skor yang diklaim.Program tidak dapat secara realistis menangani kasus rumit. Khususnya itu tidak dapat menangani salah satu kasus kegagalan. Ini karena ada terlalu banyak cara yang berbeda untuk meledakkan dinding internal atau mengambil tikus sehingga pencarian menjadi terlalu luas dan menggunakan memori terlalu banyak meskipun itu setidaknya cukup pintar untuk tidak pernah memproses keadaan yang sama beberapa kali. Batas tekanan harus diturunkan ke
100
atau lebih untuk runtime yang lumayan dan penggunaan memori.Penjelasan
Saya menggunakan pola bit karakter untuk mewakili keadaan bidang:
Misalnya pahlawan (
01000000
) yang membawa dinamit (00000001
) harus berada di tempat yang dapat ia jalani (00010000
) dan kami ingin semua nilai dicetak ASCII (00100000
). Mengambil bitwiseor
dari semua bitmasks ini memberi01110001
yang merupakan kode ASCII untukq
. Totalnya menjadi ::Program hanya akan mempertimbangkan pahlawan bergerak ke kanan (rotasi yang dijelaskan nanti akan mengurus arah lainnya). Bitmasks dipilih dengan hati-hati sedemikian rupa sehingga pahlawan selalu diwakili oleh surat dan tempat ia bisa bergerak dengan digit (kecuali pahlawan di rumah membawa korban, tapi sekali lagi ini disengaja sehingga satu-satunya langkah pahlawan adalah untuk menjatuhkan korban). Jadi pahlawan yang bisa bergerak maju dicocokkan dengan
/\pL\d/
. Substring yang cocok harus dimodifikasi sehingga pahlawan dan apa yang dibawanya dihapus dari karakter pertama dan ditambahkan ke karakter kedua, yang dapat dilakukan dengan bitwisexor
dengan nilai yang sama untuk kedua karakter. Nilai xor terdiri dari bit pahlawan (01000000
), bit dinamit (00000001
) dan carry mouse bit (00000100
). Bersama-sama merekaor
melakukannya01000101
yaitu ASCIIE
. Jadi menggerakkan pahlawan menjadi:Pahlawan dapat meledakkan dinding jika dia berdiri tepat di depannya dan membawa dinamit (
q
,s
atauy
). Pahlawan akan kehilangan dinamitnya (xor
dengan00000001
) dan dinding#
akan berubah menjadi sebuah bagian0
(xor dengan00010011
), jadiUntuk menangani arah lain seluruh papan diputar (papan diputar berakhir di
$o
):Selain menggerakkan pahlawan juga memiliki sejumlah pilihan lain yang dapat ia buat:
Ini dilakukan oleh
Papan selesai jika pahlawan di rumah tidak membawa apa-apa (
x
) dan tidak ada lagi korban untuk diselamatkan (tidak2
). Ini dapat dengan mudah diuji menggunakanSetelah papan diselesaikan, saya ingin mengingat keadaan ini dan pada akhirnya mencetaknya. Untuk itu saya membawa bendera "diselesaikan"
$\
dan mencetaknya di akhir program tanpa mencetak$_
, jadiKeadaan yang akan diproses pada tekanan 0 disimpan
@0
, pada tekanan 1 pada@1
dll. Tekanan saat ini disimpan$%
. Menggunakan$n
atau sesuatu seperti itu akan lebih pendek tetapi kode tidak berfungsi jika variabel tidak diinisialisasi ke sesuatu karena autovivification sebaliknya akan berubah$n
menjadi referensi ARRAY. Melompati keadaan pada tekanan tertentu dilakukan menggunakan afor
dan bukanmap
karena denganfor
Anda dapat memperpanjang array saat itu masih diulang dan akan mengambil elemen baru. Ini diperlukan karena rotasi dan pilihan bidang tunggal dari pahlawan terjadi dalam waktu 0 dan berakhir di array tekanan yang sama. Jadi loop untuk tekanan yang diberikan dilakukan olehIni diulang sampai tekanan mencapai 1000 atau solusi ditemukan:
Yang tersisa adalah menambahkan status yang baru ditemukan ke masing-masing bar tekanan. Itu akan dilakukan dengan subrutin
f
. Kami hanya ingin menambahkan keadaan jika belum terlihat. Negara yang telah dilihat sebelumnya disimpan di%a
:$n
mewakili tekanan baru untuk suatu negara. Saya akan mendapatkan bahwa dari negara bahwa variabel regex masih ada sebagai akibat dari tindakan pahlawan yang mengarah ke panggilan ini:Ini mengarah ke rumus berikut untuk
$n
:Semua substitusi mendapatkan
r
pengubah sehingga mereka mengembalikan keadaan yang diubah dan membiarkan keadaan saat ini$_
sendirian.f
kemudian dipanggil pada kondisi berubah ini, sehingga Anda mendapatkan kode sepertiKarena perhitungan
$n
kebutuhan variabel regex mereka harus default untuk tidak disetel jika penggantian tidak mengubah (karena kondisi untuk memicu mereka tidak terpenuhi). Saya juga tidak harus mengambil variabel regex dari loop sebelumnya. Oleh karena itu substitusi dibungkus dalam{}
blok untuk menyimpan dan mengembalikan negara regex. Seperti itulah Anda mendapatkan pernyataan sepertiKhususnya rotasi begitu dibungkus sehingga ia memanggil
f
tanpa variabel regex dan mendapat kontribusi tekanan 0.Satu-satunya hal yang masih harus dilakukan adalah prima
@0
dengan keadaan awal di awalIni berada di loop utama sehingga juga mencoba untuk menambah
$_
array tekanan kemudian, tetapi karena keadaan awal sudah%a
tidak akan terjadi apa-apa.Bersama-sama semua ini pada dasarnya menemukan solusi terpendek menggunakan algoritma Dijkstra . Namun ada potensi masalah. Kode saat ini tidak akan menambah status jika ditemukan kembali dengan tekanan lebih rendah daripada penemuan pertama. Saya tidak dapat membuat papan yang akan memicu ini, tetapi juga tidak dapat membuktikan bahwa itu tidak mungkin.
sumber
JavaScript,
863834785781 byteMenyimpan 29 byte berkat ETHproduk
Disimpan 53 byte berkat Jordan
Mengambil input sebagai string multiline.
Ini mendefinisikan fungsi anonim yang menggunakan fungsi rekursif
f
untuk menentukan apakah Anda mematikan alarm sebelum mengambil semua tikus.f
kembali1000
jika tekanan di atas 1000 (untuk menghindari rekursi tak berujung), mengembalikan tekanan jika tidak ada lagi tikus untuk menyelamatkan dan mouse di pintu keluar, dan mengembalikan tekanan minimum dari semua gerakan yang mungkin dari keadaan saat ini sebaliknya. Ini menggunakan arrayL
untuk melacak posisi yang sudah dikunjungi di manaL[pos]==0
jika dikunjungi, dan tidak terdefinisi jika tidak. Ini mungkin tidak perlu, tetapi itu mencegah mouse dari melakukan gerakan tidak berguna dan melemparkan kesalahan rekursi setidaknya. (Ini berarti Anda harus mendefinisikan ulangL
jika Anda menguji ini beberapa kali)Ini menggunakan format dalam pertanyaan selain yang mengharuskan Anda menggunakan karakter yang berbeda untuk dinding eksternal. (Apa pun selain
# MEmecd
)Versi yang lebih mudah dibaca:
sumber
s in L|p > 999
.eval
dan mengganti@
dengan$1
(tidak yakin apakah ini akan berhasil, tetapi Anda$1
banyak menulis )f
satu-liner:f=(...)=>s in L|p>999?1e3:!/M/.test(s,L[s]=0)&/E/.test(s)?p:Math.min(...
$1
18 kali, dan.replace("@","$1")
18 byte. Saya tidak melihat cara untuk melakukannya.