static int Opposite(int dir)
{
return (dir==1) ? 0 : 1;
}
The neighbor of a pole is calculated by adding to its number the
the neighbor's direction; then the neighbor's number is obtained by
dividing the sum by 3 plus 1 (think why?).
static int Neighbor(int Pole, int dir)
{
return (Pole + dir) % 3 +1;
}
Under this new consideration, we must change the definition of procedures
hanoi and moveDisk:
static void hanoi(int height,
int Pole,
int dir)
{
if (height >= 1)
{
hanoi(height-1, Pole, Opposite(dir));
moveDisk(height, Pole, dir);
hanoi(height-1, Neighbor(Pole, Opposite(dir)), Opposite(dir));
}
}
static void moveDisk(int disk, int fromPole, int dir)
{
char fromPeg = PoleName(fromPole),
toPeg = PoleName(Neigh(fromPole, dir));
moves++;
System.out.print(fromPeg);
System.out.print(toPeg);
System.out.print(((moves % 20)==0) ? '\n' : ' ');
}
static char PoleName(int pole)
{
switch (pole)
{
case 1: return 'A';
case 2: return 'B';
case 3: return 'C';
}
return 'E';
}
Back to main pageAs it was explained in the main text we can eliminate the use of the variable dir and consequently we don't need function Opposite. Let's see how procedures hanoi and moveDisk are transformed:
static void hanoi(int height,
int Pole)
{
if (height >= 1)
{
hanoi(height-1, Pole);
moveDisk(height, Pole);
hanoi(height-1, Neigh(Pole, (TowerHeight - height+1) %2 ));
}
}
static void moveDisk(int disk, int fromPole)
{
char fromPeg = PoleName(fromPole),
toPeg = PoleName(Neigh(fromPole,
(TowerHeight - disk) % 2));
moves++;
System.out.print(fromPeg);
System.out.print(toPeg);
System.out.print(((moves % 20)==0) ? '\n' : ' ');
}
Variable TowerHeight is a global static variable that holds the
initial height of the tower.
Back to main page
Get the source code
We now eliminate the second argument. First we must declare one more global variable and then we must find the which expression is used an argument and what's the inverse of this expression. Global variables in Java are just class variables and there usually declared at the beginning of the definition of a class, i.e.,
| Expression | Inverse Expression |
|
|
|
static void hanoi(int height)
{
if (height >= 1)
{
hanoi(height-1);
moveDisk(height);
Pole = Neighbor((TowerHeight - height + 1) %2);
hanoi(height-1);
Pole = Neighbor((TowerHeight - height) %2);
}
}
As it is evident both Neighbor and moveDisk have been
adapted to access variable Pole globally.
Back to main page
Get the source code
Before we actually remove recursion we must remove the postorder statement, i.e., we want to transform the recursive procedure
void C(xtype x)
{
if(P(x))
{
C(F1(x));
S1(x);
C(F2(x));
S2(x);
}
}
into the following one provided there is an inverse to expression F1:
void C(xtype x)
{
if(P(x))
{
C(F1(x));
x1 = x;
for(; P(x) ;)
x1 = F1(x1);
for(; x1 != x ;)
{
S2(x1);
x1 = inv(F1)(x1);
}
S1(x);
C(F2(x));
}
}
Although the resulting procedure is far more complex than the original
one, if we transform procedure hanoi of the
previous section, we get a really simpler procedure.
First note that the first loop becomes:
height1 = height;
for (; height1 != 0; )
height1--;
which means that we simply assign to variable height1 the
value 0! The other loop becomes:
for(; height1 != height; height1++)
Pole = Neighbor((TowerHeight - height1) %2);
Which is equivalent with the following command sequence, given that
height1 is initially set to zero:
Pole = Neighbor((TowerHeight) %2);
Pole = Neighbor((TowerHeight - 1) %2);
Pole = Neighbor((TowerHeight - 2) %2);
....
....
Pole = Neighbor((TowerHeight - height) %2);
The total effect of the above commands is null if height is odd. In
case height is even the command sequence reduces to the last command.
Thus we have for procedure hanoi:
static void hanoi(int height)
{
if (height <> 0)
{
hanoi(height-1);
if((height - 1) % 2 == 1)
Pole = Neighbor((TowerHeight - height + 1) %2);
moveDisk(height);
Pole = Neighbor((TowerHeight - height + 1) %2);
hanoi(height-1);
}
}
And if we move the assignments of Pole to procedure
moveDisk (the first assignment
before the procedures prints anything and the seconde after
the printing is done), we get the following procedure:
static void hanoi(int height)
{
if (height <> 0)
{
hanoi(height-1);
moveDisk(height);
hanoi(height-1);
}
}
Now, we must remove recursion. Applying the techniques of section
"Removing Recursion", it is
a straightforward exercise to produce a non-recursive version of the previous
procedure and the reader is urged to apply what he/she has already learned!
The following procedure is derived by transformations from the stack based
equivalent procedure created from the recursive one:
static void hanoi(int height)
{
int[] HeightStack = new int[height];
int SP = -1;
while (height > 0)
{
SP++;
HeightStack[SP] = height;
height--;
}
while (SP >= 0)
{
height = HeightStack[SP];
SP--;
moveDisk(height);
height--;
while (height > 0)
{
SP++;
HeightStack[SP] = height;
height--;
}
}
}
It is not that difficult to replace the stack in the previous procedure
by stack, which in turn can be replaced by an integer. Here comes the
set oriented version in pseudo-Java:
static void hanoi(int height)
{
integerSet HS = {1..height};
while ( HS != emptySet )
{
height = 1;
while (! (height in HS))
height++;
HS = HS setDiff {height};
moveDisk(height);
HS = HS setUnion {1..height};
}
}
where setDiff and setUnion denote set difference and
union respectively. Now, we can replace the stack and the stack operations
with an integer and operations on integers. First we observe that there is
a one-to-one correspondence between subsets of the set {1..k} and the
integers 1..2k-1. Secondly, we have the following equivalences:
| Sets | Integers |
| integerSet s; | unsigned integer s; |
| s = [1..k]; | s = (int)Math.pow(2, k)-1; |
| s != emptySet; | s != 0; |
| !(k in s ) | s % (int)Math.pow(2, k) == 0 |
| s setMinus {k} | s - (int)Math.pow(2, k-1) |
| s setUnion {1..k-1} | s + (int)Math.pow(2, k-1) -1 |
static void hanoi(int height)
{
int s = (int)Math.pow(2, height) - 1;
while (s != 0)
{
height = 1;
while (s % (int)Math.pow(2, height) == 0)
height++;
s -= (int)Math.pow(2, height - 1);
moveDisk(height);
s += (int)Math.pow(2, height - 1) - 1;
}
}
Now, let's simplify further the above procedure:
static void hanoi(int height)
{
int s, power2Height;
for (s = (int)Math.pow(2, height) - 1; s>0; s--)
{
height = 1;
power2Height = 2;
while (s % power2Height == 0)
{
height++;
power2Height *= 2;
}
moveDisk(height);
}
}
So, after many transformations of the original recursive solution,
Rohl managed to present a purely iterative solution, and consequently
to partially respond to Hayes's challenge.