Osłony prostokątne

Załóżmy, że masz macierz bitów, na przykład następujące.

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

Chcielibyśmy znaleźć prostokątną osłonę dla tej matrycy. Jest to zestaw prostokątnych podzbiorów macierzy, które nie zawierają żadnych zer, ale razem zawierają wszystkie jedynki. Podzbiory nie muszą być rozłączne. Oto przykład prostokątnej pokrywy dla powyższej matrycy.

+----+         +----+
|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|
+----+   +-------+   +-+

Liczba prostokątów w tej okładce wynosi 7.

Zadanie

Twój wkład to prostokątna matryca bitów, wykonana w dowolnym rozsądnym formacie. Możesz założyć, że zawiera co najmniej jeden 1. Twój wynik to minimalna liczba prostokątów w prostokątnej pokrywie matrycy.

Wygrywa najniższa liczba bajtów. Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

[[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

Python 2 , 318 315 271 bajtów

Mr.Xcoder, ovs i Jonathan Frech zaoszczędzili wiele bajtów

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

Wypróbuj online!

Galaretka ,  25  24 bajtów

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

Wypróbuj online! Typowe rozwiązanie o złożoności golfowej, nawet nie zawracaj sobie głowy większymi przypadkami testowymi, przekroczą limit czasu (sprawdzany jest zestaw mocy wszystkich możliwych prostokątów *)

W jaki sposób?

Tworzy wszystkie możliwe prostokąty, które można wykonać. Pobiera zestaw mocy tych prostokątów i sprawdza je, zachowując tylko te zestawy, które nie zawierają zer i zawierają przynajmniej jeden z nich.

Aby osiągnąć „zachowanie tych zbiorów, które oba nie zawierają zer i które zawierają przynajmniej jeden z nich”, kod najpierw wymusza je na zestawie odrębnych liczb całkowitych większych niż jeden, pozostawiając zera takimi, jakimi są, aby stał się „ znajdowanie maksimów iloczynu unikalnych wartości ".

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

_{* Dla macierzy n na m , czyli sposobów (n, m) = 2 ^ (T (n) × T (m)) , więc ...
sposoby (3,2) = 2 ^ ((3 + 2 + 1) × (2 + 1)) = 2 ^ 18 = 262,144 (łącze TIO)
sposoby (3,3) = 2 ^ ((3 + 2 + 1) × (3 + 2 + 1)) = 2 ^ 36 = 68 739 476,736
sposoby (3,4) = 2 ^ ((3 + 2 + 1) × (4 + 3 + 2 + 1)) = 2 ^ 60 = 1,152,921,504,606,846,976
sposoby (5,5) = 2 ^ 225 ~ = 5,4e + 67 (największy przypadek testowy)
sposoby (8,5) = 2 ^ 540 ~ = 3,6e + 162 (przykład)}

JavaScript, 434 bajty

Kod:

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 (z powodu znaków niedrukowalnych):

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

Wypróbuj online!

Nie jest bardzo golfowy, ale przynajmniej działa bardzo szybko. Wszystkie przypadki testowe można obliczyć w kilka milisekund.

Bez golfa

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
)

Wyjaśnienie

Używa podobnego algorytmu jak przy rozwiązywaniu map Karnaugh. Po pierwsze, próbuje znaleźć co najmniej jeden, 1który może być częścią dokładnie jednego nierozciągliwego prostokąta. Przez nierozszerzalny rozumiem, jeśli rozciągniemy go w dowolnym kierunku (w górę, w lewo, w prawo, w dół), będzie on zawierał przynajmniej jeden 0(lub przekroczy granice macierzy). Kiedy taki 1zostanie znaleziony, znajdź największy prostokąt, który go zawiera i oznacz wszystkie 1s w tym prostokącie. Powtarzaj, aż nie będzie już żadnych nieoznaczonych flag, 1które spełniają te warunki.

W niektórych przypadkach (jak w 16 przypadku testowym) pozostały takie, 1które pozostały po zastosowaniu pierwszego kroku. Następnie wylicz wszystkie te 1i zastosuj jakieś ulepszone wyszukiwanie z użyciem siły brute. Ten krok jest rzadko stosowany, a nawet w tych przypadkach musimy sprawdzić brutalną siłę tylko jedną lub dwie kombinacje, więc powinien działać bardzo szybko, nawet w przypadku większych przypadków testowych.