Anda adalah seorang musafir yang melintasi padang pasir antara dua kota. Anda tidak dapat membawa air yang cukup untuk menyeberang tanpa berhenti. Ini adalah variasi dari teka-teki klasik.
Aturan
Gurun terlihat seperti ini: kotak WxH sebagian besar ruang kosong. Ruang yang ditandai S
adalah tempat Anda mulai, E
tempat Anda ingin mengakhiri, dan kotak yang ditandai dengan angka N menampung N unit air. Kotak ditandai dengan .
tahan nol air.
.....................................
........S............................
.....................................
.........7...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................
Anda mulai dari S dengan 5 unit air.
Anda dapat membawa paling banyak 5 unit air.
Setiap giliran Anda
- pindahkan satu kotak ke atas, Bawah, Kiri, atau Kanan,
- mengkonsumsi 1 unit air yang Anda bawa,
- mengambil atau menjatuhkan beberapa unit air.
Sebuah gilirannya dinotasikan demikian: (direction)(+|-)(units of water)
, +
menunjukkan Anda mengambil air, -
bahwa Anda menjatuhkannya.
Contoh berubah:
D+0 Move Down
R+0 Move Right
D+2 Move Down, pick up two units of water.
U-1 Move Up, drop one unit of water.
Jika Anda melakukan gerakan ini mulai dari S pada contoh di atas, gurun tampak seperti ini sesudahnya.
.....................................
........S............................
.........1...........................
.........5...........................
.....................................
.......................3.............
.....5...............................
................................2....
.....................................
.....................................
.....................................
...............................E.....
.....................................
....................7................
.....................................
.....................................
Anda tidak dapat mengambil lebih banyak air daripada yang sudah ada di alun-alun Anda. Saat Anda mengambil air, kurangi jumlah unit itu dari hitungan ubin.
Anda hanya dapat mengambil air untuk menampung maksimal 5 unit.
Tidak ada ubin yang dapat menampung lebih dari 9 unit, kecuali S yang menampung unit tanpa batas.
Anda hanya bisa menjatuhkan air sebanyak yang Anda pegang saat ini.
Air di tanah tetap tidak berubah sampai Anda mengambilnya lagi.
Jika Anda kembali ke S, Anda dapat mengambil sejumlah air tanpa mengurasnya.
Jika Anda mencapai E maka Anda menang . Anda masih menang jika Anda mengkonsumsi unit air terakhir Anda pada E.
Jika, setelah giliran Anda, Anda memiliki nol air dan Anda tidak berada di E, Anda mati .
Masukan dan keluaran
Program Anda akan menerima peta awal ukuran sewenang-wenang STDIN
sebagai seni ASCII dalam format di atas. Anda dapat menganggap itu adalah persegi panjang yaitu semua garis memiliki panjang yang sama, bahwa ada tepat satu S
dan satu E
kotak, semua garis diakhiri dengan \n
, dan seluruh STDIN akan sesuai dengan regex ini:/^[SE1-9\.\n]+$/
Program Anda akan menulis output berikut ke STDOUT:
- daftar gerakan,
- keadaan akhir peta.
Anda dapat menampilkan daftar gerakan dalam format apa pun yang nyaman.
Status akhir peta akan dicetak dalam format yang sama dengan input kecuali bahwa itu juga akan menunjukkan rute yang Anda ambil melalui padang pasir dengan menandai semua ubin yang dikunjungi dengan #
, jika ubin itu tidak mengandung air dan bukan S atau E (yaitu ini .
).
CONTOH input:
.....S.
.......
.......
E......
....8..
CONTOH hasil kemenangan:
D+0
D+0
D+0
D+0
L+5
L+0
L+0
L+0
L+0
U+0
.....S.
.....#.
.....#.
E....#.
####3#.
Ketidaksenangan
Ketika Anda memposting kode Anda, memposting input peta sampel yang kode Anda menemukan solusi yang memenuhi kondisi non-sepele berikut:
- S dan E setidaknya 10 langkah terpisah.
- Setiap bujur sangkar yang awalnya berisi N unit air harus dikelilingi oleh perbatasan selebar-N di mana semua kotak
.
(tidak ada air, bukan S atau E)
CONTOH
........2.
..........
..........
S.1..2....
..........
..........
........1.
..3.......
.........E
Jika Anda menambah jumlah air pada ubin apa pun, hal di atas menjadi sepele.
Persyaratan
Agaknya program Anda akan menghadapi sejumlah upaya gagal sebelum menemukan solusi, jika ada.
- Program Anda pada akhirnya harus menyelesaikan setiap input yang dapat dipecahkan.
- Saya ingin melihat Anda mati - program Anda akan menampilkan gerakan dan peta akhir rute kematian untuk setiap upaya yang gagal untuk menemukan solusi.
- Jika Anda menemukan solusi yang menang, cetak output penuh untuk itu dan hentikan.
- Jalankan sampai solusi ditemukan, tetapi jangan mencoba solusi yang sama dua kali - semua kematian harus melalui rute yang berbeda.
- Gunakan input tes ini:
(membutuhkan setidaknya satu gerakan untuk menjatuhkan cache air di beberapa titik tengah).
S........
.........
.........
........E
Kode terpendek yang diposting dengan input demonstrasi non-sepele yang dipecahkan menang.
Jawaban:
Perl,
299 + 1 = 300254 + 1 = 255 byteIni hampir pasti akan dikalahkan oleh salah satu bahasa golf ketika orang melihat algoritma saya :-)
Jalankan dengan
-n
(penalti 1 byte).Versi sebelumnya tidak cukup sesuai dengan spesifikasi karena meninggalkan air ekstra di peta dan tidak menunjukkannya di versi final peta; saat mengubah algoritma untuk mengatasi situasi itu, saya berhasil golf sedikit lebih kecil dalam proses.
Contoh (Saya telah menambahkan jeda baris ke output untuk menghindari perlunya menggulir dan menampilkan struktur):
Dalam notasi yang digunakan oleh program, gerakan diwakili melalui
L
,R
,U
, danD
untuk kiri, atas, kanan, bawah masing-masing. Secara default, Anda mengambil 1 unit air setelah setiap gerakan, tetapi ini dapat dimodifikasi dengan menambahkan karakter:X
: jatuhkan 2 unit air, daripada mengambil 1Y
: jatuhkan 1 unit air, daripada mengambil 1(yaitu ruang): sepenuhnya terisi air (hanya keluaran setelah pindah ke
S
; program ini juga keluaran dengan ruang terkemuka, yang masuk akal karena Anda mulai penuh di atas air)Seperti yang dapat Anda lihat, mungkin saja untuk melintasi peta ini (agak mandul) tanpa menggunakan kolam tambahan sama sekali. Bahkan, dimungkinkan untuk mendapatkan jarak di bawah aturan ini, di peta mana pun , tanpa bantuan air yang disiapkan sebelumnya. Dengan demikian, algoritme ini mengabaikan air preplaced, artinya saya tidak perlu membuang byte yang mencoba menanganinya. Ini juga berarti Anda tidak akan melihat bot mati, maaf. Itu tidak pernah bergerak di luar rentang di mana ia tahu dijamin untuk bertahan hidup
Alasan kita membutuhkan keduanya
X
danY
(dan sedikit kode tambahan untuk memastikan kita memilikiX
sebagian besar strategi tetapi kadang-kadangY
di akhir) adalah bahwa spesifikasi membutuhkan versi final peta untuk menjadi output. Cara termudah untuk mengimplementasikan ini adalah meninggalkan peta sama sekali tidak tersentuh (terlepas dari jalur kami melalui kotak yang awalnya kosong), terutama karena kotak yang dimulai dengan9
air akan berakhir dengan10
(melanggar seni ASCII) jika kebetulan berada di jalan dan kami hanya menggunakanX
, dan dengan demikian kita perlu menemukan beberapa solusi yang menghindari menjatuhkan air tambahan di peta. Algoritme di sini akan "secara alami" menjatuhkan 1 unit air tambahan pada setiap kotak pada rute; dengan demikian, waktu terakhir kita mengunjungi setiap kotak, kita mengurangi jumlah air yang dijatuhkan oleh 1 melalui penggunaan Y daripada X, sehingga pada kunjungan terakhir kita, kita mengalirkan kembali kotak ke jumlah air aslinya, daripada meninggalkannya sedikit lebih basah daripada ketika kita mulai.Saya akan merekomendasikan untuk tidak menjalankan ini pada peta besar, karena memiliki kinerja O (2 ^ n) (meskipun bot tidak pernah mati kehausan, masuk akal untuk berpikir itu akan mati karena kelaparan menggunakan strategi seperti ini.)
Versi yang dapat dibaca:
sumber