import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.*;
import java.util.Scanner;


public class Assign3Soln 
{

    // (provided)
    // precondition:  n >= 0
    // postcondition:  has returned the number of ways to park
    //  Civics, Explorers, Tanks in a row of n parking spaces, where 
    //  a tank takes up three space, an Explorer 2, and a Civic one,
    //  and no space can be left empty.  Two vehicles of one type
    //  are indistinguishable.  
    //
    //  You must make three recursive calls, one to count the
    //  number of arrangements ending with a Civic, one to count
    //  the number of arrangements ending with an Explorer, and one
    //  to count the number of arrangements ending in with a tank.
    public static long pentagonPark (int n)
    {
         if (n == 0) return 1;  
         else if (n == 1) return 1;  
         else if (n == 2) return 2;  
         else return pentagonPark(n-3)  // A Tank in last position
                   + pentagonPark(n-2)  // An Explorer in last position
                   + pentagonPark(n-1); // A Civic in last position
    }

    // fast version of pentagonPark.  It has the same preconditions
    //  as pentagonPark, plus an additional precondition
    //   that A.length >= n+1 and each element A[i] in A[1..n] is either
    //   initialized to 0 or to the answer to pentagonPark(n).
    //  An additional postcondition is that A[n] contains the value
    //   of the answer to pentagonPark(n), every element A[i] of A
    //   that has been changed has been changed to fibonacci(i)
    //
    // The speedup should use the technique of recording intermediate
    // results in an array, which we will illustrate in class on Fibonacci
    public static long pentagonPark (int n, long [] A) 
    {
        if (A[n] == 0)  // you haven't already solved this subproblem
        {
            if (n == 0) A[n] = 1;       // the empty parking job
            else if (n == 1) A[n] = 1;  // C
            else if (n == 2) A[n] = 2;  // CC, E
            else 
            {
               A[n] = pentagonPark(n-3,A)  // tank in last position
                    + pentagonPark(n-2,A)  // Excursion in last position
                    + pentagonPark(n-1,A); // Civic in last position
            }
        }
        return A[n];
    }

    // (provided)
    // preconditions:  n >= 0; start != destination; 1 <= start <= 3;
    //   1 <= destination <= 3
    // postconditions:  The sequence of Hanoi moves to move n disks from
    //   start to destination has been printed out
    public static void Hanoi(int n, int start, int dest)
    {
        if (n == 0) return;
        else
        {
            int spare = 6 - start - dest;  // the three peg numbers add up to 6
            Hanoi(n-1, start, spare);
            System.out.println("Move disk " + n + " from " + start
                             + " to " + dest);
            Hanoi(n-1, spare, dest);
        }
    }

    // (provided)
    // precondition:  n >= 0
    // postcondition:  The number of moves required in Towers of Hanoi to 
    //   move n disks from one peg to another has been returned
    public static int HanoiMoves(int n)
    {
        if (n == 0) return 0;
        else return 2 * HanoiMoves(n-1) + 1;
    }

    // precondition:  n >= 0; source is either 1 or 3; dest is either 1 or 3;
    //   source != dest
    // postcondition:  A sequence of moves in Towers of Saigon to move
    //   a stack of n disks has been printed out.  The moves should be
    //   printed one per line, in the following format
    //   
    //     Move disk i from j to k
    //
    //  where i denotes the disk number, counting from smallest to largest,
    //  and j and k are peg numbers.
    //----------------------------------------------------
    //
    // The rules of Towers of Saigon are the same as they are for
    //   Towers of Hanoi, except that there is an additional constraint:
    //   you can't move a disk directly between peg 1 and peg 3 without
    //   setting it down on peg 2.
    //
    // Notice that if you can get the top n-1 disks to dest, then you
    //   can move disk n from source to peg 2.  If you can then get the top 
    //   n-1 disks from dest back to source, you can move disk n from peg 2 
    //   to dest.  All that remains to complete the problem at this point is
    //   to move the top n-1 disks from source to dest.  We've expressed
    //   the entire operation in terms of two moves and three smaller instances
    //   of the original problem.
    public static void Saigon (int n, int source, int dest)
    {
        if (n == 0) return;
        else
        {
            Saigon(n-1, source, dest);
            System.out.println("Move disk " + n + " from " + source + " to 2.");
            Saigon(n-1, dest, source);
            System.out.println("Move disk " + n + " from 2 to " + dest);
            Saigon(n-1, source, dest);
        }
    }

