8
\$\begingroup\$

Background

By expanding and cancelling terms, it is easy to show the following identity:

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ Seeing as this is an open problem, is there a cap on the largest value of $N$ for which our algorithm must be guaranteed to work? \$\endgroup\$ – Greg Martin Mar 28 '17 at 19:29
  • \$\begingroup\$ @GregMartin you should successfully run your program for N from 1 to 20. Brownie points if your algorithm can be proven to either succeed or disprove the conjecture. \$\endgroup\$ – user1502040 Mar 28 '17 at 19:33
  • \$\begingroup\$ For N≤20 the output can just be hardcoded ... is it your intention to allow that? There is a simple published algorithm that allows at least N=1,000,000,000.... \$\endgroup\$ – Greg Martin Mar 28 '17 at 19:37
  • \$\begingroup\$ OK, I changed the threshold from 20 to 100. \$\endgroup\$ – user1502040 Mar 28 '17 at 19:45
  • \$\begingroup\$ Oh, Goodness. I have not yet learnt sum to infinity, thus I do not understand this at all. \$\endgroup\$ – Matthew Roh Mar 29 '17 at 13:09
2
+50
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.