Skip to content

Instantly share code, notes, and snippets.

@JamesEarle

JamesEarle/Iterative

Last active March 11, 2019 01:48
Show Gist options
  • Save JamesEarle/7558399 to your computer and use it in GitHub Desktop.
Save JamesEarle/7558399 to your computer and use it in GitHub Desktop.
Download ZIP
Iterative vs. Recursive Tower of Hanoi
Raw
Iterative
import java.util.Stack;
/* An iterative approach to the Tower of Hanoi puzzle. Uses
* 3 stacks as a representation to replace the recursive method
* and approaches all possible legal moves between every peg
* combination at any point in the puzzle.
*
* @author James Earle
*/
public class PartC {
Stack<Integer> a,b,c;
int n,ctr;
double limit;
public PartC() {
a = new Stack();
b = new Stack();
c = new Stack();
ctr = 1;
}
private void runClass () {
//n is the number of disks -1, for a 0 based representation.
n = 4;
limit = (Math.pow(2.0, ((double)(n+1))))-1;
System.out.println("The limit is " + ((int)limit) + " moves.");
for (int i=n; i>=0; i--) {
a.push(i);
}
if (determine(n+1) == true) {
//Set of steps for an even number of disks.
//A-B Combinations
for (int i=0; i<limit; i++) {
if (a.empty() && b.empty()) break;
if (b.empty() == true) {
b.push(a.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from A to B");
} else if (a.empty() == true) {
a.push(b.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from B to A");
} else if (minVal(a,b) == true) {
a.push(b.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from B to A");
} else {
b.push(a.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from A to B");
} //end of A-B combinations
//A-C combinations
if (c.empty() && a.empty()) break;
if (c.empty() == true) {
c.push(a.pop());
System.out.println(ctr++ + ": Disk "
+ c.peek() + " from A to C");
} else if (a.empty() == true) {
a.push(c.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from C to A");
} else if (minVal(a,c) == true){
a.push(c.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from C to A");
} else {
c.push(a.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from A to C");
} //end of A-C combination
//C-B combinations
if (b.empty() && c.empty()) break;
if (b.empty() == true) {
b.push(c.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from C to B");
} else if (c.empty() == true) {
c.push(b.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from B to C");
} else if (minVal(c,b) == true) {
c.push(b.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from B to C");
} else {
b.push(c.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from C to B");
} //end of C-B combinations
}
} else {
//Set of steps for an odd number of disks.
//A-C combinations
for (int i=0; i<limit; i++) {
if (a.empty() && c.empty()) break;
if (c.empty() == true) {
c.push(a.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from A to C");
} else if (a.empty() == true) {
a.push(c.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from C to A");
} else if (minVal(a,c) == true){
a.push(c.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from C to A");
} else {
c.push(a.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from A to C");
} //end of A-C combinations
//A-B combinations
if (b.empty() && a.empty()) break;
if (b.empty() && !a.empty()) {
b.push(a.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from A to B");
} else if (a.empty() && !b.empty()) {
a.push(b.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from B to A");
} else if (minVal(a,b) == true) {
a.push(b.pop());
System.out.println(ctr++ + ": Disk " + a.peek()
+ " from B to A");
} else {
b.push(a.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from A to B");
} //and of A-B combinations
//C-B combinations
if (b.empty() && c.empty()) break;
if (b.empty() == true) {
b.push(c.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from C to B");
} else if (c.empty() == true) {
c.push(b.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from B to C");
} else if (minVal(c,b) == true) {
c.push(b.pop());
System.out.println(ctr++ + ": Disk " + c.peek()
+ " from B to C");
} else {
b.push(c.pop());
System.out.println(ctr++ + ": Disk " + b.peek()
+ " from C to B");
} //end of C-B combinations
}
}
}
private static boolean minVal(Stack<Integer> x, Stack<Integer> y) {
if (x.peek() > y.peek()) {
return true;
} else {
return false;
}
} //minVal
private static boolean determine(int n) {
if (n%2 == 0) {
return true;
} else {
return false;
}
} //determine
public static void main (String[] args) { PartC c = new PartC();
c.runClass();
} //main
} //PartC
Raw
Recursive
/* A recursive solution to the Tower of Hanoi puzzle,
* demonstrating it's complexity when compared to an
* iterative solution.
*
* @author James Earle
*/
public class Assign1 {
/* Each char variable represents a peg
* for the disks to be placed on. This
* allows for the printed output.
*/
static char a = 'A';
static char b = 'B';
static char c = 'C';
static int ctr = 0;
public static void main(String[] args) {
moveTower(4,a,b,c);
}
public static void moveTower (int disk, char source,
char dest, char spare) {
if (disk == 0) {
ctr++;
System.out.println(ctr + ": Disk " + disk + " from "
+ source + " to " + dest);
}
else {
moveTower(disk-1,source,spare,dest);
ctr++;
System.out.println(ctr + ": Disk " + disk + " from "
+ source + " to " + dest);
moveTower(disk-1,spare,dest,source);
}
} //moveTower
} //Assign1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment