Hanoi.java

Go to the documentation of this file.

package aud.example;
 
import aud.Stack;
 
class Hanoi {
 
  public static void recursive_solve(int n) {
    move_towers(n,0,2,1);
  }
 
  private static void move_disk(int from,int to) {
    System.out.println("move disk from "+from+" to "+to);
  }
  //@<hanoi:movetowers
  private static void move_towers(int n,int from,int to,int free) {
    if (n==1)
      move_disk(from,to);
    else {
      move_towers(n-1,from,free,to);
      move_disk(from,to);
      move_towers(n-1,free,to,from);
    }
  }
  //@>hanoi:movetowers
 
  public static void recursive_solve_1(int n) {
    move_towers_1(n,0,2,1);
  }
 
  private static void move_towers_1(int n,int from,int to,int free) {
    while (n>1) {
      move_towers_1(n-1,from,free,to);
      move_disk(from,to);
 
      --n;
      int t=from; from=free; free=t;
    }
 
    move_disk(from,to); // n=1
  }
 
  public static void iterative_solve(int n) {
    move_towers_iterative(n,0,2,1);
  }
 
  private static class Configuration {
    Configuration(int n,int from,int to,int free) {
      this.n=n;
      this.from=from;
      this.to=to;
      this.free=free;
    }
    int   n;
    int   from, to, free;
  }
 
  private static void move_towers_iterative(int n,int from,int to,int free) {
 
    Stack<Configuration> stack=new Stack<Configuration>();
 
    boolean done=false;
 
    DESCEND: do {
      while (n>1) {
        stack.push(new Configuration(n,from,to,free)); // save
        --n;
        int t=to; to=free; free=t;
      }
 
      do {
        while (n>1) {
 
          move_disk(from,to);
 
          --n;
          int t=from; from=free; free=t;
 
          continue DESCEND; // essentially a GOTO (ugly!)
                            // alternatively copy 1st while loop (we have n==1!)
        }
        move_disk(from,to); // n=1
 
        if (stack.is_empty()) {
          done=true;
        }
        else {
          Configuration c=stack.pop();
          n=c.n; from=c.from; to=c.to; free=c.free;    // restore
        }
      } while (!done);
    } while (!done);
  }
 
 
 
  public static class InorderIterator implements java.util.Iterator<String> {
 
    protected class Node extends Configuration {
      public Node(int n,int from,int to,int free) {
        super(n,from,to,free);
      }
      @Override public String toString() {
        return "move disk from "+from+" to "+to;
      }
 
      public Node getLeft() {
        return n>1 ? new Node(n-1,from,free,to) : null;
      }
      public Node getRight() {
        return n>1 ? new Node(n-1,free,to,from) : null;
      }
    }
 
    Stack<Node> stack_ = new Stack<Node>();
 
    InorderIterator(int n) {
      stack_.push(new Node(n,0,2,1));
      descendLeft();
    }
 
    private void descendLeft() {
      Node node=stack_.top();
      for (node=node.getLeft();node!=null;node=node.getLeft())
        stack_.push(node);
    }
 
    @Override public String next() {
      Node node=stack_.pop();
      if (node.getRight()!=null) {
        stack_.push(node.getRight());
        descendLeft();
      }
 
      return node.toString();
    }
 
    @Override public boolean hasNext() {
      return !stack_.is_empty();
    }
    @Override public void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
  public static class Inorder implements Iterable<String>{
    int n_;
    Inorder(int n) { n_=n; }
    @Override public java.util.Iterator<String> iterator() {
      return new InorderIterator(n_);
    }
  }
 
  public static Inorder solution(int n) {
    return new Inorder(n);
  }
 
 
  public static void main(String args[]) {
    int n=Integer.parseInt(args[0]);
    System.out.println("recursive solution:\n");
    recursive_solve(n);
 
    System.out.println("\nrecursive solution w/o end-recursion:\n");
    recursive_solve_1(n);
 
    System.out.println("\niterative solution:\n");
    iterative_solve(n);
 
    System.out.println("\niterative solution using inorder iterator:\n");
    for (String move : Hanoi.solution(n)) {
      System.out.println(move);
    }
  }
}