Packing squares

Timothy Murphy

                 <tim@maths.tcd.ie>

School of Mathematics, Trinity College Dublin

March 18, 2004

Contents

Abstract Can one pack squares of size 1, 1/2, 1/3, … into a rectangle of size 1 × π^{2}/6? This note describes — in Knuth’s ‘Literate Programming’ cweb format — an implementation in Java of a simple algorithm which may perform this task, at least to a high degree.

1 Introduction

Clive Tooth raised the question (in March 2004 on the sci.math newsgroup) whether one could pack squares of sizes 1 × 1, 1/2 × 1/2, 1/3 × 1/3, … into a rectangle of size 1×

1 + \frac{1}{2^{2}} + \frac{1}{3^{2}} + ⋯ = \frac{π^{2}}{6} .

He proposed and tested the following algorithm: We can regard the space left after inserting the first n squares as being made up of rectangles. Let the (n + 1)th square be taken from the smallest rectangle of sufficient size.

More precisely, let each rectangle R in the list be taken in the form x × y, where x ≤ y. (Note that the algorithm is not concerned with the position or even orientation of the rectangle, but only with its dimensions.) We represent the rectangle by R = (x, y).

Now suppose we want to remove the square 1/n × 1/n. Then we find the smallest rectangle R in our list with

1/n ≤ x ≤ y.

We remove the square from a corner of the rectangle, leaving 2 rectangles

R_{1} = (x − 1/n, 1/n) and R_{2} = (x, y − 1/n),

subject to the proviso that we may need to correct these orientations. (We could equally well have taken the rectangles

S_{1} = (x − 1/n, y) and S_{2} = (1/n, y − 1/n).

We make the first choice on the grounds that it is probably better to keep as large a rectangle as possible.)

Note that the length of the list is only increased by 1; so on adding the nth square the list will be of length ≤ n. It may be less, since we can omit rectangles with x = 0. (For example, the first 1 × 1 square will only leave one rectangle (π^{2}/6 − 1, 1) when it is removed.)

Clive Tooth suggests that one should also jettison rectangles that are manifestly too small. For example, if one is trying to pack 10^{6} squares then there is no point in keeping rectangles with x < 10^{−6}.

2 Skeleton of a Java program

The definition or specification of a Java class can be divided into 5 parts (not all of which are necessarily, or even usually, present), namely

Constructors — the code describing how an object in the class is created.

Class methods — routines not specific to a particular object in the class, as for example the main routine required in any Java application.

Class data — data shared by all the objects in the class, as for example, vacancies, the LinkedList holding the list of vacant rectangles.

Instance data — the ‘fields’ which are defined for each object in the class.

Instance methods — the routines which act on objects and their fields.

In addition, a class may include auxiliary classes — for example, the Rectangle class in the present case.

2 importjava.math.∗; importjava.io.∗; importjava.util .∗; public class SquarePack {

⟨ SquarePack instance data 4 ⟩ ⟨ SquarePack constructors 5 ⟩ ⟨ SquarePack instance methods 6 ⟩ ⟨ SquarePack class data 13 ⟩ ⟨ SquarePack class methods 14 ⟩ ⟨ Definition of Rectangle class 8 ⟩

}

2.1 Debugging

3 #define debug ≡

#define gubed ≡

format debug begin
format gubed end

#define stat ≡ #define tats ≡

format stat begin
format tats end

2.2 The ‘SquarePack’ object

‘SquarePack’ consists basically of a LinkedList vacancies of Rectangles.

format BigInteger int

4

format LinkedList int
format String int
format BitSet int
format System int

⟨ SquarePack instance data 4 ⟩ ≡ int currentIndex = 0; int lastIndex = 0; LinkedList rectangles ; static int maxCount = 0; static int sumCount = 0; static float vacantArea = 0;

This code is used in chunk 2.

5 ¶ ⟨ SquarePack constructors 5 ⟩ ≡ public SquarePack( ) {

rectangles = new LinkedList( ); } public SquarePack(long w, long h, long n) {

rectangles = new LinkedList( ); Rectangler = new Rectangle(w, h, n); addRectangle(r);

} public SquarePack(double x, double y) {

rectangles = new LinkedList( ); long w = (long)(x ∗ 1000000); long h = (long)(y ∗ 1000000); long n = 1000000; Rectangler = new Rectangle(w, h, n); addRectangle(r);

}

This code is used in chunk 2.

