% Nb: This file must be passed through cweave before LaTeX-ing.
%    cweave -j PackSquares.w
%    latex PackSquares
% To create the PackSquares Java class:
%    ctangle -j PackSquares.w

\documentclass[12pt,a4paper]{cweb}
% \usepackage[hypertex]{hyperref}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsbsy}
\usepackage{amssymb}
\usepackage{url}
\usepackage{doc}
\def\defin{define} % As in webmac.tex
\def\C{\textsc{C}}
\def\Java{\textsc{Java}}
\def\D{\defin{define}} % macro definition

\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand\legendre[2]{\genfrac(){}{0}{#1}{#2}}
\newcommand\F{\mathbb{F}}
\newcommand\Xxor{\wedge}

\MakeShortVerb{\"}

\title{Packing squares}

\author{Timothy Murphy\\
\texttt{<tim@@maths.tcd.ie>}\\
School of Mathematics, Trinity College Dublin}

\date{\today}

\begin{document}

\maketitle

\tableofcontents

\begin{abstract}
Can one pack squares of size $1,1/2,1/3,\dots$
into a rectangle of size $1 \times \pi^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.
\end{abstract}

@* Introduction.

Clive Tooth raised the question
(in March 2004 on the "sci.math" newsgroup)
whether one could pack squares of sizes
$1 \times 1$,
$1/2 \times 1/2$,
$1/3 \times 1/3$, \dots
into a rectangle of size $1 \times$
\[
1 + \frac{1}{2^2} + \frac{1}{3^2} + \cdots
= \frac{\pi^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 \times y$, where $x \le 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 \times 1/n$.
Then we find the smallest rectangle $R$ in our list
with
\[
1/n \le x \le y.
\]
We remove the square from a corner of the rectangle,
leaving 2 rectangles
\[
R_1 = (x - 1/n, 1/n) \text{ 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) \text{ 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 $n$th square the list will be of length $\le n$.
It may be less, since we can omit rectangles with $x = 0$.
(For example, the first $1 \times 1$ square will only leave one rectangle
$(\pi^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}$.

@* 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
\begin{description}
\item[Constructors] --- the code describing 
how an object in the class is \emph{created}.

\item[Class methods] --- routines not specific to a particular object
in the class, as for example the "main" routine required
in any \Java\ application.

\item[Class data] --- data shared by all the objects in the class,
as for example, "vacancies",
the "LinkedList" holding the list of vacant rectangles.

\item[Instance data] --- the `fields'
which are defined for each object in the class.

\item[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.
\end{description}

@c
import java.math.*;@/
import java.io.*;@/
import java.util.*;@/

public class SquarePack {
  @<"SquarePack" instance data@>@;
  @<"SquarePack" constructors@>@;
  @<"SquarePack" instance methods@>@;
  @<"SquarePack" class data@>@;
  @<"SquarePack" class methods@>@;

  @<Definition of Rectangle class@>@;
}

@*1 Debugging.

@d debug==@{
@d gubed==@t@>@} 
@f debug begin
@f gubed end
@#
@d stat==@{ 
@d tats==@t@>@} 
@f stat begin
@f tats end


@*1 The `SquarePack' object.

`SquarePack' consists basically of a "LinkedList" $vacancies$
of "Rectangles".

@f BigInteger int
@f LinkedList int
@f String int
@f BitSet int
@f System int

@<"SquarePack" instance data@>=

int currentIndex = 0;
int lastIndex = 0;
LinkedList rectangles;

static int maxCount = 0;
static int sumCount = 0;
static float vacantArea = 0;

@ @<"SquarePack" constructors@>=

public SquarePack() {
  rectangles = new LinkedList();
}

public SquarePack(long w, long h, long n) {
  rectangles = new LinkedList();
  Rectangle r = 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;
  Rectangle r = new Rectangle(w,h,n);
  addRectangle(r);
}

@ @<"SquarePack" instance methods@>=

public int findIndex(Rectangle r) {

// Returns the index of the largest rectangle s with  s.x < r.x
// ie the correct place to insert rectangle r

  Rectangle s;
  int index;
  int size = rectangles.size();

  for (index = currentIndex; index < size; index++)
     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++)
    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++) {
    Rectangle r = (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(average 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(Rectangle r) {

  // 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) {

  Rectangle square = 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);
  }
  Rectangle r = (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]
  Rectangle s = 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]
  Rectangle t = new Rectangle(w.subtract(r.n),r.n,n);
  t.count = r.count + 1;
  t.check();
  addRectangle(t);
  checkOrder();
// System.out.println("area lost: " + (r.area - s.area - t.area));
  
}



@* The `Rectangle' class.

@ @<Definition of Rectangle class@>=

class Rectangle {
  @<"Rectangle" instance data@>@;
  @<"Rectangle" constructors@>@;
  @<"Rectangle" instance methods@>@;
}

@ @<"Rectangle" instance data@>=

BigInteger w,h,n;
double x,y;
double area;
int count = 0;

@ @<"Rectangle" constructors@>=

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;
}

@ @<"Rectangle" instance methods@>=

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 + "]");
}

@ 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.

@<"Rectangle" instance methods@>=
public int compareTo(Rectangle s) {
  int c;
  c = this.w.multiply(s.n).compareTo(s.w.multiply(this.n));
  return c;
}

@* Class methods.

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

@<"SquarePack" class data@>=
static int square = 0;
static float epsilon;
static boolean first = true;

Rectangle container;

@ @<"SquarePack" class methods@>=
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(
     6L*33102L*33102L,103993L*103993L,6L*33102L*33102L);
  // 6L*113L*113L,355L*355L,6L*113L*113L);

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

  squarePack.printList(true);

}

@* Administrivia.

The file "PackSquares.w" from which this document is derived
can be retrieved from
\url{ftp://ftp.maths.tcd.ie/pub/TeX/javaTeX/javaweb/examples/PackSquares.w}.

\end{document}