    // precondition:  n >= 0
    // postcondition:  The number of moves required in Towers of Saigon
    //   to move n disks from 1 to 3 or 3 to 1 has been returned.
    public static int SaigonMoves(int n)
    {
        if (n == 0) return 0;
        else return 3 * SaigonMoves(n-1) + 2;
    }

    // precondition:  1 <= n <= A.length;  A[0..n-2] is in sorted order.
    //   (In other words, only the last element of A[0..n-1] can be out of 
    //   sorted order)
    // postcondition:  A[0..n-1] has been shuffled so that it is now in sorted
    //   order.
    //
    // Notice:  1.  If A[n-1] >= A[n-2], then the postcondition already applies.
    //          2.  If n == 1, then the postcondition already applies.
    //          3.  If A[n-2] > A[n-1], swapping their values doesn't
    //          quite meet the postcondition.  However, at this point,
    //          if you can get A[0..n-2] into sorted order, you'll meet
    //          the postcondition.  Not only that, but A[0..n-2] is a smaller
    //          instance of our problem, since only its last element is out
    //          of sorted order.
    public static void bubbleDown (int n, int [] A)
    {

       if (n == 1) return;
       else if (A[n-2] > A[n-1])
       {
           int temp = A[n-1];
           A[n-1] = A[n-2];
           A[n-2] = temp;     
           //
           // now A[0..n-2] meets the precondition for the following
           bubbleDown(n-1, A);
       }
    }

    // precondition:  1 <= n <= A.length
    // postcondition:  A[0..n-1] has been sorted.
    //
    // Notice that the precondition is much looser than it is for
    //  bubbleDown, which makes it more general and more useful.  
    //
    // Notice also:  If someone would sort A[0..n-2] for us, then A[0..n-1]
    //  would meet the precondition of bubbleDown, so we could use it
    //  to finish the job.  Sorting A[0..n-2] is a smaller instance
    //  of the problem we are now working on.
    public static void insertionSort (int n, int [] A)
    {
       if (n == 1) return;
       else
       {
           insertionSort (n-1, A);
           bubbleDown (n,A);
       }
    }

    // preconditions:  0 <= i <= j < k < A.length; A[i..j] is in sorted
    //   order and A[j+1..k] is in sorted order.
    // postcondition:  A[i..k] has been shuffled to be in sorted order.
    //
    // You must modify the algorithm of 'merge' from assignment 1.  Instead
    // of operating on two arrays A1 and A2, you are operating on two
    // sections of A, namely, A[i..j] and A[j+1..k].  Merge these into
    // a temporarily allocated array B of size k-i+1, and then copy
    // its contents back into A[i..k] to meet the postcondition.
    public static void merge(int [] A, int i, int j, int k)
    {
        int[] B = new int[k-i+1];

        int counterA1 = i;  
        int counterA2 = j+1;  
        int counterB = 0;  

        // collate the two sorted sections until one of the counters runs
        //  off the end of its sorted section ...
        while (counterA1 <= j && counterA2 <= k)
           if (A[counterA1] < A[counterA2])
               B[counterB++] = A[counterA1++];
           else
               B[counterB++] = A[counterA2++];

        // while there are still elements of the first section to copy ...
        while (counterA1 <= j)
            B[counterB++] = A[counterA1++];
       
        // while there are still elements of the second section to copy  ....
        // (There is a clever way to skip this step, if you also modify
        //  the next loop)
        while (counterA2 <= k)
            B[counterB++] = A[counterA2++];
        
        // copy everything back from B to A[i..k]
        counterB = 0;
        int counterA = i;
        while (counterA <= k)
            A[counterA++] = B[counterB++];
    }

