Latar Belakang
Nonogram , juga dikenal sebagai Picross atau Griddlers, adalah teka-teki di mana tujuannya adalah untuk menentukan apakah setiap sel pada grid 2D harus diwarnai atau dibiarkan kosong, menggunakan jumlah sel berwarna berturut-turut pada setiap baris.
Berikut ini adalah contoh puzzle Nonogram dengan solusi.
Masalahnya adalah, beberapa game / aplikasi seluler Nonogram komersial memiliki teka-teki yang tidak dapat dipecahkan dengan tangan (mis. Memiliki beberapa solusi, atau memerlukan pengulangan yang dalam). Namun, mereka juga menawarkan beberapa nyawa kepada pemain, di mana satu nyawa hilang ketika Anda mencoba untuk mewarnai sel yang jawaban yang benar kosong . Jadi sekarang saatnya untuk memaksa "puzzle" jahat itu!
Untuk menyederhanakan tugas, bayangkan hanya satu baris dengan petunjuknya dan tidak ada yang lain:
3 7 | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
The [3,7]
adalah petunjuk, dan panjang garis adalah 15 sel. Karena memiliki beberapa solusi yang mungkin, kita perlu mengambil risiko beberapa nyawa untuk sepenuhnya menyelesaikan garis ini (yaitu menentukan semua sel berwarna).
Tantangan
Diberi garis dengan petunjuk (daftar bilangan bulat positif) dan panjang garis, temukan jumlah maksimum nyawa yang akan Anda hilangkan, dengan anggapan bahwa Anda brute-paksa garis dengan strategi optimal.
Perhatikan bahwa Anda selalu menebak sel berwarna . Dalam gim sebenarnya, menebak sel kosong (baik benar atau salah) tidak berpengaruh pada hidup Anda, jadi Anda tidak bisa "memecahkan" teka-teki seperti itu.
Juga, Anda dapat mengasumsikan input selalu mewakili garis Nonogram yang valid, jadi Anda tidak perlu khawatir tentang sesuatu seperti [6], 5
.
Penjelasan
Mari kita lihat beberapa contoh sederhana dulu.
[1,2], 5
Ada tiga kemungkinan untuk garis ini ( O
sel berwarna, sel .
kosong):
O . O O .
O . . O O
. O . O O
Jika kami mencoba mewarnai sel 0 (indeks berbasis 0 dari kiri), salah satu dari yang berikut ini terjadi:
- Sel berwarna dengan benar. Sekarang kita memiliki dua kemungkinan, dan kita dapat memilih antara sel 2 dan sel 4 untuk sepenuhnya menyelesaikan garis. Bagaimanapun, kita akan kehilangan satu nyawa dalam kasus terburuk.
- Sel itu kosong, dan kita kehilangan nyawa. Dalam hal ini, kami telah mengidentifikasi solusi unik untuk baris ini, jadi kami selesai dengan 1 nyawa yang hilang.
Karena itu, jawabannya [1,2], 5
adalah 1.
[5], 10
Pencarian biner? Nggak.
Pilihan pertama yang paling jelas adalah 4 atau 5, yang akan mengungkapkan satu kemungkinan jika itu kosong (dengan biaya 1 kehidupan). Katakanlah kita memilih 4 dulu. Jika sel 4 benar-benar berwarna, kita perluas ke kiri, yaitu coba 3, 2, 1 dan 0 sampai sebuah nyawa hilang (atau sel 0 berwarna, maka kita tidak menghabiskan hidup sama sekali). Setiap kali nyawa hilang, kita dapat secara unik menentukan solusinya, misalnya jika kita melihat sesuatu seperti ini:
_ _ X O O _ _ _ _ _
maka kita sudah tahu jawabannya adalah ini:
. . . O O O O O . .
Karena itu, jawabannya [5], 10
adalah 1.
[3,7], 15
Mulai dengan sel 11, yang, jika kosong, akan segera mengungkap solusi berikut.
O O O . O O O O O O O X . . .
Kemudian coba 12, yang, jika kosong, memberikan dua kemungkinan yang dapat diselesaikan dengan biaya 1 kehidupan tambahan.
O O O . . O O O O O O O X . .
. O O O . O O O O O O O X . .
Sekarang coba 2. Jika kosong, itu mengarah ke tiga kemungkinan yang dapat dipecahkan mirip dengan [1,2], 5
contoh.
. . X O O O . O O O O O O O .
. . X O O O . . O O O O O O O
. . X . O O O . O O O O O O O
Jika Anda terus meminimalkan risiko dengan cara ini, Anda dapat mencapai solusi apa pun dengan maks. 2 nyawa dihabiskan.
Uji Kasus
[1,2] 5 => 1
[2] 5 => 2
[1] 5 => 4
[] 5 => 0
[5] 10 => 1
[2,1,5] 10 => 0
[2,4] 10 => 2
[6] 15 => 2
[5] 15 => 2
[4] 15 => 3
[3,7] 15 => 2
[3,4] 15 => 3
[2,2,4] 15 => 4
[1,1,1,1,1,1,1] 15 => 2
[2,1,1,3,1] 15 => 3
[1,1,1,2,1] 15 => 5
Untuk dua kasus terakhir, strategi optimal tidak melalui blanko minimum, tetapi hanya bergerak dari kiri ke kanan (atau kanan ke kiri). Terima kasih kepada @crashoz karena menunjukkannya.
Aturan
Aturan standar kode-golf berlaku. Pengajuan terpendek yang valid dalam byte menang.
Karunia
Jika seseorang datang dengan algoritma waktu polinomial (dengan bukti kebenaran), saya akan memberikan hadiah +100 untuk solusi semacam itu.
sumber
[6], 5
?Jawaban:
Ruby , 85 byte
Cobalah online!
Penjelasan
Berikut adalah contoh
_
yang tidak diketahui,X
adalah ruang yang dikenal,O
adalah sel berwarna yang dikenal danL
hilang nyawaMari kita mendefinisikan fungsi biayah
Finally this recursive definition ofh shows us that option (2) in function f is always the worst case (giving the maximum number of possibilities i.e. maximizing h )
Every step we decreasen by at least 3 and there is now a single recursive call, complexity is O(n)
sumber
Python,
303289 bytesFirst golf in a long time, so there may be a lot of excess fat. (Thanks Jo King for finding 14 bytes-worth.)
Function f generates all the possible arrangements (though always with a blank as the first character, but that's fine as long as we increment the length by 1 before we call it). Function g picks the position with the fewest number of blanks and recurses. Function h puts them together.
The examples all run fine:
sumber
False
for0
? If so, you can change(len(q)>1)*1and
tolen(q)>1and
. If you are not allowed to returnFalse
for0
, then do that, but changeg(f(l,n+1),n+1)
to1*g(f(l,n+1),n+1)
and it will still save one byteFalse
is not allowed for0
, instead of changingg(f(l,n+1),n+1)
to1*g(f(l,n+1),n+1)
, change it to+g(f(l,n+1),n+1)
h=
in your byte count