/**
 * October 2017 Math Puzzler
 *   https://sites.monroecc.edu/mathpuzzler/2017/10/01/october-2017-puzzle/
 * 
 * You are equipped with a single 2, 5, 7, and 10 along with the ability to combine them using only addition,
 * subtraction, multiplication, division, and exponentiation.
 * 
 * Your goal is to create each of the integers from 29 to 45 as well as 78, 81, & 87.
 * 
 * You may use any number of parenthesis to control the order of operations and in each case, you
 * must use all four numbers exactly once.
 * 
 * For example: 22 = 5^2 - 10 + 7
 * 
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class Calculator2 {
   
   interface MathOp {
      float calc(float a, float b);
   }
   
   public static void main(String[] args) {
      
      Set<Float> answers = new HashSet<Float>();            //The equation values
      Set<Solutions> solutions = new HashSet<Solutions>();  //A set of solution equations
      
      //Generate a set containing: 29.0f -> 45.0f, and 78.0f, 81.0f, 87.0f
      for (int n=29; n<=45; n++) {
         answers.add((float)n);
      }
      answers.add(78f);
      answers.add(81f);
      answers.add(87f);
      
      //Generate an array of the math allowed operations
      MathOp cmds[] = { (a, b) -> a + b,
                    (a, b) -> a - b,  
                    (a, b) -> a * b, 
                    (a, b) -> a / b, 
                    (a, b) -> (float)Math.pow(a,  b)
                   };
   
      //Generate the list of available operands
      int[] numbers = {2, 5, 7, 10};
   
      //Generate a list of all the possible ways to use the operands
      HeapAlgo heapAlgo = new HeapAlgo();
      ArrayList<IntArray> perms = heapAlgo.heapPermutation(numbers,4,4);
      
      int count = 0;
      float result = 0f;
      
      for (IntArray ia : perms) {                                    //For each way of putting operands into the formula
         int[] nums = ia.getIntArray();
         
         //Now test all possible uses of operators for each way of using operands
         for (int k=0; k<5; k++) {
            for (int j=0; j<5; j++) {
               for (int i=0; i<5; i++ ) {
                  float resultab = cmds[i].calc(nums[0], nums[1]);   //Result of first two operands and first operation
                  float resultbc = cmds[j].calc(nums[1], nums[2]);   //Result of 2nd/3rd operands and 2nd operation
                  float resultcd = cmds[k].calc(nums[2], nums[3]);   //  ...
                  
                  //Test each operand/operator combination with all parentheses combinations.
                  // When the calculated value is found in the answer set a solution is found, 
                  // add it to the solutions "set" Because it is a set, only one solution 
                  // per calculated value is saved.
                  
                  //Result of A op B op C op D or (((A op B) op C) op D)
                  result = cmds[k].calc(cmds[j].calc(resultab, nums[2]), nums[3]);  //A*B*C*D
                  if (answers.contains(result)) {
                     solutions.add(new Solutions(result, i, j, k,nums[0],nums[1],nums[2],nums[3],"ABCD"));
                  }
                  
                  //Result of A op (B op C op D) or A op ((B op C) op D))
                  result = cmds[i].calc(nums[0], cmds[k].calc(resultbc, nums[3]));  //A*(B*C*D)
                  if (answers.contains(result)) {
                     solutions.add(new Solutions(result, i, j, k,nums[0],nums[1],nums[2],nums[3],"A(BCD)"));
                  }
                  
                  //...
                  result = cmds[j].calc(resultab, resultcd);   //(A*B)*(C*D) or A*B*(C*D)
                  if (answers.contains(result)) {
                     solutions.add(new Solutions(result, i, j, k,nums[0],nums[1],nums[2],nums[3],"(AB)(CD)"));
                  }
                  
                  result = cmds[k].calc(cmds[i].calc(nums[0], resultbc),nums[3]);   //A*(B*C)*D
                  if (answers.contains(result)) {
                     solutions.add(new Solutions(result, i, j, k,nums[0],nums[1],nums[2],nums[3],"A(BC)D"));
                  }
                  
                  result = cmds[i].calc(nums[0], cmds[j].calc(nums[1], resultcd));  //A*(B*(C*D))
                  if (answers.contains(result)) {
                     solutions.add(new Solutions(result, i, j, k,nums[0],nums[1],nums[2],nums[3],"A(B(CD))"));
                  }
                  
                  result = cmds[k].calc(cmds[i].calc(nums[0], resultbc),nums[3]);   //A*((B*C)*D)
                  if (answers.contains(result)) {
                     solutions.add(new Solutions(result, i, j, k,nums[0],nums[1],nums[2],nums[3],"A((BC)D"));
                  }
                  
                  count++;
               }
            }
         }
      }
      
      //Sort and print the list of solutions
      SortedSet<Solutions> sortedSolutions = new TreeSet<Solutions>(solutions);
      for (Object s : sortedSolutions) {
         System.out.println(s);
      }
      System.out.println(count);
   }
}