/*                        CSC 17 Lab 7.


Part I.

  Part I of the lab asks you to think and experiment with the behavior
  of a program.  Please stay alert during the exercise and think about
  what lessons you are trying to learn.

  Imagine a square grid with cartesian coordinates.  Suppose you're at
  coordinate x,y: how many different routes can you take to get to the
  origin 0,0 (assuming that no intersections are blocked).  The
  "totalroutes" function in the program below implements a simple recursive
  algorithm to compute the answer.  The main program calls the function
  with command-line arguments and also reports the approximate time.

  Make sure you can run the program.  Make sure your machine is
  relatively free of other activity (type "top").  Run the program
  with x=14, y=13, then again with x=15, y=15.  Run these several times
  and note the average.

  Record the time it took for these computations.

  NOW I'M GOING TO GIVE YOU A CHOICE:

  You need to figure out how long it would take to run with x=40, y=40.
  You can choose to do this either experimentally or analytically.
  I leave the choice to you but I hope you would think carefully before
  proceeding: you must commit yourself to the choice.  If you do it
  analytically, you must show and explain your calculations carefully.
*/


public class routes
{
    static long totalroutes(int x, int y)
    {
	if (x==0 || y==0) return 1;
	else return totalroutes(x-1,y) + totalroutes(x,y-1);
    }

    public static void main(String[] args)
    {
	int x = Integer.parseInt(args[0]);
	int y = Integer.parseInt(args[1]);
	long result, t1, t2;
	t1 = System.currentTimeMillis();
	result = totalroutes(x,y);
	t2 = System.currentTimeMillis();
	System.out.printf("answer = %d, time = %dms\n",result,t2-t1);
    }
}

/*
Part II:

  There's a way to optimize the program.  The above program is inefficient
  because it is making too many redundant calls.  For example, 
  totalroutes(5,5) would call totalroutes(4,5) and totalroutes(5,4), but
  each of these calls will call totalroutes(4,4).  We really only want to
  compute totalroutes(4,4) once.

  You need to modify the program using a matrix (2D array) D.  The idea is,
  the array is initialized to all 0's (automatically).  Whenever you
  compute a value for totalroutes(i,j), you store the result in D[i][j].
  So now when you need to know what totalroutes(i,j) is, you first look
  at D[i][j].  If the value is not 0, you can just return the result without
  making any recursive calls.  

  You can base your program on the following example, which optimizes the
  naive Fibonacci implementation in a similar way.
*/

class fibs
{
    // naive implementation:
    static int fib(int n) { if (n<2) return 1; else return fib(n-1)+fib(n-2); }


    // Dynamic programming implementation using an array to store previously
    // computed values:

    static int[] M; // array to be used.

    // outer function initializes the array, then calls another function
    // for the recursive computation:

    static int dfib(int n)
    {
	if (n<2) return 1;
	M = new int[n+1];  M[0] = M[1] = 1;  // initialzes array
	return rfib(n);  // calls recursive function
    }

    // the modified recursive algorithm uses the array M to avoid redundant
    // recursive calls:

    static int rfib(int n)
    {
	if (M[n]!=0) return M[n];
	M[n] = rfib(n-1) + rfib(n-2);
	return M[n];
    }
}

/*
   After implementing the improved solutions, estimate BOTH analytically
   and experimentally how long it will take to compute "java routes 40 40".

   Report and explain your results.
*/