Skip to content

Instantly share code, notes, and snippets.

@masious
Last active August 29, 2015 14:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save masious/655baa478507ab22a2a5 to your computer and use it in GitHub Desktop.
Save masious/655baa478507ab22a2a5 to your computer and use it in GitHub Desktop.
Hanoi Tower Program in Java to calculate token time to solve it and its order
//Algorithm and implemention by Masoud Bonabi
import java.util.Stack;
public class Main {
static Stack[] pipes;
final static int N = 3;
public static void solve(final int srcPipe,final int destPipe,final int solveFor){
if(solveFor == 0)
return ;
int finalPurpose = ((Integer)pipes[srcPipe].get(pipes[srcPipe].size()-solveFor)).intValue();
int unusedPipe = findUnusedPipe(srcPipe,destPipe);
if( solveFor > 1 )
solve(srcPipe, unusedPipe, solveFor-1);
int i = pipes[destPipe].size();
if(i>0){
i--;
while(i>=0 && ((Integer)pipes[destPipe].get(i)).intValue()<finalPurpose)
i--;
i = pipes[destPipe].size() - i - 1;
if( i > 0 )
solve(destPipe, unusedPipe, i);
}
pipes[destPipe].push(pipes[srcPipe].pop());
solve(unusedPipe,destPipe,solveFor-1);
}
private static int findUnusedPipe(int a,int b) {
boolean [] total = new boolean[3];
total[a] = true;
total[b] = true;
int answer = 0;
for(int i=0;i<total.length;i++)
if(!total[i]){
answer = i;
break;
}
return answer;
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
initPipes(N);
solve(0,2,N);
print();
System.out.println((System.currentTimeMillis() - a)/1000.0f + "seconds");
}
private static void print() {
for(int i=0;i<3;i++){
System.out.print(i+1+": ");
for(int j=0;j<pipes[i].size();j++)
System.out.print(((Integer)pipes[i].get(j)).intValue()+" ");
System.out.println();
}
}
private static void initPipes(int numberOfDisks) {
pipes = new Stack[3];
for(int i=0;i<pipes.length;i++)
pipes[i] = new Stack();
for(int i=numberOfDisks;i>0;i--)
pipes[0].push(new Integer(i));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment