TowersOfHanoi.java

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class TowersOfHanoi {

    /**
    *   Program:    TowersOfHanoi.java by  Chris Clarke
    *   Created:    22.01.2007
    *   Purpose:    Working graphic model of the well-known
    *           "Towers of Hanoi" challenge: move all disks one by one
    *           from one peg to another, ensuring that each disk is always
    *           placed on top of one that is larger than itself.
    *           Method "goRight" added 18.12.2009.
    *   Modified:   21.09.2012 (JFrame)
    */

    public static void main(String[] args) {
        TowersOfHanoiJFrame frame = new TowersOfHanoiJFrame();
        frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE);
        // Set to a reasonable size.
        frame.setSize(700, 400);
        frame.setVisible(true);
    }
}

class TowersOfHanoiJFrame extends JFrame implements ActionListener {
    public TowersOfHanoiJFrame() {
        Container contentPane = getContentPane();
        userControlPanel = new JPanel();
        chSpeed = new Choice();
        chSpeed.add("Slow");
        chSpeed.add("Fast");
        chSpeed.add("Lightning");
        chSpeed.select(1);  // fast
        userControlPanel.add(chSpeed);
        btn = new JButton[max];
        for (int i=0; i<max; i++) {
            btn[i]=new JButton(""+(i+1));
            btn[i].addActionListener(this);
            userControlPanel.add(btn[i]);
        }
        contentPane.add(userControlPanel, BorderLayout.SOUTH);
        setTitle("Towers of Hanoi by Chris Clarke");
    }

    public void update(Graphics g) {
        paint(g);
    }

    public void paint(Graphics g) {
        String str;
        if (!stacksInitialised) initStax(); // set disks to start position
        redraw(g);

        if (play) {
            str=calcAlgorithm(n);   // calculate the algorithm as a String
            // disks are to end up on right-hand peg
            // only applies to odd number of disks
            if (pegRight&&n%2==1)
                str=goRight(str);
            for (int i=0; (i+2)<=str.length(); i+=2) {
                String s1 = str.substring(i, i+1);   // 1st char of 2
                String s2 = str.substring(i+1, i+2); // 2nd char of 2
                // convert Strings to ints
                int stFrom=Integer.parseInt(s1);
                int stTo=Integer.parseInt(s2);
                // move disk, in array hanoi, from stack stFrom to stTo
                doPush(stTo, doPop(stFrom));
                try {
                    if (chSpeed.getSelectedIndex()==0)
                            Thread.sleep(1000); // pause for 1 second
                    else if (chSpeed.getSelectedIndex()==1)
                            Thread.sleep(333); // pause for 1/3 second
                    else if (chSpeed.getSelectedIndex()==2)
                            Thread.sleep(50); // pause for 1/20 second
                } catch (InterruptedException e) {}
                redraw(g);
            }
            play=false;
        }
    }

    public String goRight(String s) {
        // convert string to ensure disks always end up on the right-hand disk
        String result="";
        for (int i=0; i<s.length(); i++) {
            String temp=s.substring(i, i+1);
            // peg 2 becomes peg 1 and vice versa; peg 0 remains unchanged
            if (temp.equals("1"))
                result+="2";
            else if (temp.equals("2"))
                result+="1";
            else result+=temp;
        }
        return result;
    }

    public void redraw(Graphics g) {
        deleteDiscs(g);
        drawColumns(g);
        drawDiscs(g);
    }

    public void initStax() {
        hanoi = new int[3][max];
        for (int i=0; i<=2; i++)
            for (int j=0; j<max; j++)
                hanoi[i][j]=0;

        for (int i=0; i<n; i++)
            hanoi[0][i]=i+1;    // hanoi[0][0]=1 is top of stack

        disksOnStack = new int[3];
        disksOnStack[0]=n;      // n is the number of disks user chose
        disksOnStack[1]=0;
        disksOnStack[2]=0;
        stacksInitialised=true;
    }

    public void doPush(int stk, int currDisk) { // onto top of stack
        for (int i=n-1; i>0; i--)
            hanoi[stk][i]=hanoi[stk][i-1];  // shuffle the rest down
        hanoi[stk][0]=currDisk; // top of stack
        disksOnStack[stk]++;
    }

