Generate equation with the result value closest to the requested one, have speed problems

Question

I am writing some quiz game and need computer to solve 1 game in the quiz if players fail to solve it.

Given data :

1. List of 6 numbers to use, for example 4, 8, 6, 2, 15, 50.
2. Targeted value, where 0 < value < 1000, for example 590.
3. Available operations are division, addition, multiplication and division.
4. Parentheses can be used.

Generate mathematical expression which evaluation is equal, or as close as possible, to the target value. For example for numbers given above, expression could be : (6 + 4) * 50 + 15 * (8 - 2) = 590

My algorithm is as follows :

1. Generate all permutations of all the subsets of the given numbers from (1) above
2. For each permutation generate all parenthesis and operator combinations
3. Track the closest value as algorithm runs

I can not think of any smart optimization to the brute-force algorithm above, which will speed it up by the order of magnitude. Also I must optimize for the worst case, because many quiz games will be run simultaneously on the server.

Code written today to solve this problem is (relevant stuff extracted from the project) :

from operator import add, sub, mul, div
import itertools


ops = ['+', '-', '/', '*']
op_map = {'+': add, '-': sub, '/': div, '*': mul}

# iterate over 1 permutation and generates parentheses and operator combinations
def iter_combinations(seq):
    if len(seq) == 1:
        yield seq[0], str(seq[0])
    else:
        for i in range(len(seq)):
            left, right = seq[:i], seq[i:]  # split input list at i`th place
            # generate cartesian product
            for l, l_str in iter_combinations(left):
                for r, r_str in iter_combinations(right):
                    for op in ops:
                        if op_map[op] is div and r == 0:  # cant divide by zero
                            continue
                        else:
                            yield op_map[op](float(l), r), \
                                  ('(' + l_str + op + r_str + ')')

numbers = [4, 8, 6, 2, 15, 50]
target = best_value = 590
best_item = None

for i in range(len(numbers)):
    for current in itertools.permutations(numbers, i+1): # generate perms
        for value, item in iter_combinations(list(current)):
            if value < 0:
                continue

            if abs(target - value) < best_value:
                best_value = abs(target - value)
                best_item = item

print best_item

It prints : ((((4*6)+50)*8)-2). Tested it a little with different values and it seems to work correctly. Also I have a function to remove unnecessary parenthesis but it is not relevant to the question so it is not posted.

Problem is that this runs very slowly because of all this permutations, combinations and evaluations. On my mac book air it runs for a few minutes for 1 example. I would like to make it run in a few seconds tops on the same machine, because many quiz game instances will be run at the same time on the server. So the questions are :

1. Can I speed up current algorithm somehow (by orders of magnitude)?
2. Am I missing on some other algorithm for this problem which would run much faster?

Answer 1

You can build all the possible expression trees with the given numbers and evalate them. You don't need to keep them all in memory, just print them when the target number is found:

First we need a class to hold the expression. It is better to design it to be immutable, so its value can be precomputed. Something like this:

class Expr:
    '''An Expr can be built with two different calls:
           -Expr(number) to build a literal expression
           -Expr(a, op, b) to build a complex expression. 
            There a and b will be of type Expr,
            and op will be one of ('+','-', '*', '/').
    '''
    def __init__(self, *args):
        if len(args) == 1:
            self.left = self.right = self.op = None
            self.value = args[0]
        else:
            self.left = args[0]
            self.right = args[2]
            self.op = args[1]
            if self.op == '+':
                self.value = self.left.value + self.right.value
            elif self.op == '-':
                self.value = self.left.value - self.right.value
            elif self.op == '*':
                self.value = self.left.value * self.right.value
            elif self.op == '/':
                self.value = self.left.value // self.right.value

    def __str__(self):
        '''It can be done smarter not to print redundant parentheses,
           but that is out of the scope of this problem.
        '''
        if self.op:
            return "({0}{1}{2})".format(self.left, self.op, self.right)
        else:
            return "{0}".format(self.value)

Now we can write a recursive function that builds all the possible expression trees with a given set of expressions, and prints the ones that equals our target value. We will use the itertools module, that's always fun.

We can use itertools.combinations() or itertools.permutations(), the difference is in the order. Some of our operations are commutative and some are not, so we can use permutations() and assume we will get many very simmilar solutions. Or we can use combinations() and manually reorder the values when the operation is not commutative.

import itertools
OPS = ('+', '-', '*', '/')
def SearchTrees(current, target):
    ''' current is the current set of expressions.
        target is the target number.
    '''
    for a,b in itertools.combinations(current, 2):
        current.remove(a)
        current.remove(b)
        for o in OPS:
            # This checks whether this operation is commutative
            if o == '-' or o == '/':
                conmut = ((a,b), (b,a))
            else:
                conmut = ((a,b),)

            for aa, bb in conmut:
                # You do not specify what to do with the division.
                # I'm assuming that only integer divisions are allowed.
                if o == '/' and (bb.value == 0 or aa.value % bb.value != 0):
                    continue
                e = Expr(aa, o, bb)
                # If a solution is found, print it
                if e.value == target:
                    print(e.value, '=', e)
                current.add(e)
                # Recursive call!
                SearchTrees(current, target)
                # Do not forget to leave the set as it were before
                current.remove(e)
        # Ditto
        current.add(b)
        current.add(a)

And then the main call:

NUMBERS = [4, 8, 6, 2, 15, 50]
TARGET = 590

initial = set(map(Expr, NUMBERS))
SearchTrees(initial, TARGET)

And done! With these data I'm getting 719 different solutions in just over 21 seconds! Of course many of them are trivial variations of the same expression.