If you've ever played 24, this is kind of like that. I'm working on creating a program that given an array of numbers, it attempts to use arithmetic to evaluate it to a specific other number. It is quite complex and recursive as well. The method solve, which solves the problem, got called 197134524 times before the solution was found for this particular problem:

`{7,8,4,3}>156`

And in which the solution was:

`3*(7*8-4)`

The answer given to me by the program was:

`( 3 ) * ((( 7 ) * ( 8 )) - ( 4 ))`

If you got rid of the unnecessary parentheses (which the program adds in by default to make sure that the equation works), you will find that it is the correct solution. There are some bugs though, and this code only worked after nursing the program through it, since some part of it is still not working correctly. It has correctly solved problems on its own though. If you want to see the code:

import java.util.ArrayList; import java.util.Scanner; public class NumberSolver { static Scanner input = new Scanner(System.in); static int recursionDepth = 0; static boolean overrideDepth = false; static int[] array = {7,8,4,3}; static boolean[] used; static int maxNum; static int number; static boolean solve2r = false; public static int maxForArray() { int number1 = 1; for(int i = 0; i < array.length; i++) if(array[i] > number1 && !used[i]) number1 = array[i]; use(number1); int number2 = 1; for(int i = 0; i < array.length; i++) if(array[i] > number2 && !used[i]) number2 = array[i]; resetUsed(); return number1 * number2; } public static int[] factor(int num){ ArrayList<Integer> ini = new ArrayList<Integer>(); ini.add(1); for(int i = 2; i <= Math.sqrt(num); i++) if(num % i == 0) ini.add(i); int[] arr = new int[ini.size()*2]; for(int i = 0; i < ini.size(); i++) arr[i] = ini.get(i); for(int i = 0; i < ini.size(); i++) arr[arr.length - i -1] = num/arr[i]; return arr; } public static String solve(int complexity, int num){ recursionDepth++; int a = indexOf(unused(),num); if(a != -1) { if(!use(num)) return null; return " " + Integer.toString(num) + " "; } String factored = findFromMultiplication(complexity,num); if(factored != null) return factored; if(num == number) { resetUsed(); } String added = findFromAddition(complexity,num); if(added != null || solve2r) return added; if(num == number) { resetUsed(); } String divided = findFromDivision(complexity,num); if(divided != null) return divided; if(num == number) { resetUsed(); } return findFromSubtraction(complexity,num); } public static String solve2(int complexity, int num){ recursionDepth++; int a = indexOf(unused(),num); if(a != -1) { if(!use(num)) return null; return " " + Integer.toString(num) + " "; } String factored = findFromMultiplication(complexity,num); if(factored != null) return factored; if(num == number) { resetUsed(); } return findFromAddition(complexity,num); } public static String findFromMultiplication(int complexity, int num) { if(num == 1 || unused().length == 0) return null; int[] factors = factor(num); if(factors.length == 2) { int factor2i = indexOf(unused(),num); if(factor2i != -1) { if(!use(num)) return null; return " " + Integer.toString(num) + " "; } return null; } int[] globalUnused = unused(); String solved1; String solved2; for(int i = 1; i <= (factors.length -2)/2; i++) { if(num == 592 && factors[i] == 4) ifDebug(); solved1 = solve(complexity,factors[i]); if(solved1 != null) { solved2 = solve(complexity,factors[factors.length - 1 - i]); if(solved2 != null) return "(" + solved1 + ") * (" + solved2 + ")"; } setUnused(globalUnused); } return null; } public static void ifDebug() {} public static String findFromAddition(int complexity, int num) { if(num == 1 || unused().length == 0) return null; String solved1; String solved2; int[] globalUnused = unused(); for(int i = 1; i <= num/2; i++) { if(i == 12) ifDebug(); setUnused(globalUnused); solved1 = solve(complexity, i); if(solved1 != null) { solved2 = solve(complexity,num-i); if(solved2 != null) { return "(" + solved1 + ") + (" + solved2 + ")";} } } return null; } public static String findFromSubtraction(int complexity,int num) { solve2r = true; // if(true) return null; String solved1; String solved2; int[] globalUnused = unused(); if(num == 52) ifDebug(); for(int i = 1; i + num <=maxNum; i++) { if(i == 4) ifDebug(); solved1 = solve(complexity,i+num); if(solved1 != null) { solved2 = solve(complexity,i); if(solved2 != null) { solve2r = false; return "(" + solved1 + ") - (" + solved2 + ")"; } } setUnused(globalUnused); } solve2r = false; return null; } public static String findFromDivision(int complexity,int num) { if(true) return null; String solved1; String solved2; int[] globalUnused = unused(); for(int i = 1; i * num <=maxNum; i++) { solved1 = solve(complexity,i); if(solved1 != null) { solved2 = solve(complexity, num * i); if(solved2 != null) return "(" + solved2 + ") / (" + solved1 + ")"; } setUnused(globalUnused); } return null; } public static void dumpUnused() { for(int element : unused()) System.out.print(element + ","); System.out.println(); } public static void dumpArray(int [] arr) { for(int element : arr) System.out.print(element + ","); System.out.println(); } public static String findNextNum(String str, int index) { String fin = ""; boolean hasBeenFound = false; for(int i = index; i < str.length(); i++) { if("1234567890".indexOf(str.substring(i,i+1)) == -1 && hasBeenFound) return fin; if("1234567890".indexOf(str.substring(i,i+1)) != -1) { fin += str.substring(i,i+1); hasBeenFound = true; } } return fin; } public static void setUsedFromString(String str) { if(str == null) return; String next; for(int i = 0; i < str.length(); i++) { next = findNextNum(str,i); i += next.length(); if(next.length() != 0) { use(Integer.parseInt(next)); } } } public static void setUnused(int[] arr) { for(int i = 0; i < array.length; i++) used[i] = true; for(int element : arr) for(int i = 0; i < array.length; i++) if(array[i] == element && used[i]) { used[i] = false; break; } } public static void resetUsed() { for(int i = 0; i < used.length; i++) used[i] = false; } public static boolean use(int num) { if(num == 2) { ifDebug(); } for(int i = 0; i < array.length; i++) { if(array[i] == num && !used[i]) { used[i] = true; return true; } } return false; } public static int nextEmptyIndex(int[] arr) { for(int i = 0; i < arr.length; i++) if(arr[i] == 0) return i; return -1; } public static int indexOf(int[] arr,int a) { for(int i = 0; i < arr.length; i++) if(arr[i] == a) return i; return -1; } public static int indexOf(int[] arr,int a,int b) { for(int i = b; i < arr.length; i++) if(arr[i] == a) return i; return -1; } public static int[] unused() { int[] arr = new int[trues(used)]; for(int i = 0; i < array.length; i++) if(!used[i]) arr[nextEmptyIndex(arr)] = array[i]; return arr; } public static int trues(boolean [] arr) { int counter = 0; for(boolean element : arr) counter += parseBool(!element); return counter; } public static int parseBool(boolean a) { return a ? 1 : 0; } public static void main(String[] args) { System.out.println("Setting up..."); // System.out.println("Enter number of numbers: "); // array = new int[input.nextInt()]; used = new boolean[array.length]; // for(int i = 0; i < array.length; i++){ // System.out.println("Enter number " + i + ": "); // array[i] = input.nextInt(); // } // System.out.println("Enter number to solve for: "); // int num = input.nextInt(); // System.out.println("Minimum complexity? "); // int min = input.nextInt(); // int[] factors = factor(num); int min = 1; number = 156; maxNum = maxForArray(); String solved = solve(min, number); if(solved != null){ System.out.println("Solved!"); System.out.println(solved); System.out.println("Reached recursion depth of: " + recursionDepth); return; } System.out.println("Failed."); } }

There are several commented out lines, and other such apparently useless print-outs etc. which are for debugging purposes. I hope you guys can appreciate and at least understand the logic and structure of the code. I hope you guys like it!

If you want to see the structure of the way it solves the equation, this flowchart of how the number 156 is broken up into the necessary parts is shown below: