// RecursionDemo.java
// Created on Thu Aug 07 09:28:38 EDT 2008

import java.util.*;

@SuppressWarnings("unchecked")
public class RecursionDemo {
   
   public static int pascal(int row, int col) {
      // BASE CASE
      if ((row == 0) || (col == 0) || (col == row))
         return 1;
      // RECURSIVE CASE
      return pascal(row-1,col-1) + pascal(row-1,col);
   }
   
   /////////////////////////////////
   // Memoized (fast) Pascal
   /////////////////////////////////
   
      
   private static HashMap memoizedValues = new HashMap();
   
   public static int memoizedPascal(int row, int col) {
      // USE MEMOIZED VALUE (if there is one)
      RowCol key = new RowCol(row, col);
      Integer memoizedValue = (Integer) memoizedValues.get(key);
      if (memoizedValue != null)
         return memoizedValue;
         
      // BASE CASE
      int result;
      if ((row == 0) || (col == 0) || (col == row))
         result = 1;
      // RECURSIVE CASE
      else
         result = memoizedPascal(row-1,col-1) + memoizedPascal(row-1,col); 
      
      // MEMOIZE RESULT
      memoizedValues.put(key, result);
      return result;
   }

   /////////////////////////////////
   // Verbose (instrumented) Pascal
   /////////////////////////////////
   
   public static int verbosePascal(int row, int col) {
      return verbosePascal(row,col,0);
   }
   
   public static void indent(int depth) {
      for (int i=0; i<depth; i++) System.out.print("  ");
   }

   public static int verbosePascal(int row, int col, int depth) {
      indent(depth);
      System.out.println("vb(" + row + "," + col + ")");
      int result;
      // BASE CASE
      if ((row == 0) || (col == 0) || (col == row))
         result = 1;
      // RECURSIVE CASE
      else
         result = verbosePascal(row-1,col-1,depth+1) + verbosePascal(row-1,col,depth+1);
      indent(depth);
      System.out.println("--> " + result);
      return result;
   }
   
   public static void testPascal() {
      System.out.println("In testPascal... ");
      assert(pascal(0,0) == 1);
      assert(pascal(4,1) == 4);
      assert(pascal(4,2) == 6);
      for (int row=0; row<8; row++) {
         for (int col=0; col<=row; col++)
            System.out.printf("%10d ",pascal(row,col));
         System.out.println();
      }
      System.out.println("Calling verbosePascal(4,2)");
      verbosePascal(4,2);
      System.out.println("Passed all tests!");
   }
   
   public static void testPascalSpeed() {
      // System.out.println(pascal(40,30)); // 21433 ms
      System.out.println(memoizedPascal(40,30)); // 9 ms
   }
   
   public static void towersOfHanoi(int pieces) {
      towersOfHanoi(pieces,0,1,2);
   }
   
   private static int moveNumber = 0;
   
   public static void towersOfHanoi(int pieces, int from, int to, int aux) {
      // BASE CASE
      if (pieces == 1)
         System.out.println("Move #" + (++moveNumber) + " from " + from + " to " + to);
      // RECURSIVE CASE
      else {
         towersOfHanoi(pieces-1, from, aux, to);
         towersOfHanoi(1, from, to, aux);
         towersOfHanoi(pieces-1, aux, to, from);
      }
   }

   public static void main(String[] args) {
      // testPascal();
      // testPascalSpeed();
      towersOfHanoi(4);
   }
   
}

class RowCol {
   private int row, col;
   public RowCol(int row, int col) {
      this.row = row;
      this.col = col;
   }
   public int getRow() { return this.row; }
   public int getCol() { return this.col; }
   public boolean equals(Object obj) {
      if (!(obj instanceof RowCol)) return false;
      RowCol that = (RowCol)obj;
      return ((this.row == that.row) && (this.col == that.col));
   }
   public int hashCode() { return (this.row+17)*(this.col+33131); }
   public String toString() { return "RowCol("+this.row + "," + this.col + ")"; }
}