\documentclass{article}
\usepackage{noweb}
\usepackage{pretzel-noweb}
%
% A small Java example for use with noweb
%
\begin{document}


\title{Towers of Hanoi revisited}
\author{Felix G\"artner}
\maketitle

\tableofcontents



\section{Introduction}

A ``towers of hanoi'' implementation with four landing places for
bricks. This file was written using the {\tt noweb} literate programming
system. To get a Java file from this text, run {\tt notangle} on it.

@

Here's the frame of it all. All stuff is included within the [[Hanoi]]
class, i.e. also the auxiliary functions like [[assert]].

<<Hanoi.java>>=
// towers of hanoi with four boxes

class Hanoi {

  <<Hanoi class variables>>

  <<Functions of Hanoi class>> //@cancel

  static void assert(boolean t) {
    if (!t) {
      System.err.println("Assertion violation");
      System.exit(1);
    }
  }

}
@

The moves that have been taken by this algorithm are counted in
[[moves]]. Also, we can use a [[HanoiView]] object to have a look
at what's going on.

<<Hanoi class variables>>=
static int moves = 0;
static HanoiView view = null;
@

All stuff will be broken down to calls of this function. It
is an interface to possible visualization tools. We'll count
the moves here.

<<Functions of Hanoi class>>=
static void move( int from, int to )
{
  moves++;
  if (moves > boring_size) {  // only output sporadic progress reports
    if (moves % boring_size_slice == 0) {
      System.out.println("Finished " + moves + ". move...");
    }
  } else {
    System.out.println("Moving from " + from + " to " + to + "... ("
        + moves + ". move)");
    if (view != null) view.move(from, to);
  }
}
@

<<Hanoi class variables>>=
static final int boring_size = 100;
static final int boring_size_slice = 100;
@

Here's the old ``straight out of the hat'' implementation of the
towers using only three boxes. It won't use the [[without]] box.

<<Functions of Hanoi class>>=
static void hanoi_old( int how_many, int from, int to, int use, int without )
{
  assert( from + to + use + without == 10 );

  if (how_many == 1)  {
    move( from, to );
  } else {
    hanoi_old( how_many-1, from, use, to, without );
    move( from, to );
    hanoi_old( how_many-1, use, to, from, without );
  }
}
@

The idea behind this four box implementation is to move slices
of $k$ bricks at a time. The fourth box is used to enable
building these $k$-brick bricks.

<<Functions of Hanoi class>>=
static void hanoi_four( int how_many, int from, int to, int use,
    int without, int k )
{
  assert( from + to + use + without == 10 );

  if (how_many <= k) {
    hanoi_old( how_many, from, to, without, use );
  } else {
    hanoi_four( how_many-k, from, use, to, without, k );
    hanoi_old( k, from, to, without, use );
    hanoi_four( how_many-k, use, to, from, without, k );
  }
}
@

How to invoke...

<<Functions of Hanoi class>>=
public static void main (String[] args)
{
  if (args.length != 2) {
    System.err.println("Usage: Hanoi n k");
    System.exit(1);
  }

  int n = Integer.parseInt(args[0]);
  int k = Integer.parseInt(args[1]);

  assert(k>0);

  // to view the towers, we'll use a \texttt{Hanoi\_view} for 4 towers
  view = new HanoiView(4,n);

  System.out.println("Starting to hanoi on four towers (n=" +
      n + " bricks, k=" + k + ")");

  view.show();

  hanoi_four( n, 1, 4, 2, 3, k );

  System.out.println("Needed " + moves + " moves.");
  System.err.println("Needed " + moves + " moves!");
}
@


\section{Animated Hanoi}

Here's a view of the Hanoi example. It's a class that can be used
to visualize the towers of Hanoi with up to n landing places for
blicks.

<<HanoiView.java>>=
// view of Hanoi

class HanoiView {

  <<View class variables>>

  <<View class methods>>

  <<View main routine>>

  static void assert(boolean t, String message) {
    if (!t) {
      System.err.println("Assertion violation: " + message);
      System.exit(1);
    }
  }
}
@

\subsection{Using}

How to use this view?  Just create a Hanoi view with [[new]] and tell
it, how many towers you have and how many bricks you want to
manipulate (e.g. [[new HanoiView(4,6)]] for four towers and 6
bricks). Then simply call the [[move]] method on this view and tell
it, to move a brick from where to where (e.g. [[move(1,4)]] to move a
brick from tower 1 to tower 4, if there are so many). The class will
check the arguments of [[move]] but won't check, if you're putting a
larger brick on a smaller brick. You'll have to take care of this
yourself. Also there are no accessor functions to the towers yet.

@

\subsection{Implementation}

The idea of this view is to have two [[int]] arrays that keep track of
which brick is where. Bricks are denoted by integers between 1 and the
number given in the constructor. The first array [[turm]] is a
two-dimensional array. The value of [[turm[i]]] stores the actual
status of tower [[i]], i.e. [[turm[i][j]]] tells us, which brick is at
level [[j]] in tower [[i]]. The levels count from 0 to the maximum
number of bricks given in the constructor.

There's an additional array [[hoehe]] that is implicitly contained in
[[turm]] but is kept for easy access. The value of [[hoehe[i]]] counts
the number of bricks on tower [[i]].

<<View class variables>>=
int t = 0;  // number of towers
int n = 0;  // number of bricks
int turm[][]; // new int [t][n];
int hoehe[];  // new int [t];
@

<<View class methods>>=
HanoiView(int towers, int bricks)
{
  t = towers;
  n = bricks;
  turm = new int[t][n];
  hoehe = new int[t];

  // initialize everything

  for (int i=0; i<t; i++) {
    hoehe[i] = 0;
    for (int j=0; j<n; j++) {
      turm[i][j] = 0;
    }
  }

  // n bricks are on first tower (should this be part of the
  // constructor??)

  hoehe[0] = n;
  for (int i=0; i<n; i++) {
    turm[0][n-1-i] = i+1;
  }
}
@

Now for the moves. The height of [[to]] is incremented.

<<View class methods>>=
void move(int from, int to)
{
   assert( 1<=from && from<=t, "Illegale Turm-Nummer " + from );
   assert( 1<=to   && to<=t,   "Illegale Turm-Nummer " + to );
   assert( hoehe[from-1] > 0 , "keine Scheiben mehr auf Turm " + from);

   hoehe[to-1] = hoehe[to-1] + 1;
   turm[to-1][hoehe[to-1]-1] = turm[from-1][hoehe[from-1]-1];
   turm[from-1][hoehe[from-1]-1] = 0;
   hoehe[from-1] = hoehe[from-1] - 1;

   show();
   try {
     int s = System.in.read();
   }
   catch (java.io.IOException e1) {
   }
}
@

Bricks are visualized as a series of $2\cdot n$ characters in a row.
The maximum width of a tower is therefore $2\cdot n$, and for every
brick $b$, we first output $n-b$ spaces, then $2\cdot b$ characters,
and then again $n-b$ spaces, which gives a total of $n-b+2\cdot b+n-b
= 2\cdot n$ characters.

<<View class methods>>=
void show()
{
  for (int j=n-1; j>=0; j--) { // for every possible brick
      // (instead of n-1 could take max(hoehe[i]) for every i)
    for (int i=0; i<t; i++) { // for every tower
        // turm[i][j] is number of brick
        // output n-b spaces
      for (int k=0; k<n-turm[i][j]; k++) {
        System.out.print(" ");
      }
        // output 2*b letters
      for (int k=0; k<2*turm[i][j]; k++) {
        // NB radix is n+1, i.e. 10=A etc.
        System.out.print(Character.forDigit(turm[i][j],n+1));
      }
      for (int k=0; k<n-turm[i][j]; k++) {
        System.out.print(" ");
      }
    }
    System.out.println();
  }
  for (int i=0; i<t; i++) {
    for (int j=0; j<n; j++) {
      System.out.print("--");
    }
  }
  System.out.println();
}
@

<<View main routine>>=

@

\section{List of Refinements}

\nowebchunks

\section{Index}

\nowebindex

\end{document}