Partition and Restructure

Question

Given two contiguous shapes of the same area, determine the optimal way to divide the first shape into a minimum number of contiguous segments such that they can be rearranged to form the second shape. In other words, find the minimum number of segments required that can form both of the shapes.

"Contiguous" means that every square in the shape can be reached from any other square by walking across edges. Shapes and segments are allowed to have holes.

"Rearrange" means you move the segments around; you can translate, rotate, and reflect them.

The shapes are contained on a grid; in other words, each shape consists of a collection of unit squares joined by their corners/edges.

Input Specifications

The input will be provided in some reasonable format - list of points, array of strings representing each grid, etc. You can also take the sizes of the grid if requested. The grids will have the same dimensions and the two shapes are guaranteed to have the same area, and the area will be positive.

Output Specifications

The output should just be a single positive integer. Note that there will always be a positive answer because in the worst case scenario, you just divide the shapes into N unit squares.

Examples

The examples are presented as a grid with . representing a blank and # representing part of the shape.

Case 1

Input

.....
.###.
.#.#.
.###.
.....

###..
..#..
..#..
..###
.....

Output

2

Explanation

You can divide it into two L-shaped blocks of 4:

#
###

Case 2

Input

#...
##..
.#..
.##.

.##.
####
....
....

Output

2

Explanation

You can split the shapes like so:

A...
AA..
.A.
.BB.

.AA.
BBAA
....
....

You could also do:

A...
AA..
.B..
.BB.

.AB.
AABB
....
....

Case 3

Input

#....#
######

.####.
.####.

Output

2

Explanation

A....B
AAABBB

.ABBB.
.AAAB.

(This test case demonstrates the necessity to rotate/reflect shapes for optimal output)

Case 4

Input

.###.
..#..

.##..
.##..

Output

2

Explanation

No matter how you select blocks, selecting a 2x1 from the first shape necessarily prevents the other two from being grouped together; thus, you can use one 2x1 and two 1x1s. However, (thanks @Jonah), you can split it into a 3-block L shape and a single square like so:

.AAB.
..A..

.AA..
.BA..

Case 5

Input

##
#.

#.
##

Output

1

Explanation

The input and output shapes may be identical.

Case 6

Input

#..
##.
.##

#####

Output

3

Explanation

There is no way to divide the original shape into two pieces such that both pieces are straight, so at least three are needed.

Answer 1

Python 3.6, 799 791 bytes

7 bytes saved by Jonathan Frech and motavica

B=frozenset
M=min
X={}
T=lambda s:((x,y)for y,x in s)
N=lambda s:B((x-M(s)[0],y-M(T(s))[0])for x,y in s)
G=lambda s:{(x,y):s&{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}for(x,y)in s}
C=lambda g,s,i=0:i<=len(g)and(len(g)==len(s)or C(g,s.union(*map(g.get,s)),i+1))
F=lambda s:N([(-x,y)for x,y in s])
P=lambda s,i=4:M([N(s),F(s),P(F(T(s)),i-1)],key=list)if i else s
S=lambda s,t=B(),i=0:t|S(s,B().union(u|{p}for u in t for p in s-u if C(G(u|{p}),{p}))if i else B([B([next(iter(s))])]),i+1)if-~i<len(s)else t
def U(s):
 k=P(s)
 if k in X:return
 j=[t for t in S(k)if C(G(k-t),{next(iter(k-t))})];X[k]={P(t):B()for t in j}
 for t in j:X[k][P(t)]|=B([B(P(k-t))]);U(t);U(k-t)
V=lambda s,t:1+M(V(v,w)for u in B(X[s])&B(X[t])for v in X[s][u]for w in X[t][u])if s^t else 1
A=lambda s,t:U(s)or U(t)or V(P(s),P(t))

Try it online!

Usage

A(s, t) takes in two shapes where each shape is given by a list of x, y grid positions.

A helper function to convert the graphical representation to a list of positions is below:

def H(g):
 g=g.split("\n")
 return[(x,y)for x in range(len(g[0]))for y in range(len(g))if"#"==g[y][x]]

Example:

case1_1 = \
""".....
.###.
.#.#.
.###.
....."""

case1_2 = \
"""###..
..#..
..#..
..###
....."""

print(A(H(case1_1), H(case1_2))) # Prints 2

Explanation

