23
\$\begingroup\$

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 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
\$\endgroup\$
  • \$\begingroup\$ Is this inspired by Karnaugh map? \$\endgroup\$ – user72349 Nov 11 '17 at 14:56
  • 1
    \$\begingroup\$ @ThePirateBay More by nondeterministic communication complexity. \$\endgroup\$ – Zgarb Nov 11 '17 at 15:01
  • \$\begingroup\$ @ThePirateBay for a k-map all the rectangles should have power-of-two dimensions. \$\endgroup\$ – Sparr Nov 11 '17 at 22:32
  • \$\begingroup\$ @Sparr. Yes, I know it. I just asked was it maybe the inspiration for this challenge. \$\endgroup\$ – user72349 Nov 11 '17 at 22:38
  • 1
    \$\begingroup\$ Useful test case for greedy approaches: [[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]], 4. \$\endgroup\$ – isaacg Nov 11 '17 at 23:16
6
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Would FJṁ×⁸ẆZ€Ẇ€ẎŒPFQS$$ÐṀL€Ṃ work for -1? No time to test rn. \$\endgroup\$ – Erik the Outgolfer Nov 11 '17 at 22:44
  • \$\begingroup\$ No, because a cover that neglected (only) the one coerced to 1 would have the same product as a valid cover (e.g. turn the eight by five example half a turn and it would (in theory) return 6 as it would neglect to cover the top-left cell and consider it valid.) \$\endgroup\$ – Jonathan Allan Nov 11 '17 at 23:07
  • \$\begingroup\$ ...even easier - the test case [[1,0],[0,1]] would return 1 rather than 2. \$\endgroup\$ – Jonathan Allan Nov 11 '17 at 23:13
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.