24 Game/Countdown/Number Game solver, but without parentheses in the answer

Question

I've been browsing the internet all day for an existing solution to creating an equation out of a list of numbers and operators for a specified target number.

I came across a lot of 24 Game solvers, Countdown solvers and alike, but they are all build around the concept of allowing parentheses in the answers.

For example, for a target 42, using the number 1 2 3 4 5 6, a solution could be:

6 * 5 = 30
4 * 3 = 12
30 + 12 = 42

Note how the algorithm remembers the outcome of a sub-equation and later re-uses it to form the solution (in this case 30 and 12), essentially using parentheses to form the solution (6 * 5) + (4 * 3) = 42.

Whereas I'd like a solution WITHOUT the use of parentheses, which is solved from left to right, for example 6 - 1 + 5 * 4 + 2 = 42, if I'd write it out, it would be:

6 - 1 = 5
5 + 5 = 10
10 * 4 = 40
40 + 2 = 42

I have a list of about 55 numbers (random numbers ranging from 2 to 12), 9 operators (2 of each basic operator + 1 random operator) and a target value (a random number between 0 and 1000). I need an algorithm to check whether or not my target value is solvable (and optionally, if it isn't, how close we can get to the actual value). Each number and operator can only be used once, which means there will be a maximum of 10 numbers you can use to get to the target value.

I found a brute-force algorithm which can be easily adjusted to do what I want (How to design an algorithm to calculate countdown style maths number puzzle), and that works, but I was hoping to find something which generates more sophisticated "solutions", like on this page: http://incoherency.co.uk/countdown/

Answer 1

I wrote the solver you mentioned at the end of your post, and I apologise in advance that the code isn't very readable.

At its heart the code for any solver to this sort of problem is simply a depth-first search, which you imply you already have working.

Note that if you go with your "solution WITHOUT the use of parentheses, which is solved from left to right" then there are input sets which are not solvable. For example, 11,11,11,11,11,11 with a target of 144. The solution is ((11/11)+11)*((11/11)+11). My solver makes this easier for humans to understand by breaking the parentheses up into different lines, but it is still effectively using parentheses rather than evaluating from left to right.

The way to "use parentheses" is to apply an operation to your inputs and put the result back in the input bag, rather than to apply an operation to one of the inputs and an accumulator. For example, if your input bag is 1,2,3,4,5,6 and you decide to multiply 3 and 4, the bag becomes 1,2,12,5,6. In this way, when you recurse, that step can use the result of the previous step. Preparing this for output is just a case of storing the history of operations along with each number in the bag.

I imagine what you mean about more "sophisticated" solutions is just the simplicity heuristic used in my javascript solver. The solver works by doing a depth-first search of the entire search space, and then choosing the solution that is "best" rather than just the one that uses the fewest steps.

A solution is considered "better" than a previous solution (i.e. replaces it as the "answer" solution) if it is closer to the target (note that any state in the solver is a candidate solution, it's just that most are further away from the target than the previous best candidate solution), or if it is equally distant from the target and has a lower heuristic score.

The heuristic score is the sum of the "intermediate values" (i.e. the values on the right-hand-side of the "=" signs), with trailing 0's removed. For example, if the intermediate values are 1, 4, 10, 150, the heuristic score is 1+4+1+15: the 10 and the 150 only count for 1 and 15 because they end in zeroes. This is done because humans find it easier to deal with numbers that are divisible by 10, and so the solution appears "simpler".

The other part that could be considered "sophisticated" is the way that some lines are joined together. This simply joins the result of "5 + 3 = 8" and "8 + 2 = 10" in to "5 + 3 + 2 = 10". The code to do this is absolutely horrible, but in case you're interested it's all in the Javascript at https://github.com/jes/cntdn/blob/master/js/cntdn.js - the gist is that after finding the solution which is stored in array form (with information about how each number was made) a bunch of post-processing happens. Roughly:

• convert the "solution list" generated from the DFS to a (rudimentary, nested-array-based) expression tree - this is to cope with the multi-argument case (i.e. "5 + 3 + 2" is not 2 addition operations, it's just one addition that has 3 arguments)
• convert the expression tree to an array of steps, including sorting the arguments so that they're presented more consistently
• convert the array of steps into a string representation for display to the user, including an explanation of how distant from the target number the result is, if it's not equal

Apologies for the length of that. Hopefully some of it is of use.

James

EDIT: If you're interested in Countdown solvers in general, you may want to take a look at my letters solver as it is far more elegant than the numbers one. It's the top two functions at https://github.com/jes/cntdn/blob/master/js/cntdn.js - to use call solve_letters() with a string of letters and a function to get called for every matching word. This solver works by traversing a trie representing the dictionary (generated by https://github.com/jes/cntdn/blob/master/js/mk-js-dict), and calling the callback at every end node.

Answer 2

I use the recursive in java to do the array combination. The main idea is just using DFS to get the array combination and operation combination.

I use a boolean array to store the visited position, which can avoid the same element to be used again. The temp StringBuilder is used to store current equation, if the corresponding result is equal to target, i will put the equation into result. Do not forget to return temp and visited array to original state when you select next array element.

This algorithm will produce some duplicate answer, so it need to be optimized later.

public static void main(String[] args) {
    List<StringBuilder> res = new ArrayList<StringBuilder>();
    int[] arr = {1,2,3,4,5,6};
    int target = 42;
    for(int i = 0; i < arr.length; i ++){
        boolean[] visited = new boolean[arr.length];
        visited[i] = true;
        StringBuilder sb = new StringBuilder();
        sb.append(arr[i]);
        findMatch(res, sb, arr, visited, arr[i], "+-*/", target);
    }

    for(StringBuilder sb : res){
        System.out.println(sb.toString());
    }
}

public static void findMatch(List<StringBuilder> res, StringBuilder temp, int[] nums, boolean[] visited, int current, String operations, int target){
    if(current == target){
        res.add(new StringBuilder(temp));
    }

    for(int i = 0; i < nums.length; i ++){
        if(visited[i]) continue;
        for(char c : operations.toCharArray()){
            visited[i] = true;
            temp.append(c).append(nums[i]);
            if(c == '+'){
                findMatch(res, temp, nums, visited, current + nums[i], operations, target);
            }else if(c == '-'){
                findMatch(res, temp, nums, visited, current - nums[i], operations, target);
            }else if(c == '*'){
                findMatch(res, temp, nums, visited, current * nums[i], operations, target);
            }else if(c == '/'){
                findMatch(res, temp, nums, visited, current / nums[i], operations, target);
            }
            temp.delete(temp.length() - 2, temp.length());
            visited[i] = false;
        }
    }
}