Minimum cost block diagonalisation

Question

Consider binary block diagonal matrices which have square blocks of 1s on the main diagonal, and are 0 everywhere else. Let's call such matrices "valid" matrices.

For example, here are some valid 4x4 matrices:

1 0 0 0     1 1 0 0     1 0 0 0     1 0 0 0     1 1 0 0    1 1 1 1
0 1 0 0     1 1 0 0     0 1 1 0     0 1 1 1     1 1 0 0    1 1 1 1
0 0 1 0     0 0 1 0     0 1 1 0     0 1 1 1     0 0 1 1    1 1 1 1
0 0 0 1     0 0 0 1     0 0 0 1     0 1 1 1     0 0 1 1    1 1 1 1

Note that an alternative way of describing such matrices is that there is a chain of square 1 blocks from the top-left to the bottom-right, touching corner to corner, and everywhere else is 0.

For contrast, here are some invalid 4x4 matrices:

1 0 1 0     1 0 1 0     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 1 1 1     0 1 0 1     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
1 0 0 1     1 0 1 0     0 0 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 0 1 0     0 1 0 1     0 0 0 1     1 0 0 0     0 0 1 1    0 0 0 0

You will be given an n by n binary matrix as input – what is the minimum number of 0 bits you'll need to set to 1 in order to get a valid matrix?

You may write a function or program taking in any convenient string, list or matrix format representing an n by n matrix of 0s and 1s (as long as it isn't preprocessed). Rows must be clearly separated in some way, so formats like a 1D array of bits are not allowed.

This is code-golf, so the goal is to minimise the number of bytes in your program.

Examples

For example, if the input is

0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1

then the answer is 5, since you can set five 0 bits to 1 to get:

1 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 1 0
0 0 0 0 1

and this is the minimum number required. However, if the input was

0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

then the answer is 24, since the only valid 5x5 matrix where the top-right is 1 is the matrix of all 1s.

Test cases

Tests are represented here as a 2D array of integers.

[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

Notes

• Related challenge: Print a Block-Diagonal Matrix
• Inspiration: Freedom Factory, Google Code Jam 2016 Problem 2D

Answer 1

MATL, 46 43 bytes

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

Input is a 2D array with semicolon as row separator. For example, the input for the last test case is

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Try it online! Or verify all test cases (code slightly modified to take all inputs; the results appear after a few seconds)

Explanation

Let the input be an N×N matrix. The code first computes all (N+1)-tuples of block sizes that produce the appropriate matrix size. For example, for N=4 the tuples are 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. For each tuple it builds the block-diagonal matrix with those block sizes. It then checks if the matrix covers all the 1 entries in the input, and if so takes note of the number of 1 entries that were not present in the input. The final result is the minimum of all the obtained numbers.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each 
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display

Answer 2

Python with numpy, 102

from numpy import*
lambda M:sum(diff([k for k in range(len(M)+1)if(M|M.T)[:k,k:].any()-1])**2)-M.sum()

An efficient algorithm. Finds the "neck points" on the diagonal that can separate blocks. These have all 0's above and right, as well as below and left. The minimal blocks are those between neck points.

??000
??000
00???
00???
00???

The length of a block is the difference between consecutive neck points, so their total area of the sum of squares of these. Subtracting the sum of the original matrix then gives the number of flips needed from 0 to 1.

Answer 3

Pyth, 45 bytes

[email protected]^+LsYN2d+0._ds.pM./lQss

Difficult task, so it's quite long.

Try it online: Demonstration or Test Suite

Explanation:

s.pM./lQ computes all integer partitions of len(matrix). ms.b^+LsYN2d+0._d converts them into coordinate-pairs. For instance the partition [1, 2, 2] of 5 gets converted into [[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4].

[email protected] then filters for partitions, that completely overlap the matrix (.DRlQx1sQ computes all coordinate-pairs of the active cells in the matrix).

-hSlM...ss counts the cells of each remaining partitions, chooses the one with the least cells, and subtracts the already active cells.

Answer 4

Matricks, 180 bytes (noncompeting)

Matricks is a new esolang I created very recently to deal with matrix problems (such as this one), by only having 2 data types: floats and matricies. It is not fully featured yet, and still has a lot of missing operations (I had to add some functionality for this challenge). Anyway, here's the code:

il=1:j3;:bdx;;;s1::L;j1;;
b{q:1;mgr:c;|gc:r;|(r=c)|(gr-1:c;|gr:c+1;)&(rec)|(gr+1:c;|gr:c-1;)&(cer):l:L;};z:(l-1)/2;B1;s1::g1:;-1;ig1:;=0:j2;:j1;;
s1::d{q:1;};;kg1:;-g:;;
kg:;*-1+1;

Explanation

The first part, il=1:j3;:...; checks if the array is of size 1. If it is, it jumps to the last line, kg:;*-1+1;, which is a simple 0 <-> 1 function.

Otherwise, it continues on with the rest of the code. bdx;;; sets the cell 0,0 to the current sum, and s1::L;j1; creates a counter in the cell in the row below.

The next line is a bit more complicated. It is a loop that runs n times, n being the size of the matrix. I'll use the 3rd test case as an example. When we first get to the second line, the matrix looks like this:

1 0 1
2 0 0

First, we go into the matrix comprehension {q:1;m...;}. This makes the diagonal, and tries its best to clean up 0 that need filling in. All this is accomplished using simple boolean operators. Then, we prepend it to the current matrix, giving this:

    V--data we want to keep
1 1 1 0 1 <-|
1 1 2 0 0 <-- old matrix

Then, we cut of the old matrix using z:(l-1)/2;, and rotate the entire matrix to the left using B1;. That gives us a matrix ready for the next iteration, looking like:

1 1 1
2 1 1

Finally, we decrement the counter, check it, and continue with ig1:;=0:j2;:j1;;

Once the loop is broken out of, we find the new sum and set the counter's old spot with s1::d{q:1;};;. Finally, we take the difference and return kg1:;-g:;;. k sets the current array to a value, and printing is implicit.

...

As you can see, Matricks is pretty verbose, and not a very good golfing language. But heck, I wanted to show it off.