    // precondition:  0 <= i <= k < A.length
    // postcondition:  A[i..k] has been sorted
    //
    // Notice that once again, a looser precondition means a more
    // more general and useful method.  
    //
    // We can't use 'merge' on it, since it A[i..k] doesn't necessarily
    // meet its preconditions.  However, if we let j = (i+k)/2 (integer
    // arithmetic), then somehow got A[i..j] and A[j+1..k] into sorted
    // order, we would now meet the precondition of merge(A,i,j,k).
    public static void Sort(int [] A, int i, int k)
    {
        if (i == k) return;
        else
        {
            int j = (i+k)/2;
            Sort(A, i, j);
            Sort(A, j+1, k);
            merge(A, i, j, k);
        }
    }

    /***********************************************************/
    /* Below here is infrastructure for the menu               */
    /***********************************************************/

    // Read a sequence of integers from a file into an array.
    // The first integer of the file tells the number n of integers in the
    // sequence.  The remaining n integers in the file are the sequence.
    // Each integer in the file is separated from the next by one
    // or more white-space characters (spaces or newlines).
    // The method returns an array that is allocated to have size n
    // and holds the n-integer sequence.  If there is an IO exception,
    // which can happen if the file doesn't exist or doesn't adhere
    // to the formatting requirements, the method prints an error message
    // and halts the program with status 1.
    public static int[] readIn(String fName) {
       int[] res = {};
       try {
           Scanner scan = new Scanner(new File(fName));
           int size;
           size = scan.nextInt();
           res = new int[size];
           // loop through numbers in input file and sum them
           for(int i=0; i<size; i++) {
               res[i] = scan.nextInt();
           }
       } catch (IOException E) {
           System.out.println("readIn: IOException!!");
           System.exit(1);
       }
       return res;
    }
	
	
    
    // Precondition:  0 < size <= A.length;
    // Postcondition:  A[0], A[1], ..., A[size-1] have been printed
    //   to one line of output, each followed by a space.  The line
    //   is followed by a newline.
    public static void printArr(int A[], int size)
    {
        for (int counter = 0; counter < size; counter++)
            System.out.print(A[counter] + " ");  

        System.out.println();
    }

    // Precondition:  0 <= from <= to < A.length
    // Postcondition:  A[from], A[from+1], ..., A[to] have been printed
    //   to one line of output, each followed by a space.  The line
    //   is followed by a newline.
    public static void printArrSection(int A[], int from, int to)
    {
        for (int counter = from; counter <= to; counter++)
            System.out.print(A[counter] + " ");  
        System.out.println();
    }
    
    // prints out the menu (provided)
    public static void printStrings(String[] Strings) 
    {
        for (int i = 0; i < Strings.length; i++) 
            System.out.println(Strings[i]);
    }


