Introduction
One question that I have come across recently is the possibility of dissecting a staircase of height 8 into 3 pieces, and then re-arranging those 3 pieces into a 6 by 6 square.
Namely, is it possible to dissect the following into 3 pieces:
x
xx
xxx
xxxx
xxxxx
xxxxxx
xxxxxxx
xxxxxxxx
And rearrange those 3 pieces into the following shape:
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
Task
In this challenge, you will be tasked to find out exactly this. Specifically, given two shapes created from adjacent (touching sides, not diagonally) squares of the same size and a natural number n
, return whether it is possible to dissect one of the shapes into n
pieces, with all cuts along the edges of the squares, and then rearrange those n
pieces to form the other shape. Just like the input shapes, each piece also has to be formed from adjacent squares and thus form one contiguous region. The pieces can be moved, rotated, and flipped in any way in order to form the other shape, but nothing else like shrinking or stretching the piece. The shapes can be represented in any reasonable form, including a 2d matrix with one value representing empty space and the other representing the actual shape, or a list of coordinates representing the positions of each individual square.
Additionally, you can assume that both shapes will consist of the same amount of squares, and that n
will never exceed the number of squares within either of the shapes.
This is code-golf, so the shortest code in bytes wins!
Test Cases
In these test cases, each square is represented by one #
, and an empty space is represented by a space.
I made all the test cases by hand so tell me if there are any mistakes.
Truthy
shape 1
shape 2
n
-------------------------------------
x
xx
xxx
xxxx
xxxxx
xxxxxx
xxxxxxx
xxxxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
xxxxxx
3
xxx
xxx
xx
x
xxxxx
x xxx
3
xxxx
xxxx
xxxx
xxxx
xxxxx
x x
x x
x x
xxxxx
4
x
x
xxx
xxx
xx
x
xxxxx
xxxxxx
10
Falsey
shape 1
shape 2
n
-------------------------------------
xxx
xxx
xxxxx
x
2
xxxx
xxxx
xxxx
xxxx
xxxxx
x x
x x
x x
xxxxx
3
###
###
###
#########
2
#####
## #
### #
##
#
##
###
####
#
##
#
3
###
into# #
and#
? \$\endgroup\$