Anda telah dipekerjakan sebagai asisten peneliti, dan diminta untuk membuat program kecil yang akan membangun labirin tikus. Kotak tikus selalu 62x22 dan memiliki pintu masuk (a) dan keluar (A) untuk tikus, seperti ini (input 1):
#######a######################################################
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
#################################################A############
Program Anda harus mengisi kotak dengan blok (#) meninggalkan jalur untuk tikus, seperti ini (keluaran 1):
#######a######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ######################################################
####### ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
################################################# ############
#################################################A############
Ini mudah menurut Anda! Anda mulai menulis sebuah program kecil, penuh percaya diri. Namun, Ilmuwan Prinsip telah memiliki ide baru - dia ingin dua tikus untuk menavigasi labirin pada saat yang sama. Dr Rattanshnorter menjelaskan bahwa mereka memiliki pintu dan pintu keluar yang berbeda (input 2):
#b#####a######################################################
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# #
# B
# #
#################################################A############
Tikus telah dilatih untuk bergerak lurus melalui persimpangan tetapi T-persimpangan membuat mereka bingung dan akan membatalkan percobaan. Anda memulai tugas baru Anda yang lebih kompleks ketika Dokter yang baik menjelaskan satu syarat terakhir: tikus itu ganas satu sama lain sehingga jika mereka melihat satu sama lain pada titik mana pun, perkelahian tikus akan pecah dan Anda berdua akan berada di hadapan dewan etika. Anda sekarang menyadari program Anda harus menampilkan sesuatu yang membingungkan seperti ini (keluaran 2):
#b#####a######################################################
# ##### ######################################################
# ##### ######################################################
# ##### ####################################### ####
# ##### ####################################### ######### ####
# ##### ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# ############################################# # ####### ####
# # ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### ####
################################################# ####### B
################################################# ############
#################################################A############
Pada saat tikus B mencapai persimpangan, tikus A akan melakukan perjalanan menyusuri koridor untuk keluar dari A dan pertarungan tikus akan dihindari.
Aturan:
Program Anda harus membaca (STDIN atau file) input seperti yang di atas, dan output (STDOUT atau file) data yang sama kecuali banyak ruang sekarang akan hash (#). Anda dapat mengganti karakter tunggal (seperti
;
) daripada\n
dalam string input tetapi string output masih membutuhkan\n
karakter. DIPERBARUIJalur tikus harus memiliki lebar satu karakter, kecuali untuk persimpangan silang (setiap ruang harus memiliki nol atau dua
#
karakter yang berdekatan secara orthogonal ). Setiap tikus harus memiliki jalur tunggal yang jelas, kecuali untuk persimpangan silang. Tidak ada pertigaan.Tikus dilepaskan secara bersamaan dan bergerak dengan kecepatan konstan. Tidak boleh ada waktu dua atau lebih tikus melihat satu sama lain (berada di kolom atau baris yang sama tanpa salah satu
#
karakter di antaranya).Jika tidak ada solusi yang mungkin (seperti titik masuk yang berdekatan), cetak
Impossible\n
dan keluar.Pintu masuk dan keluar bisa berada di sisi mana saja, namun mereka tidak akan pernah ada di sudut.
Jika pintu masuk dan keluar yang cocok berdekatan (misalnya:)
##aA##
, tikus tidak dapat langsung pergi daria
keA
. Harus ada bagian koridor 2 ruang kecil di dalam area labirin.Pada belokan di mana tikus mencapai titik keluarnya (atau kapan saja setelah itu), ia tidak lagi terlihat oleh tikus lain.
Program Anda dapat dirancang untuk menghitung labirin untuk 1, 2, hingga 26 tikus.
Celah standar tidak diijinkan.
Skor:
Dengan solusi Anda, tentukan berapa banyak tikus per labirin (N) yang dapat dipecahkan oleh program Anda. Skor Anda adalah panjang kode Anda dalam byte dibagi dengan angka ini N.
Harap sertakan contoh keluaran dalam jawaban Anda sehingga kami dapat melihat apa yang dihasilkan oleh program Anda.
Jawaban:
Haskell, 26 tikus ?, ~ 5000 byte
Secara teoritis, kode ini harus bekerja untuk sejumlah tikus, tetapi saya tidak memberikan jaminan bahwa itu akan berakhir sebelum kematian panas alam semesta. Ini didasarkan pada algoritma backtracking yang mencoba untuk pergi jalan lurus dulu, dan kemudian beralih jalur jika jalan tidak bekerja. Jumlah alternatif bersifat eksponensial berkenaan dengan panjang jalan dan jumlah tikus.
Saya belum repot-repot bermain golf, karena ini sangat besar, dan karena saya ingin membuatnya lebih cepat terlebih dahulu.
Output sampel, 6 tikus:
sumber
b
sampai ke persimpangane
danb
, apakah dia tidak terlihat olehe
?b
tampaknya sampai di sanat = 11
, yang akane
tetap di koridor itu. Apakah saya melewatkan sesuatu?Haskell, 1 tikus, 681 Karakter
Masalahnya bisa diselesaikan secara sepele untuk semua labirin hanya dengan satu tikus. Kode ini juga "berfungsi" untuk sejumlah tikus, tetapi tidak mengikuti kendala apa pun pada interaksi antara banyak tikus dan lintasan.
Output sampel:
Saya berencana untuk mendukung banyak tikus, jadi saya menulis kode generik, tetapi saya belum menemukan algoritma yang bagus untuk itu.
parse
mengekstrak daftar semua pintu masuk dan keluar, dengan koordinatnyarats
mengambil daftar itu dan mengonversinya menjadi pasangan koordinat untuk setiap tikus.bnds
mengambil koordinat di tepi dan memindahkannya ke koordinat terdekat di dalam labirin.naive
mengambil posisi awal dan akhir dan mengembalikan jalur sederhana di antara mereka.main
lalu ganti semua ruang putih yang tidak ada di jalur dengan '#'sumber