Minimum rectangle cover

Question

Rectangle covers

Suppose you have a matrix of bits, for example the following.

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

We would like to find a rectangle cover for this matrix. It is a set of rectangular subsets of the matrix that don't contain any 0s, but together contain all the 1s. The subsets are not required to be disjoint. Here is an example of a rectangle cover for the above matrix.

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

The number of rectangles in this cover is 7.

The task

Your input is a rectangular matrix of bits, taken in any reasonable format. You can assume it contains at least one 1. Your output is the minimum number of rectangles in a rectangle cover of the matrix.

The lowest byte count wins. Standard code-golf rules apply.

Test cases

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

Answer 1

Python 2, 318 315 271 bytes

Mr.Xcoder, ovs and Jonathan Frech saved a lot of bytes

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

Try it online!

Answer 2

Jelly,  25  24 bytes

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

Try it online! A typical golf-complexity solution, don't even bother with larger test cases, they will time out (the power set of all possible rectangles is inspected*)

How?

Forms all the possible rectangles that may be made. Takes the power-set of those rectangles and inspects them only keeping those sets which both contain no zeros and contain each of the ones at least once.

To achieve the "keeping those sets which both contain no zeros and contain each of the ones at least once" part the code first coerces the ones to a set of distinct integers greater than one, leaving the zeros as they are so that it becomes "finding the maxima of the product of the unique values".

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

---

_{* For an n by m matrix that's ways(n,m) = 2^(T(n)×T(m)), so...
ways(3,2) = 2^((3+2+1)×(2+1)) = 2^18 = 262,144 (the TIO link)
ways(3,3) = 2^((3+2+1)×(3+2+1)) = 2^36 = 68,719,476,736
ways(3,4) = 2^((3+2+1)×(4+3+2+1)) = 2^60 = 1,152,921,504,606,846,976
ways(5,5) = 2^225 ~= 5.4e+67 (the largest test case)
ways(8,5) = 2^540 ~= 3.6e+162 (the example)}

Answer 3

JavaScript, 434 bytes

Code:

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 (because of unprintable characters):

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

Try it online!

It is not very golfy, but at least it works very fast. All test cases can be computed in few milliseconds.

Ungolfed

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
)

Explanation

It uses similar algorithm like for solving Karnaugh maps. Firstly it tries to find at least one 1 which can be part of exactly one non-extensible rectangle. By non-extensible I mean if we extend it in any direction (up, left, right, down) it will include at least one 0 (or will go beyond the matrix bounds). When such 1 is found, find the biggest rectangle that includes it and flag all 1s in that rectangle. Repeat until there is no more non-flagged 1s that satisfy these conditions.

In some cases (like in the 16th test case) there are 1s that left over after applying the first step. Then enumerate all these 1s and apply some kind of enhanced brute-force search. This step is rarely applied, and even in these cases, we need to brute-force check only one or two combinations, so it should work very fast even for larger test cases.

Answer 4

Python 3+Numpy, 253 bytes

from numpy import*
from itertools import*
R=range
P=product
def f(A):s=A.shape;r=random.rand(*s);return[N for N in R(1,sum(A)+1)for m in P(*[[(A*r)[a:b+1,c:d+1]for a,c,b,d in P(*[*map(R,s)]*2)]]*N)if len({e*all(b)for b in m for e in b.flat})==sum(A)][0]

Try it online!

This is quite slow due to generating more than the full power set of all rectangles. I also have an optimized version to test the slower test cases, which makes three optimizations:

• Uses combinations of N rectangles instead of cartesian product to avoid duplicate rectangles
• Uses next(...) instead of [...][0] to terminate as soon as a single covering is found with minimal number of rectangles
• Prunes out rectangles that are subsets of larger rectangles containing only 1s (96% reduction in rectangles for the largest test case)

Semi-ungolfed

from numpy import*
from itertools import*
R=range
# P is the itertools product
P=product

def f(A):
    # take input as a numpy array A
    s = A.shape;
    # r is a weight matrix that gives a distinct value to each entry in A
    # (probability 1)
    # Longer alternative (can be inlined): r=~reshape(range(h*w),(h,w))
    r = random.rand(*s);
    return [
        # We're finding number of rectangles N
        N
        # In the range [1..sum(A)] where sum(A) is the number of 1s (upper bound for # rectangles)
        for N in R(1, sum(A)+1)
        # m is a combination of N possible rectangles
        for m in P(
            # (this is Cartesian product instead of combinations, but duplicates
            # provide no benefit)
            # P(*[...]*N) === product(..., repeat=N)
            *[
                [
                    # A*r is modified array such that each 1 is given
                    # a distinct value and all 0s remain 0

                    # all rectangles in A*r
                    (A*r)[a:b+1, c:d+1]
                    for a,c,b,d in P(*[*map(R,s)]*2)
                ]
            ]*N
        )
        # Test that each rectangle contains no 0s and the combination of rectangles covers all 1s:
        if len({e*all(b) for b in m for e in b.flat})==sum(A)
    # Get the first N with a valid covering
    # must be min N because N is generated in order
    ][0]