/*

   Purpose:

     This program illustrates recursion as used to develop

     a solution to the Towers of Hanoi problem.  The user

     enters a number for the size of the stack of disks

     to move, and the program displays the moves in a

     simplified text-based illustration. A 2D array of

     ints is used to represent the stacks of disks,

     with rows of the array representing the towers,

     and numbers within each row representing disks

     of different sizes, larger numbers representing larger

     disks.



   Record of revisions:

    Date                Programmer          Description of change

    ====                ==========          =====================

    February 2002       J. Rodger           Adapted Original from web examples

    June 2002           J. Rodger           added documentation

    February 2003       J. Rodger           adapted to apsc142 I/O

    March 2003          J. Rodger           minor cleanup

    May 2003            J. Rodger           back to hsa package

*/

// The Hanoi class

import hsa.*;

public class Hanoi

{

    // global variables



    // towers array used to represent the stacks of disks

    // 4 rows, row 0 unused so that row numbers can directly

    // represent towers

    public static int [] [] towers = new int [4] [];

    // numdisks the original stack size

    public static int numDisks = 0;



    // moves disk, represented by the int num

    // from one tower to another, from a to b

    public static void moveDisk (int num, int a, int b)

    {

	int i = numDisks;



	// scan down to disk location on tower a

	while (towers [a] [i] == 0)

	    i--;

	// remove disk from tower a

	towers [a] [i] = 0;

	i = 1;

	// scan up to empty level on tower b

	while (towers [b] [i] != 0)

	    i++;

	// add disk on tower b

	towers [b] [i] = num;

    } // end method moveDisk





    // method to display current problem status

    // simple display uses rows of asterisks

    // to represent disks

    public static void showDisks ()

    {

	int i = numDisks, j = 0;

	for (i = numDisks ; i > 0 ; i--)

	{

	    Stdout.print ("\t\t");

	    for (j = 0 ; j < towers [1] [i] ; j++)

		Stdout.print ("*");

	    Stdout.print ("\t\t");

	    for (j = 0 ; j < towers [2] [i] ; j++)

		Stdout.print ("*");

	    Stdout.print ("\t\t");

	    for (j = 0 ; j < towers [3] [i] ; j++)

		Stdout.print ("*");

	    Stdout.println ();



	}

	Stdout.println ("\t\t1\t\t2\t\t3\n");

    } // end method showDisks





    // recursive method that implements the solution

    // to the Towers of Hanoi puzzle

    // move a stack of numDisks n from place a to place b,

    // where  a  and  b  belong to {1,2,3}, using c as "spare"

    public static void moveStack (int n, int a, int b, int c)

    {

	// if n is 0, already moved, no recursion

	if (n > 0)

	{

	    // move top n-1 disks to free place

	    moveStack (n - 1, a, c, b);

	    Stdout.print ("move Disk " + n);

	    Stdout.println (" from " + a + " to " + b);



	    // then move disk n from source to destination

	    moveDisk (n, a, b);

	    showDisks ();



	    // move top n-1 disks from free place to destination

	    moveStack (n - 1, c, b, a);

	}

    }





    public static void main (String [] args)

    {

	Stdout.print ("Enter number of disks to move from Tower 1 to Tower 3: ");

	numDisks = Stdin.readInt ();

	Stdout.println ();

	Stdout.println ("Tower of Hanoi with " + numDisks + " disks");



	// size global array rows according to number of Disks

	towers [1] = new int [numDisks + 1];

	towers [2] = new int [numDisks + 1];

	towers [3] = new int [numDisks + 1];



	// initialize all disks on tower 1

	// position 0 unused in each row so that contents

	// can directly represent disk number (size)

	for (int i = 1 ; i <= numDisks ; i++)

	{

	    towers [1] [i] = numDisks + 1 - i;

	    towers [2] [i] = 0;

	    towers [3] [i] = 0;



	}

	showDisks ();



	moveStack (numDisks, 1, 3, 2);

    } // end main method

} // end class Hanoi