22
1
Introduction
There is a small village with nothing but a few houses and empty fields. The local bureaucrats want to divide the village into lots so that each lot contains exactly one house, and the borders of the lots form a nice straight-line grid. Your task is to determine whether this is possible.
The task
Your input is a rectangular 2D array of bits; 1 represents a house and 0 an empty field. Its size will be at least 1×1, and it will contain at least one 1. You can take the input in any reasonable format (nested list of integers, list of strings, multiline string etc).
Your program shall determine whether the array can be divided into grid cells using straight horizontal and vertical lines so that each grid cell contains exactly one 1. The grid cells may have different sizes and shapes, although they will always be rectangular. The lines must run from one edge of the array to the opposite edge.
For example, the following is a valid division of an array:
00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1
whereas the following division is not valid, since there are grid cells with no 1s or more than one 1:
00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1
If a valid division exists, you shall output a truthy value, and otherwise a falsy value.
Rules and scoring
You can write a full program or a function. The lowest byte count wins.
Test cases
[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True
can [ [0,0,1,0,1] , [1,0,0,1,0] , [0,0,0,1,0] ] be divided into: 3X1, 2X1, 3X2, 2X1, 2X1 rectangles in this manner or not? 001|01 ---+-- 100|10 +-- 000|10 – officialaimm – 2017-01-23T09:22:52.077
4@officialaimm No, that is not valid. The grid lines must run from one side of the array all the way to the other side. – Zgarb – 2017-01-23T09:30:48.343
Proposed test case:
[[1, 0, 1], [0, 1, 0], [1, 0, 0]]
That was the only 3x3 matrix my new approach was failing for. – Dennis – 2017-01-26T01:03:27.117@Dennis Thanks, added. – Zgarb – 2017-01-26T08:51:11.093