import java.io.*;

public class Hanoi{

public static int numberOfDisks;
public static String startPole;
public static String tempPole;
public static String endPole;
public static int counter;

/* choose 1 disk as the base case */
public static void solveTowers(int numberOfDisks, String startPole, String tempPole, String endPole){
	if(numberOfDisks==1){
		System.out.println("Move Disk #"+numberOfDisks+" from "+ startPole +" to "+ endPole);
		counter++;
		return;
	}
	solveTowers(numberOfDisks-1, startPole, endPole, tempPole);
	System.out.println("Move Disk #"+numberOfDisks+" from "+ startPole +" to "+ endPole);
	counter++;
	solveTowers(numberOfDisks-1, tempPole, startPole, endPole);	
}

/* alternatively, choose 0 disk as the base case*/
public static void solveTowers2(int numberOfDisks, String startPole, String tempPole, String endPole){
	if(numberOfDisks==0){
		return;
	}
	solveTowers2(numberOfDisks-1, startPole, endPole, tempPole);
	System.out.println("Move Disk #"+numberOfDisks+" from "+ startPole +" to "+ endPole);
	counter++;
	solveTowers2(numberOfDisks-1, tempPole, startPole, endPole);	
}

public static void main(String[] args){
	while(readArgs()!=0){
		counter=0;
		solveTowers(numberOfDisks, startPole, tempPole, endPole);
		//solveTowers2(numberOfDisks, startPole, tempPole, endPole);
		System.out.println("total moves = " + counter);
	}
}

/* read args from user input */
/* return 0, if user doesn't want to play any more */
public static int readArgs(){
	try{
	        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	        String s;
	        
	        do{
	        	System.out.print("Start the game?('y' or 'n')");
	        	s=in.readLine();
	        	if(s.trim().equalsIgnoreCase("y")) break;
	        	if(s.trim().equalsIgnoreCase("n")) {in.close(); return 0;}
	        }while(true);
	        
		do{
			System.out.print("please input numberOfDisks (numberOfDisks>0):");
			try{
				numberOfDisks = Integer.parseInt(in.readLine().trim());
				if(numberOfDisks>0) break;
			}catch(NumberFormatException e){
				/* continue to request input a number */
			}
		}while(true);
		
		System.out.print("please input startPole:");
		startPole=in.readLine().trim();
		System.out.print("please input tempPole:");
		tempPole=in.readLine().trim();
		System.out.print("please input endPole:");
		endPole=in.readLine().trim();
		return 1;	
	}catch(IOException e){
		return 0;
	}
}
}