Tomas Rokicki's ACM UIST Interaction Contest Entry


Try out my entry here!

Precomputing Solutions
Tomas Rokicki
Instantis

When I found out about the UIST contest from a friend on TopCoder, I was intrigued. The input was just four numbers, from 0..100 each, a total of about 104 million possibilities; certainly I could precompute some good solutions. Further, with three bins to pack into, it seemed that solutions with tilted squares would be rare; rather than waste the space needed to tilt a square, just allocate the squares among the bins in a better fashion.

So I broke the problem into the following steps:

  1. For squares and rectangles as large as I could, compute the best possible packings, orienting the squares with the axes and locating them at integer coordinates. I found a dynamic programming approach to this, with which I was able to find all the possible packings (eliminating equivalent ones) for squares up to 20x20 and for rectangles up to 18x43. Dynamic programming was critical here; there are 790,265,495,126,500 different ways to arrange squares of size 2..5 in a larger square of only 11x11; with dynamic programming I was able to explore this space in under a third of a second. I stored the resulting solutions in a series of files that totaled 16.7 megabytes, compressed.
  2. Combine the narrow rectangles as strips of larger squares to compute the orthogonal packings possible for squares of size larger than 20x20. This used a simple approach of combining all possible strips of a given length from the previous step, and resulted in a set of data files totalling 93.3 megabytes, compressed. I could stop at a square size of 43 because it is straightforward to fit 100 squares of each size into three such squares.
  3. Next, figure out how the solutions for squares could be combined into two and then three bins. To do this I just considered all possible pairs of squares of each size, and figured out the solution that came first in the ordering prescribed by the problem. I then considered all combinations of these pairs with the individual square solutions again to generate sets of three bins. This resulted in data files totalling 83.2 megabytes.
  4. Finally, I considered the impact of tilting squares. I considered only one recipe for tilting squares: combining a rectangle tilted at 45 degrees in the center with four surrounding truncated triangles, for as many sizes of triangles and rectangles as I could. To compute the possible triangles I slightly modified the program used in step 1. This led to a new set of square layouts with different possible packings, so I had to rerun step 3 to integrate these solutions into the bin solutions. This generated another 3.9 megabytes worth of compressed data files.
Because of limited memory and disk space, I had to use a number of optimizations in the programs to represent the set of packings with as little space as possible. I also took advantage of symmetric states in the dynamic programming problem, and used gzip throughout to compress all data files (using zlib to read and write the files as though they were not compressed). All told I probably used about two solid weeks of CPU time (on slow CPUs).

The final program that calculates the packing for the specific input values has to read the data files, scanning them linearly for a solution that works, and decomposing the problem into smaller subproblems, in reverse order of the steps I enumerated above.

The code was written in C and Perl. I have got to start using some better programming languages.

With a more modern machine (I used a pair of ancient 450MHz Celeron processors on a machine with only 768M of memory) I probably could have pushed some of the limits even farther. But overall I enjoyed the problem immensely.