import java.util.logging.Level;
import java.util.logging.Logger;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 * even: right side move.
 * odd: left side move.
 */

/**
 *
 * @author Jefferson M. Fermo 
 * 
 * Iterative solution of tower of Hanoi.
 * 
 * 
 */
public class Hanoi {

    private Peg[] pegs;
    
    private final int NUMBEROFTOWERS = 3;
    
    private boolean directionOfMoveIsRight = false;
    
    private long numberOfMoves = 0;
    
    private int discCount = 0;
    
    int currentPeg = 0;
        
    int lastPegMove = 0;
    
    int moves = 0;
    
    public Hanoi(int discCount) throws Exception {
        
        this.discCount = discCount;
        
        // (N^2)-1
        numberOfMoves = (long) Math.pow(2, discCount)-1;
        
        System.out.println("moves: " + numberOfMoves);
        
        
        // determine the movement of disc based on its quantity.
        if (discCount % 2 == 1) {
            System.out.println("odd");
            directionOfMoveIsRight = false;
        }else{
            System.out.println("even");
            directionOfMoveIsRight = true;
        }            
        
        pegs = new Peg[NUMBEROFTOWERS];
        
        // create pegs with slots equal to the total number of disc.
        for (int cntr = 0; cntr < NUMBEROFTOWERS; cntr++) {
            pegs[cntr] = new Peg(discCount);
        }
        
        
        for (int cntr = 0; cntr < discCount; cntr++) {
            Disc disc = new Disc(discCount-cntr);
            
            pegs[0].populatePeg(disc);
        }
        
        System.out.println("Initial content");
        
        for (Peg peg1 : pegs) {
                System.out.println(peg1);
        }
        
        System.out.println("**************");
        
        //System.out.println("next peg transfer disc #" + nextPeg(pegs[1]).getPegNumber());
        
        
    }
    
    public void solve() throws Exception{
        
        for (moves = 0; moves < numberOfMoves; ) {
            
            Peg peg = pegs[currentPeg];
            
            moveDiscFromPeg(peg);
            
            if ((currentPeg == 0 & lastPegMove == 2) | (currentPeg == 2 & lastPegMove == 0)) {
                currentPeg = 1;
            }else if((currentPeg == 0 & lastPegMove == 1) | (currentPeg == 1 & lastPegMove == 0)){
                currentPeg = 2;
            }else if((currentPeg == 1 & lastPegMove == 2) | (currentPeg == 2 & lastPegMove == 1)){
                currentPeg = 0;
            }
            
        }
        
        for (Peg peg1 : pegs) {
            System.out.println(peg1);
        }
        
    }
    
    
    private int moveDiscFromPeg(Peg currentPeg) throws Exception{
    
        int invalidNextPeg = 0;
        
        int movesMade = 0;
        
        Peg peg = currentPeg;
        
        int lastPeg = 0;
        
        // there are only 2 possible moves in a 3 tower.
        while (invalidNextPeg <= 2) {         
            
            Peg nextPeg = nextPeg(peg);
            
            if (currentPeg.getPegNumber() == nextPeg.getPegNumber()) {
                return movesMade;
            }
            
            //System.out.println("is move legal? " + currentPeg.getPegNumber() + ", " + nextPeg.getPegNumber());
            
            if (isNextMoveLegal(currentPeg, nextPeg)){
                
                moveDisk(currentPeg, nextPeg);
                                
                moves++;
                
                invalidNextPeg = 0;
                
                lastPegMove = nextPeg.getPegNumber();
                
            }else{
                
                invalidNextPeg++;
                
            }
            
            peg = nextPeg;            
        }
    
        System.out.println("last peg: " + lastPeg);
            
        
        return movesMade;
    }
    
    /**
     * Checks if the move is legal from source to destination peg.
     * A move is legal if the following has been met:
     * 1. source peg contains a disc and destination peg is empty.
     * 2. disc at the top of destination peg is bigger than the disc on top of source peg. Both pegs are not empty.
     * A move is considered invalid if:
     * 3. source peg does not contain a disc and destination contains a disc.
     * 4. disc at the top of destination peg is smaller than the disc on top of source peg. Both pegs are not empty.
     * 5. both pegs does not contain a disc.
     * 
     * @param sourcePeg Peg where disc will be taken
     * @param destPeg   Peg where disc will be placed
     * @return  returns true if move is legal based on rule #1 and #2
     */
    
