/** implements the game "the towers of hanoi" */
public class Hanoi {
        public static int numDiscs;
        public static DiscStack startStack;
        public static DiscStack targetStack;
        public static DiscStack helpStack;
                        
        /** 
         * constructor of the Hanoi class. creates 3 discstacks to play with.
         *
         * @param p_numDiscs the number of discs that have to be moved
         */
        Hanoi(int p_numDiscs ) {
                numDiscs = p_numDiscs;
                startStack = new DiscStack(numDiscs, numDiscs, "startStack");
                targetStack = new DiscStack(numDiscs, 0, "targetStack");
                helpStack = new DiscStack(numDiscs, 0, "helpStack");
        }
        
        
        /** play function, implements the algorithm that solves the Hanoi problem */
        private void solve(int curHeight, DiscStack dstack1, DiscStack dstack2, DiscStack dstack3 ) {
                if(curHeight == 1) {
                        dstack2.push(dstack1.pop());
                        /* we're done at this point */
                }
                else {
                        solve(curHeight -1, dstack1, dstack3, dstack2);
                        dstack2.push(dstack1.pop());
                        solve(curHeight -1, dstack3, dstack2, dstack1);
                }
                
        }
        
        
        /** main program, creates a Hanoi instance to run the game */
        public static void main(String[] args) {
                int a_numDiscs = Integer.parseInt(args[0]);
                Hanoi myHanoi = new Hanoi(a_numDiscs);
                System.out.println("INFO : starting to play.");
                
                myHanoi.solve(startStack.curHeight, startStack, targetStack, helpStack);
                System.out.println("INFO : done.");
                startStack.show();
                targetStack.show();
                helpStack.show();
        }
}


/** class that represents a stack of discs, index = disc number, value = disc width. */
class DiscStack {
        public int[] dstack;
        public int curHeight;
        public int maxSize;
        String name;
        
        
        /** constructor of DiscStack class */
        public DiscStack(int p_maxSize, int p_curHeight, String p_name) {
                if(p_maxSize < p_curHeight || p_maxSize < 0 || p_curHeight < 0) {
                        System.out.println("ERROR : can't create such a weird DiscStack!");
                        System.exit(1);
                }
                else {
                        maxSize = p_maxSize;
                        curHeight = p_curHeight;
                        name = p_name;
                        
                        System.out.println("PLAY : creating discStack " + name + ", startsize " + curHeight + " of " + maxSize);
                        dstack = new int[maxSize];
                        
                        /* init the DiscStack, widest disc lies at the bottom */
                        for(int i = 0; i < curHeight; i++) {
                                dstack[i] = curHeight - i;
                                System.out.println("DEBUG : initializing disc " + i + " of stack " + name + " with width " + (curHeight -i));
                        }
                        System.out.println("DEBUG : size of stack " + name + " is now " + curHeight);
                        show();
                }
        }
        
        
        /** prints the discStack */
        public void show() {
                System.out.println("showing structure of diskStack " + name + " : ");
                for(int i = 0; i < dstack.length; i++) {
                        System.out.println("element " + i + " has value " + dstack[i]);
                }       
        }
        
        
        /** removes the up-most disc from the DiscStack */
        public int pop() {
                if(dstack.length <= 0 || curHeight <= 0) {
                        System.out.println("ERROR : Trying to pop() from empty Stack. Exiting.");
                        System.exit(1);
                }
                
                int topDiscSize = dstack[curHeight -1];
                
                if(topDiscSize <= 0) {
                        System.out.println("WARNING : trying to remove disc of length zero from " + name + ".");
                }
                
                dstack[curHeight -1] = 0;
                curHeight--;
                System.out.println("PLAY : removed disc of size " + topDiscSize + " from dstack " + name + ".");
                return(topDiscSize);
        }
        
        
        
        /** places a disc on top of the DiscStack */
        public boolean push(int discSize) {
                if(curHeight >= dstack.length)  {
                        System.out.println("ERROR : dStack " + name + " full , can't push(). Exiting.");
                        System.exit(1);
                }
                
                if(discSize <= 0) {
                        System.out.println("ERROR : discSize to small (not a disc!), can't push to " + name);
                        System.exit(1);
                }
                
                if(curHeight == 0) {
                        curHeight++;
                        System.out.println("PLAY : added disc of size " + discSize + " to empty dstack " + name + ".");
                        dstack[curHeight -1] = discSize;        
                }
                else {
                        if(discSize < dstack[curHeight -1]) {
                                curHeight++;
                                System.out.println("PLAY : added disc of size " + discSize + " to dstack " + name + ".");
                                dstack[curHeight -1] = discSize;
                        }
                        else {
                                System.out.println("ERROR : disc to wide (" + discSize + "), not allowed to place it on " + name + " (" + dstack[curHeight -1] + ").  Exiting.");
                                System.exit(1);
                        }
                }
                return(true);
        }
        
        
        
}