6 ¶ ⟨ SquarePack instance methods 6 ⟩ ≡ public int findIndex (Rectangler) { /∗ Returns the index of the largest rectangle s with s.x ¡ r.x ∗/

/∗ ie the correct place to insert rectangle r ∗/ Rectangles; int index ; int size = rectangles .size( ); for (index = currentIndex ; index < size; index {+ \atop +})

if (((Rectangle)rectangles .get (index )).compareTo(r) < 0) break;

/∗ System.out.println(findIndex -> + index); ∗/ return index ;

} public void checkOrder ( ) {

float lastx = (float) 10.0; for (int index = 0; index < rectangles .size( ); index {+ \atop +})

if (((Rectangle)rectangles .get (index )).x > lastx )

    System.out .println("List␣out␣of␣order␣at␣index␣" + index );

} public void printList (boolean verbose) {

int maxCount = 0; int sumCount = 0; double vacantArea = 0; for (int index = 0; index < rectangles .size( ); index {+ \atop +}) \{

Rectangler = (Rectangle)rectangles .get (index );

if (verbose) System.out .println(r + "␣" + index + "␣" + r.count ); sumCount += r.count ; vacantArea += r.area; if (r.count > maxCount ) maxCount = r.count ;

} if (first ) {

  System.out .println("square\t␣list␣length\t␣max␣split(averag\
      e␣split)\t␣vacant␣space");

first = false; } System.out .println(square + "\t␣␣␣␣" + rectangles .size( ) +

"\t\t\t" + maxCount + "(" + sumCount /rectangles .size( ) + ")\t\t\t␣␣" + (float) vacantArea);

} public void addRectangle(Rectangler) { /∗ Insert rectangle into correct place in linked list ∗/

int index = findIndex (r); if (r.x > epsilon) {

rectangles .add (index , r); /∗ System.out.println(Adding + r +

      in position + index); ∗/

} } public void removeSquare(int i) {

Rectanglesquare = new Rectangle(BigInteger.ONE, BigInteger.ONE,

BigInteger.valueOf ((long) i)); int index = findIndex (square) − 1; if (index < 0) {

  System.err .println("No␣room␣for␣square␣side␣1/" + i);
  System.out .println("No␣room␣for␣square␣of␣side␣1/" + i +

"␣=␣" + 1/(float) i); printList (true); System.exit (1);

} Rectangler = (Rectangle)rectangles .get (index );

/∗ System.out.println(Removing + r + from position + index); ∗/

rectangles .remove(index ); currentIndex = index ; BigInteger m = BigInteger.valueOf ((long) i); BigInteger w = r.w.multiply (m); BigInteger h = r.h.multiply (m); BigInteger n = r.n.multiply (m);

/∗ First we construct the rectangle s = r.x x (r.y - 1/i) ∗/ /∗ ie [w,h,n] = [r.w*i,r.h*i-r.n,r.n*i] ∗/

Rectangles = new Rectangle(w, h.subtract (r.n), n); s.count = r.count + 1; s.check ( ); addRectangle(s); /∗ Next we construct the rectangle t = (r.x - 1/i)

x 1/i ∗/ /∗ ie [w,h,n] = [r.w*i-r.n,r.n,r.n*i] ∗/ Rectanglet = new Rectangle(w.subtract (r.n), r.n, n); t.count = r.count + 1; addRectangle(t); t.check ( ); checkOrder ( );

/∗ System.out.println(area lost: + (r.area - s.area - t.area)); ∗/ }

This code is used in chunk 2.

3 The ‘Rectangle’ class

8 ¶ ⟨ Definition of Rectangle class 8 ⟩ ≡

class Rectangle { ⟨ Rectangle instance data 9 ⟩ ⟨ Rectangle constructors 10 ⟩ ⟨ Rectangle instance methods 11 ⟩

}

This code is used in chunk 2.

9 ¶ ⟨ Rectangle instance data 9 ⟩ ≡ BigInteger w, h, n; double x, y; double area; int count = 0;

This code is used in chunk 8.

10 ¶ ⟨ Rectangle constructors 10 ⟩ ≡ Rectangle(BigInteger w, BigInteger h, BigInteger n) {

this.w = w; this.h = h; this.n = n; x = w.doubleValue( )/n.doubleValue( ); y = h.doubleValue( )/n.doubleValue( ); area = x ∗ y;

} Rectangle(long w, long h, long n) {

this.w = BigInteger.valueOf (w); this.h = BigInteger.valueOf (h); this.n = BigInteger.valueOf (n); x = (double) w/(double) n; y = (double) h/(double) n; area = x ∗ y;

}

This code is used in chunk 8.

11 ¶ ⟨ Rectangle instance methods 11 ⟩ ≡ public void check ( ) { /∗ We ensure that gcd(w,h,n) = 1 and w ¡= h ∗/

BigInteger d = w.gcd (n); d = d.gcd (h); if (d.compareTo(BigInteger.ONE) > 0) {

w = w.divide(d); h = h.divide(d); n = n.divide(d);

} if (w.compareTo(h) > 0) {

BigInteger t = w; w = h; h = t; double z = x; x = y; y = z;

} } public String toString ( ) {

return ("(" + (float) x + "," + (float) y + ")");

/∗ return ([ + w + , + h + , + n + ]); ∗/ }