    public int doPop(int stk) {         // from top of stack
        int currDisk=hanoi[stk][0]; // top of stack
        for (int i=0; i<n-1; i++)
            hanoi[stk][i]=hanoi[stk][i+1];  // shuffle the rest up
        disksOnStack[stk]--;
        return currDisk;
    }

    public String calcAlgorithm(int i) { // uses recursion to calculate algorithm
        // when n=1, Hanoi(n)="01"
        if (i==1)
            return "01";    // "Remove disk from column 0,
                    // and place it on column 1."
        else {
            /** When n>1, the algorithm (formula) for n disks, is:-
             *  Hanoi(n) = Hanoi(n-1)+("02"or"01")+rm(Hanoi(n-1)),
             *  where:
             *    Hanoi(n-1) is the algorithm for n-1 disks;
             *    the "02" or "01" depends on whether n is even or odd;
             *    and rm is a function applied to Hanoi(n-1)
             */
            String formula = calcAlgorithm(i-1); // eg when #ofdisks=2 "01"
            String rm = reversedAndMirrored(formula, i); // eg     "12"
            if (i%2==0)
                formula += "02"; // with 2 disks: "01"+"02"="0102"
            else
                formula += "01";
            formula += rm;  // eg (when # of disks=2) "0102"+"12"="010212"
            return formula;
        }
    }

    public String reversedAndMirrored(String s, int n) {
        String s2 = "";
        // reversed sequence
        for (int i=s.length(); i>0; i--) {
            char ch = s.charAt(i-1);    // "01" backwards becomes "10"
            // mirrored left/right
            if (n%2==0) {   // even number of disks
                if (ch=='0') s2 += "2"; // swap left and right columns
                else if (ch=='2') s2 += "0"; // for even numbered n
                else s2 += ch;
            } else {
                if (ch=='0') s2 += "1"; // swap left and middle columns
                else if (ch=='1') s2 += "0"; // for odd numbered n
                else s2 += ch;
            }
        }
        return s2;
    }

    public void drawColumns(Graphics g) { // draw 'em
        g.setColor(Color.LIGHT_GRAY);
        g.fillRect(85, maxY-100, 555, 50);  // draw base
        for (int i=0; i<=2; i++) {
            g.fillRect(stackX[i], maxY-300, 30, 200); // stackX[0]=150

//          g.setColor(Color.white); // number them 0 to 2 on screen
//          g.drawString(" " + (i), stackX[i], maxY-75);
//          g.setColor(Color.LIGHT_GRAY);
        }
    }

    public void deleteDiscs(Graphics g) { // wipe the disks out
        g.setColor(Color.white);
        g.fillRect(85, 0, 555, 300);
    }

    public void drawDiscs(Graphics g) { // display contents of the array hanoi
        for (int i=0; i<=2; i++) {
            int d=disksOnStack[i];
            for (int j=d-1; j>=0; j--) {
                int currentDisk = hanoi[i][(d-j)-1];
                int y=(maxY-100)-((j+1)*sizeY);
                g.setColor(Color.black);
                g.drawRect(stackX[i]+14 - (sizeX[currentDisk-1]/2), y-1,
                  sizeX[currentDisk-1]+1, sizeY);
                g.setColor(Color.red);
                g.fillRect(stackX[i]+15 - (sizeX[currentDisk-1]/2), y,
                  sizeX[currentDisk-1], sizeY);
            }
        }
    }

    public void actionPerformed(ActionEvent e) { // user clicked a button
        for (int i=0; i<max; i++)
            if (e.getSource() == btn[i])
                n = i+1;
        play=true;
        stacksInitialised=false;
        repaint();
    }

    private JPanel userControlPanel;
    private JButton[] btn;
    Choice  chSpeed;        // slow, fast or lightning speed
    int max=10;         // The maximum number of disks.
    int n=1;            // The number of disks as chosen by you.
    int[][] hanoi;          // 3 by max array representing the stacks.
    int[] disksOnStack;     // max disks on stack 0, 0 on stack 1, 0 on stack 2
    int[] stackX= { 150, 350, 550 };    // x-coordinates of stacks
    int sizeY=20;           // Height of each disk.
    int[] sizeX = { 50, 60, 70, 80, 90, 100, 110, 120, 130, 140 };
    boolean play=false;
    boolean stacksInitialised=false;
    static boolean pegRight=true;   // if true, always move disks to right-hand peg
    int maxX = 700, maxY = 400; // The size of the window.
}