By expanding and cancelling terms, it is easy to show the following identity:
However, it is an open problem whether all 1/n-by-1/(n+1) rectangles can tile the unit square.
Your program should take a positive integer N as input in any convenient manner, and pack all 1/n-by-1/(n+1) open rectangles with n between 1 and N inclusive into the unit square, such that no two overlap.
For each rectangle you must generate the following integers in order:
- 1 if the horizontal edges are longer than the vertical edges, else 0
- The numerator and denominator of the x-coordinate of the bottom-left corner
- The numerator and the denominator of the y-coordinate of the bottom-left corner
Note that we take the unit square to be
(0, 1) x (0, 1), with x-values running from left to right, and y-values running from bottom to top.
The final expected output is the concatenation of these integers for each rectangle in order of increasing n, in any convenient format (e.g. printed to stdout, or as a list returned from a function).
Example Input and Output
0 0 1 0 1 1 1 2 0 1 1 1 2 1 3
This parses as the following:
0 (0/1, 0/1) 1 (1/2, 0/1) 1 (1/2, 1/3)
This is a code-golf challenge, so the answer with the fewest bytes wins. However, your algorithm should also be reasonably efficient; it should be able to run for all
N<=100 in a total of around 10 minutes.
Your solution must give valid solutions for all
N<=100, but provably complete algorithms are also welcome even if they aren't the shortest.