Meliputi persegi panjang
Misalkan Anda memiliki matriks bit, misalnya yang berikut ini.
1 1 0 0 0 1 1 0
1 1 1 1 0 1 1 1
0 1 1 1 0 1 1 1
1 1 0 1 1 1 1 0
1 1 0 1 1 1 0 1
Kami ingin menemukan penutup persegi panjang untuk matriks ini. Ini adalah satu set himpunan bagian persegi panjang dari matriks yang tidak mengandung 0s, tetapi bersama-sama berisi semua 1s. Subhimpunan tidak harus disjoint. Berikut adalah contoh penutup persegi panjang untuk matriks di atas.
+----+ +----+
|1 1| 0 0 0 |1 1| 0
| | | |
| +-|-----+ | |+-+
|1 |1| 1 1| 0 |1 1||1|
+----+ | | || |
| | | || |
0 |1 1 1| 0 |1 1||1|
+-------+ | |+-+
+----+ +-----|-+ |
|1 1| 0 |1 1 |1| 1| 0
| | | +----+
| | | | +-+
|1 1| 0 |1 1 1| 0 |1|
+----+ +-------+ +-+
Jumlah persegi panjang di sampul ini adalah 7.
Tugas
Input Anda adalah matriks bit persegi panjang, diambil dalam format apa pun yang masuk akal. Anda dapat menganggapnya mengandung setidaknya satu 1. Output Anda adalah jumlah minimum persegi panjang dalam penutup persegi panjang dari matriks.
Hitungan byte terendah menang. Aturan standar kode-golf berlaku.
Uji kasus
[[1]] -> 1
[[1,1]] -> 1
[[1],[1]] -> 1
[[1,0,1]] -> 2
[[1,0],[0,0]] -> 1
[[1,0],[0,1]] -> 2
[[1,0],[1,1]] -> 2
[[1,1,1],[1,0,1]] -> 3
[[0,1,0],[1,1,1],[0,1,0]] -> 2
[[1,1,1],[1,0,1],[1,1,1]] -> 4
[[1,1,0],[1,1,1],[0,1,1]] -> 2
[[1,0,1,0],[1,1,1,1],[1,0,1,0]] -> 3
[[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,0]] -> 4
[[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,0,1,1]] -> 5
[[1,1,1,0],[1,0,1,0],[1,1,1,1],[0,1,1,1]] -> 4
[[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]] -> 3
[[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]] -> 4
[[0,0,1,0,0],[0,1,1,1,0],[1,1,1,1,1],[0,1,1,1,0],[0,0,1,0,0]] -> 3
code-golf
matrix
optimization
Zgarb
sumber
sumber
[[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]]
Jawaban:
Python 2 ,
318315271 byteMr.Xcoder, ovs dan Jonathan Frech menyelamatkan banyak byte
Cobalah online!
sumber
Jelly ,
2524 byteCobalah online! Solusi golf-kompleksitas tipikal, bahkan tidak perlu repot dengan kasus uji yang lebih besar, mereka akan habis waktu (set daya dari semua persegi panjang yang mungkin diperiksa *)
Bagaimana?
Membentuk semua persegi panjang yang mungkin dibuat. Mengambil set daya persegi panjang itu dan memeriksanya hanya menjaga set yang keduanya tidak mengandung nol dan mengandung masing-masing setidaknya satu kali.
Untuk mencapai "menjaga set-set yang sama-sama tidak mengandung nol dan masing-masing berisi setidak-tidaknya satu kali" bagian kode pertama kali memaksa yang ke set bilangan bulat berbeda lebih dari satu, meninggalkan nol sebagaimana adanya sehingga " menemukan nilai maksimum produk dari nilai - nilai unik ".
* Untuk n oleh matriks m itu cara (n, m) = 2 ^ (T (n) × T (m)) , jadi ...
cara (3,2) = 2 ^ ((3 + 2 + 1) × (2 + 1)) = 2 ^ 18 = 262.144 (tautan TIO)
cara (3,3) = 2 ^ ((3 + 2 + 1) × (3 + 2 + 1)) = 2 ^ 36 = 68.719.447.736
cara (3,4) = 2 ^ ((3 + 2 + 1) × (4 + 3 + 2 + 1)) = 2 ^ 60 = 1.152.921.500.606.846.976
cara (5,5) = 2 ^ 225 ~ = 5.4e + 67 (kasus uji terbesar)
cara (8,5) = 2 ^ 540 ~ = 3,6e + 162 (contoh)
sumber
FJṁ×⁸ẆZ€Ẇ€ẎŒPFQS$$ÐṀL€Ṃ
bekerja untuk -1? Tidak ada waktu untuk menguji rn.1
memiliki produk yang sama dengan penutup yang valid (mis. Putar delapan dengan lima contoh setengah putaran dan akan (secara teori) kembali6
karena akan mengabaikan untuk menutupi bagian atas -kiri sel dan anggap itu valid.)[[1,0],[0,1]]
akan kembali1
daripada2
.JavaScript, 434 byte
Kode:
Hexdump (karena karakter yang tidak patut dicetak):
Cobalah online!
Ini tidak terlalu golf, tetapi setidaknya itu bekerja sangat cepat. Semua kasus uji dapat dihitung dalam beberapa milidetik.
Tidak disatukan
Penjelasan
Ini menggunakan algoritma yang sama seperti untuk memecahkan peta Karnaugh. Pertama ia mencoba untuk menemukan setidaknya satu
1
yang dapat menjadi bagian dari satu persegi panjang yang tidak dapat diperpanjang. Maksud saya non-extensible jika kita memperluas ke arah mana pun (atas, kiri, kanan, bawah) itu akan mencakup setidaknya satu0
(atau akan melampaui batas matriks). Ketika1
ditemukan, temukan persegi panjang terbesar yang menyertakannya dan beri tanda semua1
pada persegi panjang itu. Ulangi sampai tidak ada lagi yang tidak ditandai1
yang memenuhi kondisi ini.Dalam beberapa kasus (seperti dalam kasus uji 16) ada
1
s yang tersisa setelah menerapkan langkah pertama. Kemudian sebutkan semua ini1
dan terapkan semacam pencarian brute-force yang ditingkatkan. Langkah ini jarang diterapkan, dan bahkan dalam kasus ini, kita perlu memeriksa dengan paksa satu atau dua kombinasi, sehingga harus bekerja sangat cepat bahkan untuk kasus uji yang lebih besar.sumber