22
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – officialaimm Jan 23 '17 at 9:22
  • 4
    \$\begingroup\$ @officialaimm No, that is not valid. The grid lines must run from one side of the array all the way to the other side. \$\endgroup\$ – Zgarb Jan 23 '17 at 9:30
  • \$\begingroup\$ Proposed test case: [[1, 0, 1], [0, 1, 0], [1, 0, 0]] That was the only 3x3 matrix my new approach was failing for. \$\endgroup\$ – Dennis Jan 26 '17 at 1:03
  • \$\begingroup\$ @Dennis Thanks, added. \$\endgroup\$ – Zgarb Jan 26 '17 at 8:51
7
\$\begingroup\$

Pyth, 30 29 26 24 23 bytes

sm.Asmmq1ssbCkds./MC./M

Try it online.

I'm sure this will get shorter. This is O(2mn), where m and n are the width and height of the array, but completes the last two test cases in 45 seconds on my laptop on battery (i5-5200U with limited performance).

Outputs the number of solutions.

Explanation

Five-dimensional arrays are really fun to work with.</sarcasm> You are not supposed to understand how this works even with the explanation.

                    ./M    Find all partitions of each row. Now we have a list of rows,
                           each containing the ways to split the row, each containing
                           the parts of the split (3D).
                   C       Transpose. Now we have a list of ways to split the columns,
                           each containing the rows, each containing the parts of the
                           row (3D).
                ./M        Find all partitions of each row list. Now we have a list of
                           ways to split the columns, each containing the ways to split
                           the rows, each containing the bunch of rows, each containing 
                           the rows in the bunch, each containing the parts of the row
                           (6D).
               s           Combine the ways to split rows & columns into one array (5D).
 m            d            Do the following for each way to split rows & columns (4D):
     m       k                 Do the following for each bunch of rows (3D):
            C                      Transpose the array. We now have a list of column
                                   groups, each containing the row parts (3D).
      m    b                       Do the following for each column group (2D):
          s                            Combine the row parts in the column group. We now
                                       have the list of cells in this row/column group
                                       (1D).
         s                             Sum the cells.
       q1                              Check if the sum is one.
                                   We now have the list of booleans that tell if each
                                   row/column group is valid (1D).
                               We now have the 2D list of booleans that tell if each
                               row/column group in each bunch of rows is valid. (2D)
    s                          Combine the 2D list of booleans to 1D.
  .A                           Check if all values are truthy; if the split is valid.
                           We now have the validity of each split.
s                          Sum the list to get the number of valid solutions.
\$\endgroup\$
3
\$\begingroup\$

Jelly, 22 bytes

ŒṖḅ1S€€=1Ȧ€
SŒṖ⁸ṁþÇ€FS

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Haskell, 116 bytes

import Data.List
m(a:b)=[a:e|e<-m b]++[zipWith(+)a d:e|d:e<-m b];m e=[e]
d=(any$any$all$all(==1)).map(m.transpose).m

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ This does not compile. Please delete your answer until it is fixed. There is also a lot of golfing potential, eg. renaming mergerows to m. \$\endgroup\$ – Laikoni Jan 23 '17 at 20:12
  • \$\begingroup\$ I was planning to run out of competition due to the hard-to-beat Pyth brevity and thank thee @Laikoni for spotting I likely messed up my indentation braces. \$\endgroup\$ – Roman Czyborra Jan 23 '17 at 20:46
  • 2
    \$\begingroup\$ This incorrectly gives False on [[1,0],[0,1],[1,0]]. The problem is that a greedy collapse can get in the way of a later better collapse. \$\endgroup\$ – xnor Jan 23 '17 at 22:03
  • \$\begingroup\$ Indeed, my [[1,1],[1,0]] collapse falsely obstructs the [[1],[1],[1]] solution. Let me sleep over this or ought i delete? \$\endgroup\$ – Roman Czyborra Jan 23 '17 at 22:17
  • 1
    \$\begingroup\$ I count 116 bytes. \$\endgroup\$ – Zgarb Jan 25 '17 at 10:58
1
\$\begingroup\$

Jelly, 20 bytes

ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS

This is still a brute-force solution, but it's quite a bit faster than my other answer – which cannot cope with the last two test cases on TIO – and handles all test cases in ~4 seconds.

Try it online!

How it works

ŒṖS€€ỊȦ$ÐfZ€µ⁺€Ȧ€€FS  Main link. Argument: M (matrix, array of rows)

ŒṖ                    Compute all partitions, i.e., all groupings of M's rows.
  S€€                 Map sum over all individual groupings, collapsing the grouped
                      rows into a single row.
        Ðf            Filter; keep only those partially collapsed matrices for
                      which the link to the left returns a truthy value.
       $                Group the two links to the left into a monadic chain.
     Ị                    Insignificant; map 0 and 1 to 1, greater integers to 0.
      Ȧ                   All; return 1 iff the matrix contains no zeroes.
          Z€          Zip/transpose all kept matrices,
            µ         Combine all links to the left into a monadic chain.
             ⁺€       Duplicate the chain and map it over the individual results
                      from the first call. We now have all possible combinations
                      of row and column groupings (represented by the corresponding
                      matrices of collapsed rows and columns) that do not have a
                      2 anywhere. However, they still may contain zeroes.
               Ȧ€€    Map the all atom over the matrices, returning 1 only for
                      matrices that consist entirely of ones.
                  FS  Flatten and sum, counting the number of valid divisions.
\$\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.