Penutup persegi panjang minimum

23

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 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
Zgarb
sumber
Apakah ini terinspirasi oleh peta Karnaugh ?
1
@ThePirateBay Lainnya oleh kompleksitas komunikasi nondeterministic .
Zgarb
@ThePirateBay untuk k-map semua persegi panjang harus memiliki kekuatan dua dimensi.
Sparr
@Parr. Ya saya tahu. Saya hanya bertanya apakah itu mungkin inspirasi untuk tantangan ini.
1
[[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]]
Kasing

Jawaban:

6

Python 2 , 318 315 271 byte

Mr.Xcoder, ovs dan Jonathan Frech menyelamatkan banyak byte

p=range
def f(x,i=0,j=-1):z=len(x[0]);j+=1;i+=j/z;j%=z;return i<len(x)and(x[i][j]and-~min([f([[v,v[:j]+[2]*(r-j)+v[r:]][i<=y<=e]for y,v in enumerate(x)],i,j)for e in p(i,len(x))for r in p(j+1,z+1)if all(all(k[j:r])for k in x[i:e+1])]+[f(x,i,j)-1]*(x[i][j]>1))or f(x,i,j))

Cobalah online!

Halvard Hummel
sumber
4

Jelly ,  25  24 byte

FJ‘ṁ×⁸ẆZ€Ẇ€ẎŒPFQP$$ÐṀL€Ṃ

Cobalah 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 ".

FJ‘ṁ×⁸ẆZ€Ẇ€ẎŒPFQP$$ÐṀL€Ṃ - Link: list of lists of ones and zeros, M
F                        - flatten M into a single list
 J                       - range of length = [1,2,3,...,len(flattened(M))]
  ‘                      - increment       = [2,3,4,...,len(flattened(M))+1]
   ṁ                     - mould like M - reshapes it just like M again
     ⁸                   - chain's left argument, M
    ×                    - multiply (vectorises) - unique integers > 1 at M's 1s and 0s at M's 0s
      Ẇ                  - non-empty sublists - i.e. row selections
       Z€                - transpose €ach
         Ẇ€              - non-empty sublists of €ach - column selections of those
           Ẏ             - tighten - a flat list of all of the rectangles
            ŒP           - power-set - all possible selections of rectangles
                   ÐṀ    - filter keep those for which the following is maximal:
                  $      -   last two links as a monad:
              F          -     flatten
                 $       -     last two links as a monad:
               Q         -       de-duplicate
                P        -       product
                     L€  - length of €ach - # of rectangles used by each full-cover
                       Ṃ - minimum

* 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)

Jonathan Allan
sumber
Akan FJṁ×⁸ẆZ€Ẇ€ẎŒPFQS$$ÐṀL€Ṃbekerja untuk -1? Tidak ada waktu untuk menguji rn.
Erik the Outgolfer
Tidak, karena penutup yang mengabaikan (hanya) yang dipaksakan untuk 1memiliki produk yang sama dengan penutup yang valid (mis. Putar delapan dengan lima contoh setengah putaran dan akan (secara teori) kembali 6karena akan mengabaikan untuk menutupi bagian atas -kiri sel dan anggap itu valid.)
Jonathan Allan
... lebih mudah - test case [[1,0],[0,1]]akan kembali 1daripada 2.
Jonathan Allan
1

JavaScript, 434 byte

Kode:

for(_='),d=...-1||(,Ad<=a,u[o][n]=d,    =0,(e,r,C,m))&&()=>.map((h((A,n,on<e|o<r|n>C|o>mf=u=>(q(s=(e>C[e,C]=[C,e]r>m[r,m]=[m,r]lk=1,k&=!!A)kl|=&1,=2k&lh=f=>uA,$ABf(B,$))))(($,Bae=r=C=m=,d=to-Bt=n$&n>$e   C=nn+1~ee   C=ttn-$t=oB&o>Br    m=oo+1~rr   m=tq+=sg=[],h((ca||g.push(c)gigb,j(p=1,q+=i<j&&s(b)q)';G=/[-]/.exec(_);)with(_.split(G))_=join(shift());eval(_)

Hexdump (karena karakter yang tidak patut dicetak):