The algorithm used here is a little better than brute force by caching sub-shapes. For a given shape, it caches all the ways to split that shape into two contiguous shapes, I then normalise these shapes (shift the coordinates so it starts at the origin, then find a rotation/reflection of it which is used in the cache) and store them in the cache to look up quickly later. All sub-shapes then have their sub-shapes cached as well until it gets to the single block shape.

These sub-shapes are generated by converting it to a graph adjacency list and using a BFS to generate all sub-graphs. We can then filter these subgraphs to ones where the vertices which weren't included are a connected component. Determining whether the graph is connected is done with another BFS.

After the cache is complete, the solution is found by comparing the two shapes to find the sub-shapes that it has in common. Once it has these list of sub-shapes, it takes the pair of sub-shapes left over after removing the common shape and recursively applies the same algorithm again to find the minimum number of blocks needed to reconstruct the shape. This then returns the sub-shape with the minimum of all those values and we have our solution.

I've put an annotated version below to kinda explain what each line is doing.

B=frozenset
M=min
# Shapes are stored as a frozenset of tuples where each tuple represents an (x, y) position
# Cache of shape partitions. This is a two-level dictionary where the outer key is a shape, and the inner key is a sub-shape where the value is a list of the shapes left when the sub-shape is removed.
# there may be multiple shapes in the inner-most list if the sub-shape appears multiple times
X={}
# Transpose list of coords (flip around diagonal axis)
T=lambda s:((x,y)for y,x in s)
# Translate shape so its upper-left corner is at the origin
N=lambda s:B((x-M(s)[0],y-M(T(s))[0])for x,y in s)
# Convert shape to graph in adjacency list form
G=lambda s:{(x,y):s&{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}for(x,y)in s}
# Check if graph is connected given a set of nodes, s, known to be connected
C=lambda g,s,i=0:i<=len(g)and(len(g)==len(s)or C(g,s.union(*map(g.get,s)),i+1))
# Flip shape around vertical axis
F=lambda s:N([(-x,y)for x,y in s])
# Converts shape to the minimal reflection or rotation. rotation is equivalent to transpose then flip.
P=lambda s,i=4:M([N(s),F(s),P(F(T(s)),i-1)],key=list)if i else s
# returns all the contiguous sub-shapes of s that contain the first pos, given by next(iter(s))
S=lambda s,t=B(),i=0:t|S(s,B().union(u|{p}for u in t for p in s-u if C(G(u|{p}),{p}))if i else B([B([next(iter(s))])]),i+1)if-~i<len(s)else t
# updates the sub-shape cache, X, recursively for an input shape s 
def U(s):
 k=P(s)
 if k in X:return
 j=[t for t in S(k)if C(G(k-t),{next(iter(k-t))})];X[k]={P(t):B()for t in j}
 for t in j:X[k][P(t)]|=B([B(P(k-t))]);U(t);U(k-t)
# Gets the minimum number of partitions for two shapes
V=lambda s,t:1+M(V(v,w)for u in B(X[s])&B(X[t])for v in X[s][u]for w in X[t][u])if s^t else 1
# The function to run, will update the cache for the two input shapes then return the minimum number of partitions
A=lambda s,t:U(s)or U(t)or V(P(s),P(t))

Answer 2

Python3, 788 bytes:

import itertools as I
E=enumerate
R=lambda x,n=4:set()if n==0 else{str(x),*R([i[::-1]for i in zip(*x)],n-1)}
S=lambda t:{(x,y)for x,k in E(t)for y,p in E(k)if p}
V=lambda x:1==len(x)or all(any((j+J,k+K)in x for J,K in[(0,1),(0,-1),(1,0),(-1,0)])for j,k in x)
G=lambda p,i,F=min:F(j[i]for j in p)
N=lambda p:[(x-G(p,0),y-G(p,1))for x,y in p]
M=lambda j:[[int((x,y) in j)for y in range(G(j,1,max)+1)]for x in range(G(j,0,max)+1)]
O=lambda j:{*R(m:=M(j)),*R([i[::-1]for i in m])}
def P(b,n):
 q=[(b,[],n)]
 while q:
  b,C,n=q.pop(0)
  if n==0 and not b:yield C
  if n and b:
   for i,_ in E(b,1):
    for c in I.combinations(b,i):
     if V(c):q+=[(b-{*c},C+[N(c)],n-1)]
def f(a,b):
 c=0
 while c:=c+1:
  if any(all(O(J)&O(K)for J,K in zip(x,y))for x in P(S(a),c)for y in P(S(b),c)):return c

Try it online!