Plot : Jimmy hilang; kita harus menemukannya. Kita harus berpisah.
Plot twist : Jimmy sudah mati.
Tapi, pemeran kami tidak tahu itu, jadi mereka perlu mencari di seluruh area. Ada kolom N kolom x M baris (1 <= M, N <= 256) sel, baik ditandai sebagai "S" untuk titik awal, "." untuk ruang terbuka, atau "#" untuk hambatan. Ini peta .
Ada 0 <= p <= 26 costars , 0 <= q <= 26 ekstra , dan 1 bintang . Setiap orang awalnya di sel bertanda S.
Aturan
Setiap orang memiliki radius penglihatan yang ditunjukkan di bawah ini:
...
.....
..@..
.....
...
Bintang dilambangkan dengan "@", costars dengan huruf kapital, dimulai dengan "A", dan ekstra dengan huruf kecil, dimulai dengan "a". Awalnya, radius penglihatan yang mengelilingi titik awal sudah ditandai sebagai dicari. Jika ini merupakan seluruh ruang terbuka peta, permainan berakhir. Setiap belokan, dengan urutan sebagai berikut :
- Setiap orang secara bersamaan membuat raja bergerak (baik berdiri diam, atau pindah ke salah satu dari 8 sel tetangga).
- Semua sel dalam radius penglihatan di sekitar setiap orang dihitung sebagai yang dicari.
- Jika seorang costar tidak bisa melihat orang lain, dia mati. Jika ekstra tidak dapat melihat costar, bintang, atau setidaknya 2 tambahan lainnya, dia mati. Ini terjadi secara bersamaan - yaitu, tidak ada reaksi berantai kematian pada satu putaran; kondisi di atas diperiksa, dan semua orang yang akan mati akan mati sekaligus.
- Jika semua ruang terbuka di peta telah dicari, pencarian sudah selesai.
Catatan
Banyak orang dapat berada di alun-alun yang sama pada titik mana pun, dan orang-orang ini dapat saling bertemu.
Rintangan tidak pernah menghalangi penglihatan, hanya gerakan; orang bisa melihat satu sama lain di seberang, eh ... lava?
Ruang terbuka di peta dijamin terhubung oleh gerakan raja.
Awal "S" juga dianggap sebagai ruang terbuka, bukan hambatan.
Setiap raja yang mendarat di ruang terbuka valid. Misalnya, langkah berikut ini legal:
.... ....
.@#. ---> ..#.
.#.. .#@.
.... ....
Memasukkan
Masukan akan dalam format
N M p q
[N cols x M rows grid with characters ".", "#", and "S"]
Input sampel:
6 5 0 0
......
......
..S...
......
......
dan
9 9 1 1
S.......#
.......##
......##.
..#####..
...##....
...##....
...#.....
....#..#.
.........
p dan q adalah jumlah costars dan ekstra, masing-masing.
Keluaran
Output harus, untuk setiap belokan, gerakan yang dibuat, dengan arah yang ditunjukkan oleh
789
456
123
Urutan gerakan tidak masalah, karena semuanya diberlakukan secara bersamaan. Tidak mencantumkan langkah untuk seseorang baik-baik saja, dan sama dengan memindahkannya ke arah 5. Gerakan harus terdaftar dalam format berikut:
@9 A2 a2 B7.
"." menunjukkan akhir gerakan Anda untuk giliran.
Setelah peta dicari, garis akhir output haruslah tiga bilangan bulat, dipisahkan oleh spasi: jumlah belokan yang Anda perlukan untuk menyelesaikan pencarian papan, jumlah costar hidup, dan jumlah ekstra hidup. Untuk input contoh pertama
6 5 0 0
......
......
..S...
......
......
berikut ini adalah output yang valid:
@4.
@6.
@6.
@6.
4 0 0
Catatan terakhir: bintang tidak bisa mati dan ruang terbuka di peta dijamin akan terhubung, sehingga pencarian akan selalu berhasil pada akhirnya.
Mencetak gol
Skor Anda adalah jumlah total belokan yang diambil atas serangkaian tes benchmark; Anda dipersilakan untuk menyerahkan test case Anda sendiri beserta jawaban Anda. Jumlah dari jumlah costar hidup selama set benchmark akan digunakan sebagai tie-breaker, dan jika masih ada tie, jumlah dari jumlah ekstra living akan digunakan.
Perangkat Uji dan Pengontrol
Saat ini, 5 peta online di https://github.com/Tudwell/HorrorMovieSearchParty/ . Siapa pun yang mengirimkan jawaban juga dapat mengajukan test case, yang saya berhak tolak karena alasan apa pun (jika saya menolak peta Anda karena suatu alasan, Anda dapat mengirimkan yang lain). Ini akan ditambahkan ke set tes sesuai kebijaksanaan saya.
Kontroler Python (diuji dalam 2.7.5) disediakan di github sebagai controller.py . Kontroler kedua di sana, controller_disp.py , identik kecuali menunjukkan output grafis selama pencarian (memerlukan pustaka Pygame).
Penggunaan :
python controller.py <map file> <your execution line>
Yaitu:
python controller.py map1.txt python solver.py map1.txt
Pengontrol memiliki output (ke stdin program Anda ) dari formulir
Turn 1
@:2,3 A:2,3 B:2,3.
##...##
#ooo..#
ooooo..
ooooo..
ooooo..
#ooo...
##.....
###....
----------------------------------------
Ini adalah nomor belokan (belok 1 adalah sebelum Anda pindah), daftar '.'- yang diakhiri dari semua aktor dan koordinat x, y mereka (karakter kiri atas adalah (0,0)), representasi dari keseluruhan papan, dan garis dengan 40 '-'s. Kemudian menunggu input (dari stdout program Anda ) dari formulir
@9 A2 B7.
Ini adalah format output yang ditentukan di atas. Pengontrol menghasilkan 'o' untuk ruang terbuka yang telah dicari, '.' untuk ruang terbuka yang belum dicari, dan '#' untuk hambatan. Ini hanya mencakup orang yang hidup dalam daftar orang dan koordinatnya, dan melacak semua aturan permainan. Pengontrol akan keluar jika ada upaya ilegal. Jika gerakan untuk giliran tertentu menyelesaikan pencarian, hasilnya tidak seperti di atas; alih-alih itu dari formulir
Finished in 4 turns
4 1 0
"4 1 0" di sini menunjukkan 4 total belokan, 1 costar hidup, dan 0 ekstra hidup. Anda tidak perlu menggunakan pengontrol; merasa bebas untuk menggunakannya atau memodifikasinya untuk entri Anda sendiri. Jika Anda memutuskan untuk menggunakannya dan menemui masalah, beri tahu saya.
Terima kasih kepada @githubphagocyte karena membantu saya menulis controller.
Sunting: Untuk entri acak, Anda dapat memilih jalan di peta tertentu sebagai skor Anda untuk peta itu. Perhatikan bahwa karena persyaratan penilaian, Anda harus selalu memilih belokan paling sedikit, kemudian costar mati paling sedikit, lalu tambahan mati paling sedikit untuk setiap peta.
sumber
Jawaban:
Ruby, Safety First + BFS + Randomness, Score ≤ 1458
Saya tidak yakin bagaimana Anda akan mencetak kiriman acak. Jika semua jawaban harus deterministik, beri tahu saya dan saya akan memilih satu benih atau menyingkirkan keacakan secara bersamaan.
Beberapa fitur dan kekurangan dari solusi ini:
map5.txt
membutuhkan waktu antara 1 dan 13 menit untuk menyelesaikan.Beberapa hasil
Sekarang inilah kodenya:
Ada beberapa keluaran debug yang dikomentari di sana. Terutama
if group['@']
blok ini cukup menarik karena mencetak visualisasi data BFS.Sunting: Peningkatan kecepatan yang signifikan, dengan menghentikan BFS jika langkah yang lebih baik telah ditemukan (yang agak merupakan titik menggunakan BFS di tempat pertama).
sumber