    private boolean isNextMoveLegal(Peg sourcePeg, Peg destPeg){
        
        // rule #1
        if (destPeg.getTopIndex() == -1 & sourcePeg.getTopIndex() != -1) {
            return true;
        // rule #3    
        }else if(sourcePeg.getTopIndex() == -1 & destPeg.getTopIndex() != -1){
            return false;
        }else if(sourcePeg.getTopIndex() != -1 && destPeg.getTopIndex() != -1){
            Disc sourceDisk = sourcePeg.readTopDisc();
            Disc destDisk = destPeg.readTopDisc();
            
            //rule #2
            if (destDisk.getSize() > sourceDisk.getSize()) {
                return true;
            //rule #4
            }else{
                return false;
            }
        //rule #5    
        }else if(sourcePeg.getTopIndex() == -1 & destPeg.getTopIndex() == -1){
            return false;
        }
        
        return false;
        
    }
    
    private Peg nextPeg(Peg currentPeg){
    
        int pegNumber = currentPeg.getPegNumber();
        
        int nextPegNumber = 0;
        
        if (directionOfMoveIsRight) {
            int tmp = pegNumber + 1;
            
            if (tmp < 3) {
                nextPegNumber = tmp;
            }else{
                nextPegNumber = 0;
            }
        }else{
            int tmp = pegNumber - 1;
            
            if (tmp < 0) {
                nextPegNumber = 2;
            }else{
                nextPegNumber = tmp;
            }
        }
        
        return pegs[nextPegNumber];
    }
    
    private boolean moveDisk(Peg sourcePeg, Peg destinationPeg) throws Exception{
    
        Disc disc = sourcePeg.getDisk();
        
        destinationPeg.putDisc(disc);        
        
        return false;
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        try {
            // create 3 towers(default) with disc from 1 to 25 ascending.
            Hanoi hanoi = new Hanoi(25);
            
            hanoi.solve();
            
        } catch (Exception ex) {
            Logger.getLogger(Hanoi.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
}


class Peg{

    private Disc[] disc;
    
    private int topIndex = -1;
    
    private int discCount = 0;
    
    private static int pegNumber = 0;
    
    private int myPegNumber = 0;
    
    Peg(int discCount){
        disc = new Disc[discCount];
        this.discCount = discCount;
        myPegNumber = pegNumber++;
    }

    public Disc readTopDisc(){
        
        if (topIndex == -1) {
            return null;
        }else{
            return disc[topIndex];
        }
        
    }

    public int getTopIndex() {
        return topIndex;
    }
    
    public Disc getDisk(){
        
        if (topIndex == -1) {
            return null;
        }else{
            Disc disk = this.disc[topIndex];
            this.disc[topIndex] = null;
            topIndex--;
            return disk;
        }
    }
    
    public void populatePeg(Disc disc) throws Exception{
        
        if (topIndex <= discCount) {
            topIndex++;
            
            this.disc[topIndex] = disc;
            System.out.print("Added disk #" + disc.getSize() + " at :" + topIndex + "\n");
            
        }else{
            throw new Exception("Peg overflowed with disk");
        }
    }
    
    public void putDisc(Disc disc) throws Exception{
        
        if (topIndex <= discCount) {
            topIndex++;
            
            this.disc[topIndex] = disc;
            //System.out.print("Added disk #" + disc + " at P" + myPegNumber + ":" + topIndex + "\n");
            
        }else{
            throw new Exception("Peg overflowed with disk");
        }
    }

    public int getPegNumber() {
        return myPegNumber;
    }
    
    
    @Override
    public String toString(){
    
        StringBuilder string = new StringBuilder();
        
        string = string.append("\nPeg #").append(myPegNumber).append("\t");
        
        for (int cntr = 0; cntr <= topIndex; cntr++) {
            string = string.append(disc[cntr].getSize()).append(",");
        }
        
        //string = string.append("\n");
        
        return string.toString();
    }
    
}

class Disc{

    int size;
    
    public Disc(int number) {
        size = number;
    }

    public int getSize() {
        return size;
    }
    
    @Override
    public String toString(){
        return "" + size;
    }
    
}