import java.util.Scanner;

/**
 * A program to print out the skeleton of a proof-by-induction.
 *
 * @author Mark Young (A00000000)
 */
public class ProofByInduction {

    public static final Scanner KBD = new Scanner(System.in);
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        printIntroduction();
        
        // choose kind of induction (linear/binary)
        System.out.print("Does your recurrence relation use subtraction "
                + "or division? ");
        String choice = KBD.nextLine().toLowerCase();
        if ("subtraction".startsWith(choice)) {
            doLinear();
        } else if ("division".startsWith(choice)) {
            doBinary();
        } else {
            System.out.println("Sorry, I didn't understand that!");
        }
    }
    
    /**
     * Get recurrence and formula, and show skeleton of proof of W(N) in terms
     * of N - 1.
     */
    private static void doLinear() {
        System.out.print("What is your recurrence relation: W(N) = ");
        String recurrence = KBD.nextLine().replaceAll("N-1", "N - 1");
        System.out.print("What is your formula for work? W(N) = ");
        String formula = KBD.nextLine();
        doInduction("N - 1", recurrence, formula);
    }
    
    /**
     * Get recurrence and formula, and show skeleton of proof of W(N) in terms
     * of N/2.
     */
    private static void doBinary() {
        System.out.print("What is your recurrence relation: W(N) = ");
        String recurrence = KBD.nextLine().replaceAll("N / 2", "N/2");
        System.out.print("What is your formula for work? W(N) = ");
        String formula = KBD.nextLine();
        doInduction("N/2", recurrence, formula);
    }
    
    /**
     * Print the skeleton of a proof by induction.
     * 
     * @param smaller the value less than N that we're working in terms of
     * @param recurrence the rhs of the recurrence relation
     * @param formula the rhs of the formula for work
     */
    private static void doInduction(String smaller, 
            String recurrence, String formula) {
        // create versions with W(N) = at start
        String recurrenceEquation = "W(N) = " + recurrence;
        String formulaEquation = "W(N) = " + formula;
        
        // separate from input
        System.out.println("\n\n\n----------------------------------------\n");
        
        // print what's to be proved
        System.out.println("Proof by Induction");
        System.out.println("Given that " + recurrenceEquation + ",");
        System.out.println("prove that " + formulaEquation + ".");
        System.out.println();
        
        // make inductive assumption
        System.out.println("Let's assume that " 
                + formulaEquation.replace("N", "n")
                + " is true for all n < N.");
        
        // note that smaller is smaller
        System.out.println("Well, " + smaller + " < N,");
        String formulaNMinus1 = formula.replace("N", "(" + smaller + ")");
        System.out.println("so W(" + smaller + ") = " 
                + formulaNMinus1 + ".");
        
        // substitute into recurrence equation
        System.out.println("But " + recurrenceEquation + ",");
        String expanded = recurrence.replace("W(" + smaller + ")", 
                "(" + formulaNMinus1 + ")");
        System.out.println("so W(N) = " + expanded + ".");
        
        // do some math (need human input here)
        System.out.println("... (expand and simplify) ...");
        System.out.println("... (may take multiple lines) ...");
        
        // state conclusion
        System.out.println("and thus " + formulaEquation + " for all N.");
        System.out.println("Q.E.D.");
    }

    /**
     * Print a description and instructions for this program.
     */
    private static void printIntroduction() {
        System.out.println("This program will print out the shell of a proof "
                + "by induction.\n\n"
                + "You need to provide the recurrence relation "
                + "and the supposed equation of work.\n\n"
                + "The recurrence relation needs to use subtraction "
                + "(W(N) = ... W(N - 1) ...)\n"
                + "or division (W(N) = ... W(N/2) ...).\n\n"
                + "This is a very simple program, so it can't handle anything "
                + "more complicated than that!\n\n");
    }

}
