Tiling the unit square

Question

Background

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.

The Task

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

Input:

3

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)

Scoring

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.

Answer 1

Haskell, 263 262 bytes

import Data.Ratio;f m=let{(#)n z|n>m=[[]]|True=[a:y|(a,j)<-[((o,x,y),[c|c<-(u&w,h-v,x,g):(w-u,h&v,a,y):z,c/=b])|b@(w,h,x,y)<-z,(o,u,v)<-[(o,1%(n+1-o),1%(n+o))|o<-[0,1]],(a,g)<-[(x+u,y+v)|u<=w,v<=h],let(&)p q|w>h=p|True=q],y<-(n+1)#j]}in(1#[(1%1,1%1,0%1,0%1)])!!0

This follows the algorithm described in Paulhus 1997, An Algorithm for Packing Squares, doi:10.1006/jcta.1997.2836. The key observation in the paper, which is empirically if not theoretically verified, is that the region left over after placing a rectangle in a box can be split into two sub-boxes whose filling can then in turn be regarded as independent.

Rather than finding the smallest width sub-box to fit the next rectangle into, the code performs a search across all possible sub-boxes; in practice this does not make an appreciable slow down for n<100.

Output is in the form of a list of entries as tuples with the fraction marker % still included. The integers in the formatted output are in the desired order, but strictly speaking some post-processing would be required to produce the list of integers alone.

Sample run:

*Main> f 5 (0,0 % 1,0 % 1),(0,1 % 2,0 % 1),(0,1 % 2,1 % 2),(0,3 % 4,1 % 2),(1,1 % 2,5 % 6)

Edit: removed an errant space after a let.