# Matrices Generated Using Rectangles

Input is an r by c matrix of non-negative integers (you may input r and c as other parameters if this helps with golf). This may be inputted as a 2D array or, if you prefer, a 1D array (though taking in r this time is necessary). Strings separated by spaces to distinguish rows and newlines to distinguish columns are also fine (below, the test cases have multiple spaces to distinguish rows for clarity -- you do not have to do this).

Consider a matrix of zeros. A move consists of replacing a rectangle of numbers with a rectangle of some positive integer (not zero). For example, these are all valid first moves:

0 0 0 0
0 2 0 0
0 0 0 0
0 0 0 0

0 3 0 0
0 3 0 0
0 3 0 0
0 3 0 0

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


These are not valid first moves:

0 0 0 0
0 2 0 0
0 0 0 0
0 2 0 0

0 1 0 0
0 2 0 0
0 0 0 0
0 0 0 0

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0


Make golfed code to answer the following the question:

Given an r by c matrix, what is the smallest possible number of turns taken to construct this?

### Test Cases:

1 1 1 1
1 2 2 2
1 2 3 3
1 2 3 4
1 2 3 4
> 4

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
> 15

3 3 3 3 3 3
3 2 2 2 2 3
3 2 1 1 2 3
3 2 1 1 2 3
3 2 2 2 2 3
3 3 3 3 3 3
> 3

1 1 1 1 1 1
1 2 2 2 2 1
1 2 0 0 2 1
1 2 0 0 2 1
1 2 2 2 2 1
1 1 1 1 1 1
> 8

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
> 0

1 1 1 1
1 3 3 1
2 3 3 2
2 2 2 4
> 4

• This seems like a very, very hard problem to compute efficiently to me.
– orlp
Commented Jan 27, 2018 at 15:03
• This is a harder variation of this challenge. Commented Jan 29, 2018 at 9:26
• Based on your examples of first moves I guess the numbers aren't inputted in order? None of your test cases reflect that, though. The test cases all go from 1 upwards (first test case four movies: 1,2,3,4; second test case 15 moves: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15; third test case 3 moves: 1,2,3; fourth test case 8 moves: 1,1,1,1,2,2,2,2). (It does make the challenge easier if only the same or next numbers can be inputted in that order. But if that's not your intention, you could for example swap the 1s and 3s in the third test case to reflect this.) Commented Mar 2, 2018 at 8:18
• What is the answer for [[1,1,1,1], [1,3,3,1], [2,3,3,2], [2,2,2,3]]? (In other words, can a rectangle be placed over different numbers?) Commented Mar 23, 2019 at 17:06
• Can you add a test case where the optimal solution requires multiple rectangles with the same number for a reason other than interfering zeros? For example, [[1,1,2,2],[1,1,2,2],[2,2,1,1],[2,2,1,1]] should take 3 rectangles. Commented Aug 24, 2019 at 22:35

# Python 2, 333 bytes

lambda g,l=len:min(i for i in r(l(g)*l(g[0])+1)if g in o(l(g[0]),l(g),[[0]*l(g[0])for _ in" "*l(g)],set(sum(g,[])),i))
o=lambda w,h,g,s,I:I and sum([o(w,h,n,s,I-1)for n in[[[x<=j<=X<[]>Y>=i>=y and S or E for j,E in e(R)]for i,R in e(g)]for x in r(w)for X in r(x,w)for y in r(h)for Y in r(y,h)for S in s]],[])or[g]
r=range
e=enumerate


Try it online!

This only works in theory, because in practice, it takes way too long if you have more than about 5 elements in the grid.

Since this is , I apologize for the inefficiency, but efficiency would require more thought and FAR more bytes.

This code does the same thing at the cost of 5 bytes, but short-circuits, meaning that a larger grid with a small answer may finish somewhat earlier... the difference in viable search space is negligible, but just in case you wanted to test it a bit more.

The reason this is so slow is because it looks from $$\0\$$ up to $$\W\times H\$$, generating every possible $$\W\times H\$$ grid that can be achieved with the elements of the grid with that many steps being used.

# Python3, 1288 bytes

Long, but crunches the test cases in under a second.

R=range
E=enumerate
M=[(1,0),(-1,0),(0,-1),(0,1)]
def D(b):
for x,j in E(b):
for y,_ in E(j):
for X in R(x,len(b)):
for Y in R(y,len(b[0])):yield[(u,i)for u in R(x,X+1)for i in R(y,Y+1)]
def r(b):
S={(x,y)for x,j in E(b)for y,_ in E(j)if _ not in['0']}
W={*S}
while S:
x,y=[(x,y)for x,y in S if b[x][y]!='-'][0];S=S-{(x,y)};d,s={x:[y]},[(x,y)]
V=b[x][y]
q=[(x,y)]
while q:
x,y=q.pop(0)
F=1
for X,Y in M:
J,K=x+X,y+Y
if(J,K)in S and(b[J][K]==V or'-'==b[J][K]):F=0;q+=[(J,K)];S=S-{(J,K)};d={**d,J:sorted(d.get(J,[])+[K])};s=s+[(J,K)]
if all(b==d[min(d)]for b in d.values()):yield s
def Z(B,s,i):
B=eval(str(B))
for x,y in s:B[x][y]=i
return B
V=lambda W,c,S,U:(W==-1 or c+1<W)and all(C>c for C,u in S if u==U)
def f(b):
q,S=[(b,0)],[(0,b)]
L=[i for i in D(b) if i]
W=-1
while q:
B,c=q.pop()
if all(not({*i}-{'-','0'})for i in B):W=c if W==-1 else min(W,c);continue
H=[*r(B)]
for i in H:
U=Z(B,i,'-')
if V(W,c,S,U):
q+=[(U,c+1)];S+=[(c,U)]
if len({sum(B[x][y]!='-'for x,y in j)for j in H})==1:break
U=Z(B,max([i for i in L if len(T:={B[x][y]for x,y in i})<3 and{'-'}!=T and'0'not in T and(len(T)==1 or'-'in T)],key=lambda X:sum(B[x][y]not in{'-','0'}for x,y in X)),'-')
if V(W,c,S,U):q+=[(U,c+1)];S+=[(c,U)]
return W


Try it online!