Java Source Code and Related Exercises
/* .:....1....:....2....:....3....:....4....:....5....:....6....:....7.. */
// by John Spurgeon
// Contents
//
// Introduction
// Variations on a Theme
//
// 0. Names and Descriptions
// 1. The Main Method
// 2. Solution Algorithms
// 3. Utility Functions
// 4. Move Data Types
// 5. Moves Data Types
// 6. Iterator Data Types
// 7. List Data Type
//
// Further Reading
/*
* Introduction
*/
// The Towers of Hanoi is a puzzle consisting of disks of various
// sizes that are stacked on pegs such that a smaller disk does not
// appear above a larger one. The challenge is to move disks from
// an initial state to a final state while obeying certain rules.
// Disks must always be transferred from one peg to another peg,
// and a larger disk can never be placed on top of a smaller one.
//
// According to the English Wikipedia's "Tower of Hanoi" article
// (retrieved on 3 January 2018),
//
// There is a story about an Indian temple in Kashi Vishwanath
// which contains a large room with three time-worn posts in it,
// surrounded by 64 golden disks. Brahmin priests, acting out the
// command of an ancient prophecy, have been moving these disks
// in accordance with the immutable rules of Brahma since that
// time. The puzzle is therefore also known as the Tower of
// Brahma puzzle. According to the legend, when the last move of
// the puzzle is completed, the world will end.
//
// The article goes on to say that it is not clear whether Édouard
// Lucas, the French mathematician who invented the puzzle in 1883,
// invented this legend or was inspired by it.
/*
* Variations on a Theme
*/
// 1. From Here to Anywhere
//
// In variation 1, a disk on top of a stack may be moved from the
// peg it's on to any other peg as long as doing so does not entail
// placing a larger disk on top of a smaller one.
//
// 2. Pegs in a Row
//
// In variation 2, pegs are arranged in a line, and a disk can only
// be moved to a peg adjacent to the one it's on. In the three-peg
// version of this variation, if the pegs are labeled 0, 1, and 2,
// then peg 0 is adjacent to peg 1, and peg 1 is adjacent to peg 2;
// peg 0 is not adjacent to peg 2.
/*
* 0. Names and Descriptions
*/
// Names and descriptions of frequently used variables.
//
// NAME DESCRIPTION
//
// n A non-negative integral number of disks.
//
// m A non-negative integral number of moves, where a move
// is defined by integers that identify the peg from which
// and the peg to which the move is made.
//
// moves A sequence of moves.
//
// f An integer identifying a peg from which a move is made.
//
// t An integer identifying a peg to which a move is made.
//
// d The absolute value of the difference of two peg numbers.
/*
* 1. The Main Method
*/
/**
* The TowersOfHanoi class is composed of a main method and several
* other static methods with names like solution1a, solution1b,
* solution2a, solution2b, etc. Each of these methods produces a
* a solution to a variation of the Towers of Hanoi puzzle. The
* main method works as follows.
*
* Step 1. Use the command-line arguments (i.e. the value of the
* main method's parameter, which is typically called args)
* to set the values of variables that identify the puzzle
* to be solved and the solution method to be used.
*
* a) If the number of arguments is greater than zero, then the
* first argument determines which solution method to use;
* otherwise, a default solution method is selected.
*
* b) If the number of arguments is greater than one, then the
* second argument determines the number of disks to move;
* otherwise, a default number of disks is selected.
*
* c) If the number of arguments is greater than two, then the
* third argument determines the peg from which the disks are
* to be moved; otherwise, a default peg number is selected.
*
* d) If the number of arguments is greater than three, then the
* fourth argument determines the peg to which the disks are
* to be moved; otherwise a default peg number is selected.
*
* Step 2. Use the selected solution method to obtain a solution to
* to the puzzle to be solved by calling the method, passing
* to the method the number of disks to move, the peg from
* which to move the disks, and the peg to which the disks
* are to be moved.
*
* Step 3. Print the solution (the value of a Moves object) that is
* returned by the selected solution method.
*/
public class TowersOfHanoi
{
public static Moves solution1a(int n, int f, int t)
{
final Moves moves = new ListOfMoves();
return Recursively.solve1(n, f, t, moves);
}
public static Moves solution1b(int n, int f, int t)
{
final int m = Get.numMoves1(n, f, t);
final Moves moves = new ArrayOfMoves(m);
return Recursively.solve1(n, f, t, moves);
}
public static Moves solution1c(int n, int f, int t)
{
final Moves moves = new ListOfMoves();
return NonRecursively.solve1(n, f, t, moves);
}
public static Moves solution1d(int n, int f, int t)
{
final int m = Get.numMoves1(n, f, t);
final Moves moves = new ArrayOfMoves(m);
return NonRecursively.solve1(n, f, t, moves, m);
}
public static Moves solution2a(int n, int f, int t)
{
final Moves moves = new ListOfMoves();
return Recursively.solve2(n, f, t, moves);
}
public static Moves solution2b(int n, int f, int t)
{
final int m = Get.numMoves2(n, f, t);
final Moves moves = new ArrayOfMoves(m);
return Recursively.solve2(n, f, t, moves);
}
public static void main(String[] args)
{
final int numArgs = args.length;
final String whichSolution = numArgs > 0 ? args[0] : "1";
final int
n = numArgs > 1 ? Get.numDisks(args[1]) : 2,
f = numArgs > 2 ? Get.pegNumber(args[2]) : 0,
t = numArgs > 3 ? Get.pegNumber(args[3]) : 1;
Moves moves;
switch (whichSolution)
{
case "1":
case "1a": moves = solution1a(n, f, t); break;
case "1b": moves = solution1b(n, f, t); break;
case "1c": moves = solution1c(n, f, t); break;
case "1d": moves = solution1d(n, f, t); break;
case "2":
case "2a": moves = solution2a(n, f, t); break;
case "2b": moves = solution2b(n, f, t); break;
default: moves = new ArrayOfMoves(0);
}
System.out.println(moves);
}
}
/*
* 2. Solution Algorithms
*/
/**
* The Recursively class is a collection of functions that recursively
* solve variations of the Towers of Hanoi puzzle.
*/
class Recursively
{
public static Moves solve1(int n, int f, int t, Moves moves)
{
if (Get.distance(f, t) > 0)
{
if (n == 1)
{
moves.append(new Move1(f, t));
}
else if (n > 1)
{
final int other = 3 - f - t;
solve1(n - 1, f, other, moves);
solve1(1, f, t, moves);
solve1(n - 1, other, t, moves);
}
}
return moves;
}
public static Moves solve2(int n, int f, int t, Moves moves)
{
final int other = 3 - f - t;
final int d = Get.distance(f, t);
if (d == 2)
{
solve2(n, f, other, moves);
solve2(n, other, t, moves);
}
else if (d == 1)
{
if (n == 1)
{
moves.append(new Move2(f, t));
}
else if (n > 1)
{
solve2(n - 1, f, other, moves);
solve2(1, f, t, moves);
solve2(n - 1, other, t, moves);
}
}
return moves;
}
}
/**
* The NonRecursively class is a collection of functions that solve a
* variation of the Towers of Hanoi puzzle non-recursively.
*/
class NonRecursively
{
public static Moves solve1(int n, int f, int t, Moves moves)
{
final int m = Get.numMoves1(n, f, t);
return solve1(n, f, t, moves, m);
}
public static Moves solve1(int n, int f, int t, Moves moves, int m)
{
final Decoder mathemagician = new Decoder(n, f, t);
for (int i = 1; i <= m; i++)
moves.append(mathemagician.toMove1(i));
return moves;
}
/**
* The Decoder class defines a data type. A Decoder object is
* associated with a particular instance of a variation of the
* Towers of Hanoi puzzle. A Decoder object has a method that
* takes a move number as input and returns a Move1 object; a
* solution to the puzzle associated with the Decoder object is
* formed by the sequence of moves produced by calling the method
* repeatedly, each time passing the next step number, beginning
* with step 1 and repeating m times, where m is the minimum
* number of moves required to solve the puzzle.
*/
private static class Decoder
{
final int evenTick, origin;
public Decoder(int n, int f, int t)
{
int d = Get.distance(f, t);
int magnitude = d == 0 ? 0 : 1;
int sign = d == 1 ? 1 : -1;
sign *= f > t ? 1 : -1;
sign *= Get.isEven(n) ? 1 : -1;
this.evenTick = sign * magnitude;
this.origin = f;
}
public Move1 toMove1(int moveNumber)
{
int i, diskNumber = 0;
for (i = moveNumber; Get.isEven(i); i = i >> 1)
diskNumber++;
final int tickCount = i >> 1;
final int tick = Get.isEven(diskNumber) ? evenTick : -evenTick;
final int f = Get.pegNumber(origin + (tick * tickCount));
final int t = Get.pegNumber(f + tick);
return new Move1(f, t);
}
}
}
/*
* 3. Utility Functions
*/
/**
* The Get class is a collection of assorted utility functions that are
* used by various other methods.
*/
class Get
{
public static boolean isEven(int i)
{
return (1 & i) == 0;
}
public static int numDisks(String s)
{
int n;
try { n = Integer.parseInt(s); }
catch (Exception e) { n = 0; }
return n < 0 ? 0 : n;
}
public static int pegNumber(String s)
{
int i;
try { i = Integer.parseInt(s); }
catch (Exception e) { i = 0; }
return pegNumber(i);
}
public static int pegNumber(int i)
{
return pegNumber(i, 3);
}
public static int pegNumber(int i, int numPegs)
{
return (i + numPegs) % numPegs;
}
public static int distance(int f, int t)
{
int diff = f - t;
return diff < 0 ? -diff : diff;
}
public static int numMoves1(int n, int f, int t)
{
return (n < 1 || f == t) ? 0 : numMoves1(n);
}
public static int numMoves2(int n, int f, int t)
{
return numMoves2(n, distance(f, t));
}
private static int numMoves1(int n)
{
return (n == 1) ? 1 : 1 + (numMoves1(n - 1) * 2);
}
private static int numMoves2(int n, int d)
{
if (n < 1) return 0;
if (n == 1) return d;
if (d == 1) return (numMoves2(n - 1, 1) * 3) + 1;
return d * numMoves2(n, 1);
}
}
/*
* 4. Move Data Types
*/
abstract class Move
{
private int f, t;
public Move(int f, int t)
{
set(f, t);
if (f < 0 || t < 0) invalidate();
}
public void invalidate()
{
set(-1, -1);
}
public void set(int f, int t)
{
this.f = f;
this.t = t;
}
public String toString()
{
return toJsonObject();
}
public String toCsv()
{
return f + "," + t;
}
public String toJsonObject()
{
return "{from:" + f + ",to:" + t + "}";
}
}
class Move1 extends Move
{
public Move1(int f, int t)
{
super(f, t);
if (f > 2 || t > 2) invalidate();
}
}
class Move2 extends Move1
{
public Move2(int f, int t)
{
super(f, t);
if (Get.distance(f, t) > 1) invalidate();
}
}
/*
* 5. Moves Data Types
*/
abstract class Moves
{
public abstract Iterator getIterator();
public abstract Moves append(Move move);
public String toCsv()
{
String s = "";
Iterator i = this.getIterator();
if (!i.done())
{
s = i.getNext().toString();
while (!i.done())
s += "," + i.getNext().toString();
}
return s;
}
public String toJsonArray()
{
return "[" + toCsv() + "]";
}
public String toJsonObject()
{
return "{moves:" + toJsonArray() + "}";
}
public String toString()
{
return toJsonObject();
}
}
class ArrayOfMoves extends Moves
{
private final int capacity;
private int nextIndex = 0;
private Move[] array;
public ArrayOfMoves(int capacity)
{
this.capacity = capacity;
this.array = new Move[capacity];
}
public ArrayOfMoves append(Move move)
{
this.array[nextIndex++] = move;
return this;
}
public ArrayIterator getIterator()
{
return new ArrayIterator(this.array);
}
public int getCapacity()
{
return capacity;
}
}
class ListOfMoves extends Moves
{
private List list = new List();
public ListOfMoves append(Move move)
{
this.list.append(new List.Node(move));
return this;
}
public ListIterator getIterator()
{
return new ListIterator(this.list);
}
}
/*
* 6. Iterator Data Types
*/
interface Iterator
{
public boolean done();
public Object getNext();
}
class ArrayIterator implements Iterator
{
private final Object[] array;
private final int last;
private int i = -1;
public ArrayIterator(Object[] array)
{
this.array = array;
this.last = array.length - 1;
}
public boolean done()
{
return i >= last;
}
public Object getNext()
{
return array[++i];
}
}
class ListIterator implements Iterator
{
private final List list;
private List.Node current;
public ListIterator(List list)
{
this.list = list;
this.current = new List.Node(null, list.head);
}
public boolean done()
{
return current.next == null;
}
public Object getNext()
{
current = current.next;
return current.value;
}
}
/*
* 7. List Data Type
*/
class List
{
public Node head = null;
public Node tail = null;
public void append(Node node)
{
if (tail == null)
head = tail = node;
else
tail = tail.next = node;
}
public static class Node
{
public final Object value;
public Node next;
public Node(Object value, Node next)
{
this.value = value;
this.next = next;
}
public Node(Object value)
{
this(value, null);
}
}
}
/*
* Further Reading
*/
// Computer Science: An Interdisciplinary Approach
// by Robert Sedgewick and Kevin Wayne
// Section 2.3 Recursion (Towers of Hanoi, p. 268)
// Concrete Mathematics: A Foundation for Computer Science
// by Graham, Knuth, and Patashnik
// Section 1.1. The Tower of Hanoi
/* .:....1....:....2....:....3....:....4....:....5....:....6....:....7.. */