/** Hanoi.java -- This is the classic "Towers of Hanoi" puzzle.
 *  In some oriental monastery, monks want to move a stack of disks from
 *  one peg to another.  The disks are so heavy (or the monks are so weak)
 *  that only one disk may be moved at one time.  Also, we must ensure that
 *  we never place a disk on top of a smaller disk.
 *  A third peg is available for temporary storage of disks.
 *  Legend has it that the monks want to move a stack of 64 disks, and when
 *  their task is completed, this will signal the end of the world.
 *  So let's not try to optimize their strategy!
 */
import java.io.*;

public class Hanoi
{
  /** The idea is that we have n disks that need to move from peg A to peg C.
   *  We don't know immediately how to do it, but we can break up the
   *  problem as follows.  Suppose we knew a way of moving n-1 of the disks.
   *  1.  Move n-1 disks from A to B.  (Use C as needed for temp storage.)
   *  2.  Move the bottom disk from A to C.
   *  3.  Move the n-1 disks from B to C.  (Use A as needed for temp storage.)
   *  Now, this recursive solution begs the question of a base case.  How
   *  can we move 1 peg from A to B or from B to C?  This can be accomplished
   *  in a single, direct transfer because the destination peg will be empty.
   */
  public static void main(String [] args) throws IOException
  {
    System.out.print("How many disks?  ");
    BufferedReader kbd = new BufferedReader(new InputStreamReader(System.in));
    int numDisks = Integer.parseInt(kbd.readLine());
    System.out.printf("\nYou entered %d\n", numDisks);

    // Now we want to move this many disks from peg A to peg C.
    move(numDisks, 'A', 'C', 'B');
  }

  /** This is our recursive move function.
   */
  public static void move(int n, char source, char destination, char temp)
  {
    if (n == 1)
    {
      System.out.printf("move(%d):  base case, simply move %c -> %c\n",
			n, source, destination);
    }
    else
    {
      System.out.printf("move(%d):  Step 1 - need to move %d disks from " +
			"%c to %c\n", n, n-1, source, temp);
      move(n-1, source, temp, destination);

      System.out.printf("move(%d):  Step 2 - directly move %c -> %c\n",
			n, source, destination);

      System.out.printf("move(%d):  Step 3 - need to move %d disks from " +
			"%c to %c\n", n, n-1, temp, destination);
      move(n-1, temp, destination, source);
    }
  }
}