Tiling the unit square

8

1

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.

user1502040

Posted 2017-03-28T19:23:14.250

Reputation: 2 196

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? – Greg Martin – 2017-03-28T19:29:00.010

@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. – user1502040 – 2017-03-28T19:33:23.867

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.... – Greg Martin – 2017-03-28T19:37:25.590

OK, I changed the threshold from 20 to 100. – user1502040 – 2017-03-28T19:45:34.843

Oh, Goodness. I have not yet learnt sum to infinity, thus I do not understand this at all. – Matthew Roh – 2017-03-29T13:09:30.420

@SIGSEGV This isn't really a Riemann sum (there's no x or Δx). It's just the infinite series (1/1)(1/2) + (1/2)(1/3) + (1/3)(1/4) + ... which equals 1/2 + 1/6 + 1/12 + .... See series, and integral. Looking at the Partial sum formula of the integral, you can see that as m => ∞ that the result is 1.

– mbomb007 – 2017-04-04T21:05:17.187

@user1502040 Can you perhaps add a graphical picture of your example? I think that'd help. – mbomb007 – 2017-04-04T21:18:08.227

@mbomb007 Oh no. Calculus. I didn't learn that too. – Matthew Roh – 2017-04-04T23:05:32.877

Answers

2

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.

halfflat

Posted 2017-03-28T19:23:14.250

Reputation: 261