pengantar
Selama berabad-abad, ada sungai tertentu yang tidak pernah dipetakan. Guild of Cartographers ingin membuat peta sungai, namun, mereka tidak pernah berhasil - karena beberapa alasan, semua kartografer yang mereka kirim untuk memetakan sungai telah dimakan oleh binatang buas di daerah tersebut. Diperlukan pendekatan yang berbeda.
Deskripsi Input
Area tersebut adalah grid sel panjang m
dan lebar n
. Sel di kiri bawah adalah 0,0
, dan sel di kanan atas adalah m-1,n-1
. m
dan n
disediakan dalam input sebagai tuple m,n
.
Dengan menggunakan teknik sounding geografis jarak jauh lokasi pulau di sekitar sungai telah diidentifikasi. Ukuran pulau (yaitu berapa banyak sel yang ditempati pulau) juga telah diidentifikasi tetapi bentuknya belum. Kami menyediakan informasi ini dalam sebuah tuple di s,x,y
mana s
ukuran pulau, dan x
dan y
adalah posisi x dan y dari satu sel tertentu dari pulau itu. Setiap tuple dalam input dipisahkan oleh ruang, jadi di sini adalah contoh input:
7,7 2,0,0 2,3,1 2,6,1 2,4,3 2,2,4 8,0,6 1,2,6 3,4,6
Untuk mengilustrasikan lebih jelas, berikut adalah input pada grafik:
y 6|8 1 3
5|
4| 2
3| 2
2|
1| 2 2
0|2
=======
0123456
x
Deskripsi Output
Keluarkan peta menggunakan karakter ASCII untuk mewakili bagian dari area. Setiap sel akan menjadi #
(tanah) atau .
(air). Peta harus mengikuti aturan-aturan ini:
- Definisi. Pulau adalah kelompok sel tanah yang berdekatan secara ortogonal yang seluruhnya dibatasi oleh sel-sel sungai dan / atau perbatasan daerah tersebut.
- Definisi. Sungai adalah kelompok sel air yang berdekatan secara ortogonal yang dibatasi seluruhnya oleh sel tanah dan / atau perbatasan daerah tersebut, dan tidak mengandung "danau" (2x2 area sel air).
- Memerintah . Peta harus memuat tepat satu sungai.
- Memerintah . Setiap sel bernomor dalam input harus merupakan bagian dari pulau yang mengandung
s
sel dengan tepat . - Memerintah . Setiap pulau di peta harus berisi persis salah satu sel bernomor dalam input.
- Memerintah . Ada satu peta unik untuk setiap input.
Berikut adalah output dari contoh input:
#.#.##.
#....#.
#.##...
##..##.
###....
...##.#
##....#
Berikut ini adalah input dan output lain.
Memasukkan:
5,5 3,0,1 1,4,1 2,0,4 2,2,4 2,4,4
Keluaran:
#.#.#
#.#.#
.....
###.#
.....
sumber
javascript:(_=>{var t=Game.nurikabe().task,m=t.length,n=t[0].length,s=[m,n];for(var i=0;i<m;i++)for(var j=0;j<n;j++)if(t[i][j]>=0)s+=' '+[t[i][j],i,j];puzzleContainerDiv.insertAdjacentHTML('beforeend','<hr><tt style=color:red>'+s+'</tt><hr>')})();void(0)
Jawaban:
C + PicoSAT ,
2345995952 byteCobalah online!
(Peringatan: tautan TIO ini adalah URL 30 kilobyte yang berisi salinan PicoSAT 965 yang diperkecil, jadi Anda mungkin tidak dapat memuatnya di beberapa peramban, tetapi memuat setidaknya di Firefox dan Chrome.)
Bagaimana itu bekerja
Kami menginisialisasi pemecah SAT dengan variabel untuk setiap sel (tanah atau air), dan hanya kendala berikut:
Sisa kendala sulit untuk disandikan langsung ke SAT, jadi alih-alih kami menjalankan solver untuk mendapatkan model, menjalankan urutan pencarian pertama untuk menemukan wilayah yang terhubung dari model ini, dan menambahkan kendala tambahan sebagai berikut:
Mengambil keuntungan dari antarmuka tambahan ke pustaka PicoSAT, kita dapat segera menjalankan kembali solver termasuk kendala yang ditambahkan, menjaga semua kesimpulan sebelumnya yang dibuat oleh solver. PicoSAT memberi kami model baru, dan kami terus mengulangi langkah-langkah di atas sampai solusinya valid.
Ini sangat efektif; itu memecahkan 15x15 dan 20x20 contoh dalam sepersekian detik.
(Terima kasih kepada Lopsy karena menyarankan gagasan ini untuk secara interaktif membatasi daerah yang terhubung dalam pemecah SAT yang meningkat, beberapa waktu lalu.)
Beberapa test case yang lebih besar dari puzzle-nurikabe.com
Halaman acak berisi 15 × 15 teka-teki keras ( 5057541 , 5122197 , 5383030 , 6275294 , 6646970 , 6944232 ):
Halaman acak 20 × 20 puzzle normal ( 536628 , 3757659 ):
sumber
GLPK , (tidak bersaing) 2197 byte
Ini adalah entri yang tidak bersaing, seperti
Saya akan menyimpan versi yang masih belum diubah, namun fungsional di sini. Bergantung pada umpan balik, saya mungkin mencoba mempersingkat + menambahkan penjelasan jika ada minat. Sejauh ini, nama kendala berfungsi sebagai dokumen di tempat.
Gagasan utamanya adalah untuk menyandikan batasan "pulau-pulau yang berdekatan" dengan memperkenalkan variabel aliran terpelihara yang memiliki sumber yang ditentukan sebelumnya di lokasi petunjuk. Variabel keputusan
is_island
kemudian memainkan peran tempat tenggelam. Dengan meminimalkan jumlah total aliran ini, pulau-pulau tersebut dipaksa untuk tetap terhubung secara optimal. Kendala lain agak langsung menerapkan berbagai aturan. Apa yang membingungkan saya yang sepertinya masih saya butuhkanisland_fields_have_at_least_one_neighbor
.Kinerja formulasi ini tidak bagus. Dengan langsung memakan semua kompleksitas dengan sejumlah besar kendala, pemecah membutuhkan waktu hampir 15 detik untuk contoh 15 x 15.
Kode (masih belum diubah)
Data masalah
5 x 5
7 x 7
15 x 15
Pemakaian
Telah
glpsol
terpasang, model sebagai satu file (mis.river.mod
), Memasukkan data dalam file terpisah (mis7x7.mod
). Kemudian:Ini ditambah beberapa kesabaran akan mencetak solusi dalam format output yang ditentukan (bersama dengan output diagnostik "beberapa").
sumber
Python 3 , 1295 byte
Ini adalah solusi hanya python. Tidak menggunakan pustaka dan memuat papan melalui input standar. Penjelasan lebih lanjut akan datang. Ini adalah upaya pertama saya di golf yang begitu besar. Ada tautan ke kode yang dikomentari dan tidak ada golf di bagian bawah.
Cobalah online!
Lihatlah kode un-golfed .
sumber