23
2
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
Is this inspired by Karnaugh map?
– None – 2017-11-11T14:56:20.1971
@ThePirateBay More by nondeterministic communication complexity.
– Zgarb – 2017-11-11T15:01:56.970@ThePirateBay for a k-map all the rectangles should have power-of-two dimensions. – Sparr – 2017-11-11T22:32:29.913
@Sparr. Yes, I know it. I just asked was it maybe the inspiration for this challenge. – None – 2017-11-11T22:38:09.293
1Useful test case for greedy approaches:
[[0,1,0,0],[0,1,1,1],[1,1,1,0],[0,0,1,0]]
, 4. – isaacg – 2017-11-11T23:16:32.880Note that this Rectilinear Image Compression problem is known to be NP-hard (Garey & Johnson, SR25). – Eric Towers – 2017-11-12T05:48:55.917