/*
 * T12n05.java:  The good ol' Towers of Hanoi problem.  Here's one
 * version of the story:
 *
 * There is a hidden monastery with three tall spires and a collection
 * of stone discs of various sizes with holes in their centers.
 * When the monastery was founded, the discs were neatly stacked on the
 * first spire, each disc smaller than the one beneath it.
 * The monks' task is to move the discs from that first spire to the
 * third, using the second to help.
 * Discs can be moved only one at a time (they're heavy),
 * they can only be placed on the spires (space is tight at the monastery),
 * and no disc may be placed on a smaller disc (lest they break).
 * When the pile has been completely relocated to the third spire,
 * the world will come to an end.
 *
 * What is the disc movement plan the monks are following to
 * accomplish this task?
 */

import java.util.*;

public class T12n05
{

        /*
         * movePile() -- Solves the Towers of Hanoi puzzle for a given
         *   number of discs on the given source spire that need to be
         *   moved to the specified destination spire with the help of
         *   the given helper spire.
         *
         *   The thing that amazes people when they see this for the first
         *   time is the lack of data structures; we don't store any discs
         *   or use stacks to represent spires.  The recursion and the
         *   nature of the problem make such representations unnecessary.
         *
         *   Precondition:  The spires have distinct numbers, and the
         *       number of discs is known.
         *   Postcondition: The steps to solve the given problem are
         *       displayed to the screen.
         */

    public static void movePile(int pileSize, int source, int destination,
                                int helper)
    {
        if (pileSize < 1) 
            return;

        movePile(pileSize - 1, source, helper, destination);
        System.out.println("Move the top disc from spire " + source
                         + " to spire " + destination);
        movePile(pileSize - 1, helper, destination, source);
    }


    public static void main (String [] args)
    {
        if (args.length < 1) {
            System.out.println("\n\tUSAGE:  java T12n04 <n>   where <n> is "
                             + "the number of discs in the starting pile.");
            System.exit(1);
        }

        int numberOfDisks = Math.abs(Integer.parseInt(args[0]));

        System.out.println("\n\t\tTowers of Hanoi");
        System.out.println("\nThe solution for " + numberOfDisks
                         + " discs is as follows:");

        movePile(numberOfDisks,1,3,2);

    }
}