    public static void main(String[] args)
    {
        Scanner Input = new Scanner(System.in);
        int [] Array;
        int arrSize;
        System.out.println("The first element of the file should be the size n");
        System.out.println("The next n elements are the values that get filled");
        System.out.println("into the array\n\n");

        System.out.println("Name of file containing array:  ");
        String filename = Input.next();
        System.out.print ("\n" + filename + "\n\n\n");
        Array = readIn(filename); 
        arrSize = Array.length;
        System.out.println();
        printArr(Array, arrSize);
        System.out.println();

        String[] MenuChoices =
        {
           "0.  Exit",
           "1.  Read in a new Array (provided) ",
           "2.  Print contents of Array (provided)",
           "3.  Pentagon Park (provided)",
           "4.  Fast Pentagon Park",
           "5.  Towers of Hanoi (provided)",
           "6.  Compute just the number of moves for Towers of Hanoi (provided)",
           "7.  Towers of Saigon",
           "8.  Compute just the number of moves for Towers of Saigon",
           "9.  Bubble-down",
           "10. Recursive sort, using bubble-down for last step",
           "11. Merge",
           "12. Sort using a call to Merge for last step",
        };

        int choice = -1; // Records the option number the user selected
                         //   from the menu
        do
        {
             System.out.println("\n ---------------------------------------");
             System.out.println("                MENU");
             printStrings(MenuChoices);

             System.out.print("\n    Which? ");

             choice = Input.nextInt();
             System.out.println(choice);

            
             if (choice == 1)
             { 
                  System.out.println("Name of file for Array:  ");
                  filename = Input.next();
                  System.out.print ("\n" + filename + "\n\n\n");
                  Array = readIn(filename); 
                  arrSize = Array.length;
             }
             else if (choice == 2)  
                 printArr(Array, arrSize); 
             else if (choice == 3)
             {
                 System.out.print("Enter number of parking spaces:  ");
                 int n = Input.nextInt();
                 System.out.println("There are " + pentagonPark(n) + 
                                    " ways to park tanks, Explorers, Civics in "
                                    + n + " spaces.\n");
             }
             else if (choice == 4)
             {
                 System.out.print("Enter number of parking spaces:  ");
                 int n = Input.nextInt();
                 long [] A = new long [n+1];
                 System.out.println("There are " + pentagonPark(n,A) + 
                                    " ways to park tanks, Explorers, civis in "
                                    + n + " spaces.\n");
             }
             else if (choice == 5)  // Standard Hanoi
             {
                 System.out.print("Enter number of disks in pile:  ");
                 int n = Input.nextInt();
                 System.out.print("Enter start peg (1-3), destination peg (1-3):  ");
                 int start = Input.nextInt();
                 int dest = Input.nextInt();
                 Hanoi(n, start, dest);
             }
             else if (choice == 6)  // HanoiMoves
             {
                 System.out.print("Enter number of disks in pile:  ");
                 int n = Input.nextInt();
                 System.out.println("That will take "
                                  + HanoiMoves(n) + " moves ");
             }
             else if (choice == 7) // Saigon
             {
                 System.out.print("Enter number of disks in pile:  ");
                 int n = Input.nextInt();
                 System.out.print("Enter start peg (1 or 3), destination peg (1 or 3):  ");
                 int start = Input.nextInt();
                 int dest = Input.nextInt();
                 Saigon(n, start, dest);
             }
             else if (choice == 8)
             {
                 System.out.print("Enter number of disks in pile:  ");
                 int n = Input.nextInt();
                 System.out.println("That will take "
                                  + SaigonMoves(n) + " moves ");
             }
             else if (choice == 9)
             {
                 System.out.print(
                    " Enter a number of leading elements of Array that meet\n"
                  + " the precondition for bubbleDown:  ");
                 int n = Input.nextInt();
                 System.out.print ("Before the call:  ");
                 printArr(Array,n);
                 bubbleDown(n, Array);
                 System.out.print("After the call:  ");
                 printArr(Array,n);
             }
             else if (choice == 10)
             {
                 System.out.print ("Before the call:  ");
                 printArr(Array,arrSize);
                 insertionSort(arrSize, Array);
                 System.out.print("After the call:  ");
                 printArr(Array,arrSize);
             }
             else if (choice == 11)
             {
                 System.out.println (
                  "Enter indices i <= j < k delimiting sorted sections of A: ");
                 int i = Input.nextInt();
                 int j = Input.nextInt();
                 int k = Input.nextInt();
                 System.out.print ("Before the call:  ");
                 System.out.print("First section (should be sorted): ");
                 printArrSection(Array,i,j);
                 System.out.print("Second section (should be sorted): ");
                 printArrSection(Array,j+1,k);
                 merge(Array, i, j, k);
                 System.out.print("The two sections after the call:  ");
                 printArrSection(Array,i,k);
             }
             else if (choice == 12)
             {
                 System.out.println(
                    "Enter indices i, k delimiting section of Array to sort: ");
                 int i = Input.nextInt();
                 int k = Input.nextInt();
                 System.out.print("That section before sort: ");
                 printArrSection(Array, i, k);
                 Sort (Array, i, k);
                 System.out.print("That section after sort: ");
                 printArrSection(Array, i, k);
             }

        } while (choice != 0);
    }
}