Reassemble Three Rectangles
Autumn Tournament (2015)
Submission name: rect.cpp
Problem summary
Three integer-sided rectangular pieces came from one rectangular sheet. Rotate and arrange them without overlap to reconstruct a rectangle, then draw all outer and internal piece boundaries with dots. Any valid reconstruction is accepted.
Input
Three lines, each containing the two side lengths of one piece.
Output
A dot diagram of one reconstruction. On each horizontal boundary, consecutive unit grid points are dots separated by one space; vertical boundaries have one dot at every unit height. Leave piece interiors blank.
Constraints
All side lengths are integers strictly between 1 and 40. The pieces are promised to come from a rectangular sheet.
Worked example
Original first sample input; this code prints a valid side-by-side reconstruction, with exact unit spacing.
Input
2 2 2 3 4 2
Output
. . . . . . . . . . . . . . . . . . . . . . . .
Solution analysis
- With only three rectangles, a tiling has a full straight cut. Up to rotating the whole answer, it has one of two forms: three side-by-side strips of equal height, or one full-height piece beside two pieces stacked vertically. Enumerate all 6 piece orders and all 8 choices of individual rotations.
- For strips, require equal heights and add the widths. For the second form, the stacked pieces must have equal widths and their heights must sum to the height of the full-height piece. These tests also provide the coordinates of every piece.
- For pieces 2×2, 2×3, and 4×2, rotate the second to 3×2. Place the widths 2, 3, 4 side by side, giving a 9×2 rectangle. Dots on vertical boundaries are at x=0,2,5,9. The picture has 3 rows and 19 character columns because each horizontal unit uses two character columns.
- The renderer uses grid coordinates for geometry, then writes a dot at character column 2x. Mark both horizontal sides and both vertical sides of each placed piece. Shared boundaries are harmless: writing the same dot twice produces the intended line.
Why it works
The outer rectangle has four corners but only three pieces, so some piece contains two outer corners. Those corners must be adjacent unless that piece occupies the whole sheet; therefore the piece spans the full width or height. If this spanning piece is internal, the other two pieces occupy its two sides, giving three strips. If it touches an outer side, the other two tile the rectangular remainder, separated by one straight cut. Up to rotating the result, these are exactly the two enumerated forms. Every piece order and orientation is considered, so a valid promised input is found. Drawing each piece boundary at its computed coordinates produces exactly that tiling.
Watch out. This is an output-construction problem: a different valid picture can be correct. Draw unit grid points, not solid runs of dots. Keep spaces inside the rectangles. Do not assume the input side order fixes a piece’s orientation.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct Rectangle{
int width;
int height;
};
struct Placement{
int x;
int y;
int width;
int height;
};
void draw(const array<Placement,3>&pieces,int width,int height){
vector<string>picture(height+1,string(2*width+1,' '));
for(const Placement&piece:pieces){
for(int x=piece.x;x<=piece.x+piece.width;++x){
picture[piece.y][2*x]='.';
picture[piece.y+piece.height][2*x]='.';
}
for(int y=piece.y;y<=piece.y+piece.height;++y){
picture[y][2*piece.x]='.';
picture[y][2*(piece.x+piece.width)]='.';
}
}
for(const string&row:picture){
cout<<row<<'\n';
}
}
int main(){
array<Rectangle,3>original;
for(Rectangle&piece:original){
cin>>piece.width>>piece.height;
}
array<int,3>order{0,1,2};
do{
for(int mask=0;mask<8;++mask){
array<Rectangle,3>pieces;
for(int index=0;index<3;++index){
pieces[index]=original[order[index]];
if((mask&(1<<index))!=0){
swap(pieces[index].width,pieces[index].height);
}
}
Rectangle a=pieces[0];
Rectangle b=pieces[1];
Rectangle c=pieces[2];
// First topology: three strips with the same height.
if(a.height==b.height&&b.height==c.height){
array<Placement,3>placed{{{0,0,a.width,a.height},{a.width,0,b.width,b.height},
{a.width+b.width,0,c.width,c.height}}};
draw(placed,a.width+b.width+c.width,a.height);
return 0;
}
// Second topology: one full-height piece beside two stacked pieces.
if(b.width==c.width&&a.height==b.height+c.height){
array<Placement,3>placed{{{0,0,a.width,a.height},{a.width,0,b.width,b.height},
{a.width,b.height,c.width,c.height}}};
draw(placed,a.width+b.width,a.height);
return 0;
}
}
}
while(next_permutation(order.begin(),order.end()));
}