See also chunk 12. This code is used in chunk 8.

¶ The function compareTo checks if the Rectangle r should come after or before the given Rectangle; r.compareTo(s) will return +1 if r is ‘larger’ than s, ie has larger width, and -1 if it is smaller. If the two rectangles have the same width it will return 0.

12 ⟨ Rectangle instance methods 11 ⟩ +≡ public int compareTo(Rectangle s) {

int c; c = this.w.multiply (s.n).compareTo(s.w.multiply (this.n)); return c;

}

4 Class methods

Every Java application must have at least one class method, namely the main() program.

13 ⟨ SquarePack class data 13 ⟩ ≡ static int square = 0; static float epsilon; static boolean first = true; Rectangle container ;

This code is used in chunk 2.

14 ¶ ⟨ SquarePack class methods 14 ⟩ ≡ public static void main(String[ ]args ) {

int count = 1000; if (args .length > 0) {

count = Integer .parseInt (args [0]); } epsilon = (float) 0.999/(float) count ; /∗ SquarePack squarePack

= new SquarePack(1.0,Math.PI*Math.PI/6); ∗/ SquarePack squarePack = new SquarePack(6_{L} ∗ 33102_{L} ∗ 33102_{L},

103993_{L} ∗ 103993_{L}, 6_{L} ∗ 33102_{L} ∗ 33102_{L}); /∗ 6L*113L*113L,355L*355L,6L*113L*113L); ∗/

for (square = 1; square ≤ count ; square {+ \atop +}) \{ squarePack .removeSquare(square); if (square % 16 ≡ 0) System.err .print ("."); if (square % 1024 ≡ 0) squarePack .printList (false);

} squarePack .printList (true);

}

This code is used in chunk 2.

5 Administrivia

The file PackSquares.w from which this document is derived can be retrieved

from ftp://ftp.maths.tcd.ie/pub/TeX/javaTeX/javaweb/examples/PackSquares.
w.

Index

add : 6. addRectangle: 5, \underline{6}. area: 6, \underline{9}, 10. args : 14. BigInteger: 6, 9, 10, 11. c: \underline{12}. check : 6, \underline{11}. checkOrder : \underline{6}. compareTo: 6, 11, \underline{12}. container : \underline{13}. count : 6, \underline{9}, \underline{14}. currentIndex : \underline{4}, 6. d: \underline{11}. debug : \underline{3}. divide: 11. doubleValue: 10. epsilon: 6, \underline{13}, 14. err : 6, 14. exit : 6. false: 6, 14. findIndex : \underline{6}. first : 6, \underline{13}. gcd : 11. get : 6. gubed : \underline{3}. h: \underline{5}, \underline{6}, \underline{9}, \underline{10}. i: \underline{6}. index : \underline{6}. Integer : 14. io: 2. java: 2. lastIndex : \underline{4}. lastx : \underline{6}. length: 14. LinkedList: 4, 5. m: \underline{6}. main: \underline{14}. math: 2. maxCount : \underline{4}, \underline{6}. multiply : 6, 12. n: \underline{5}, \underline{6}, \underline{9}, \underline{10}. ONE: 6, 11. out : 6. parseInt : 14. print : 14. printList : \underline{6}, 14. println: 6. Rectangle: 5, 6, \underline{8}, \underline{10}, 12, 13. rectangles : \underline{4}, 5, 6. remove: 6. removeSquare: \underline{6}, 14. s: \underline{12}. size: \underline{6}. square: 6, \underline{13}, 14. squarePack : \underline{14}. SquarePack: \underline{2}, \underline{5}, 14. stat : \underline{3}. String: 11, 14. subtract : 6. sumCount : \underline{4}, \underline{6}. System: 6, 14. t: \underline{11}. tats : \underline{3}. toString : \underline{11}. true: 6, 13, 14. util : 2. vacantArea: \underline{4}, \underline{6}. valueOf : 6, 10. verbose: \underline{6}. w: \underline{5}, \underline{6}, \underline{9}, \underline{10}. x: \underline{5}, \underline{9}. y: \underline{5}, \underline{9}. z: \underline{11}.

List of Refinements

⟨ Rectangle constructors 10 ⟩ Used in chunk 8. ⟨ Rectangle instance data 9 ⟩ Used in chunk 8. ⟨ Rectangle instance methods 11, 12 ⟩ Used in chunk 8. ⟨ SquarePack class data 13 ⟩ Used in chunk 2. ⟨ SquarePack class methods 14 ⟩ Used in chunk 2. ⟨ SquarePack constructors 5 ⟩ Used in chunk 2. ⟨ SquarePack instance data 4 ⟩ Used in chunk 2. ⟨ SquarePack instance methods 6 ⟩ Used in chunk 2. ⟨ Definition of Rectangle class 8 ⟩ Used in chunk 2.