66 6F 72 28 5F 3D 27 29 2C 13 13 64 3D 12 2E 2E 2E 11 2D 31 10 7C 7C 28 0F 2C 41 0F 64 3C 3D 0E 61 2C 0C 75 5B 6F 5D 5B 6E 5D 0B 3D 64 2C 09 3D 30 2C 08 28 65 2C 72 2C 43 2C 6D 07 29 29 13 06 26 26 28 05 29 3D 3E 04 2E 6D 61 70 28 28 03 68 28 28 41 2C 6E 2C 6F 04 02 02 6E 3C 65 7C 6F 3C 72 7C 6E 3E 43 7C 6F 3E 6D 0F 01 66 3D 75 3D 3E 28 71 08 28 73 3D 07 04 28 65 3E 43 05 5B 65 2C 43 5D 3D 5B 43 2C 65 5D 13 72 3E 6D 05 5B 72 2C 6D 5D 3D 5B 6D 2C 72 5D 13 6C 08 6B 3D 31 2C 01 6B 26 3D 21 21 41 29 13 6B 05 01 6C 7C 3D 0B 26 31 2C 0B 3D 32 06 6B 26 6C 13 68 3D 66 3D 3E 75 03 41 2C 24 04 41 03 0C 42 04 66 28 0C 42 2C 24 29 29 29 29 28 28 0C 24 2C 42 04 61 10 0F 65 3D 72 3D 43 3D 6D 3D 10 2C 64 3D 74 08 02 6F 2D 42 0F 74 3D 6E 0E 24 26 6E 3E 24 05 65 09 43 3D 6E 10 12 6E 2B 31 06 7E 65 0F 65 09 43 3D 74 12 74 08 02 6E 2D 24 0F 74 3D 6F 0E 42 26 6F 3E 42 05 72 09 6D 3D 6F 10 12 6F 2B 31 06 7E 72 0F 72 09 6D 3D 74 13 71 2B 3D 73 07 06 67 3D 5B 5D 2C 68 28 28 0C 11 63 04 61 10 7C 7C 67 2E 70 75 73 68 28 63 29 13 67 03 0C 69 04 67 03 62 2C 6A 04 28 70 3D 31 2C 71 2B 3D 69 3C 6A 26 26 73 28 11 0C 11 62 29 06 71 29 27 3B 47 3D 2F 5B 01 2D 13 5D 2F 2E 65 78 65 63 28 5F 29 3B 29 77 69 74 68 28 5F 2E 73 70 6C 69 74 28 47 29 29 5F 3D 6A 6F 69 6E 28 73 68 69 66 74 28 29 29 3B 65 76 61 6C 28 5F 29

Cobalah online!

Ini tidak terlalu golf, tetapi setidaknya itu bekerja sangat cepat. Semua kasus uji dapat dihitung dalam beberapa milidetik.

Tidak disatukan

f=mat=>(
  iterate=f=>mat.map((A,x)=>A.map((a,y)=>f(a,y,x))),
  fill=(x1,y1,x2,y2)=>(
    x1>x2&&([x1,x2]=[x2,x1]),
    y1>y2&&([y1,y2]=[y2,y1]),
    isFilled=0,

    canBeFilled=1,
    iterate((A,X,Y)=>X<x1|Y<y1|X>x2|Y>y2||(
      canBeFilled&=!!A
    )),

    canBeFilled&&(
      iterate((A,X,Y)=>X<x1|Y<y1|X>x2|Y>y2||(
        isFilled|=mat[Y][X]&1,
        mat[Y][X]=2
      ))
    ),

    canBeFilled&isFilled
  ),

  rectangles=0,

  iterate((a,x,y)=>a-1||(
    x1=y1=x2=y2=-1,

    start=end=0,
    iterate((A,X,Y)=>Y-y||(
      end=X,
      A||(
        start<=x&X>x&&(x1=start,x2=X-1),
        start=X+1
      )
    )),
    ~x1||(x1=start,x2=end),

    start=end=0,
    iterate((A,X,Y)=>X-x||(
      end=Y,
      A||(
        start<=y&Y>y&&(y1=start,y2=Y-1),
        start=Y+1
      )
    )),
    ~y1||(y1=start,y2=end),

    rectangles+=fill(x1,y1,x2,y2)
  )),


  ones=[],
  iterate((a,...c)=>a-1||ones.push(c)),
  ones.map((a,i)=>ones.map((b,j)=>(
    M=1,
    rectangles+=i<j&&fill(...a,...b)
  ))),

  rectangles
)

Penjelasan

Ini menggunakan algoritma yang sama seperti untuk memecahkan peta Karnaugh. Pertama ia mencoba untuk menemukan setidaknya satu 1yang 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 satu 0(atau akan melampaui batas matriks). Ketika 1ditemukan, temukan persegi panjang terbesar yang menyertakannya dan beri tanda semua 1pada persegi panjang itu. Ulangi sampai tidak ada lagi yang tidak ditandai 1yang memenuhi kondisi ini.

Dalam beberapa kasus (seperti dalam kasus uji 16) ada 1s yang tersisa setelah menerapkan langkah pertama. Kemudian sebutkan semua ini 1dan 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