Return all valid expressions with specific target

Question

The problem is stated as: Given a string that contains only digits 0-9 and a target value, return all expressions that are created by adding some binary operators (+, -, or *) between the digits so they evaluate to the target value. In some cases there may not be any binary operators that will create valid expressions, in which case the function should return an empty array. The numbers in the new expressions should not contain leading zeros.

The function should return all valid expressions that evaluate to target, sorted lexicographically.

For example:

digits = "123" and target = 6, should return: ["1*2*3", "1+2+3"]

My current algorithm is below. I optimized it as much as I can. The question is base on code fights. My algo will generate all combinations of operands and operators accordingly. For the example above, it'll generate:

Operands:

[['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]

Operators:

{0: [()], 1: [('+',), ('-',), ('*',)], 2: [('+', '+'), ('+', '-'), ('+', '*'), ('-', '+'), ('-', '-'), ('-', '*'), ('*', '+'), ('*', '-'), ('*', '*')]}

It then combines all possible combinations of operands and operators and evaluate each.

For digits = "1234506789" and target = 6, it takes about 2.2 secs. It should be enough for code fights that has a limit of 4 sec, but I guess that also depends on the speed of the processor. But for some reason it still hits the time limit from the site. Thus Im trying to see how it can be optimized a bit more.

Restrictions are:

2 <= digits.length <= 10
-10^4 <= target <= 10^4

My code is below. I commented out some of the alternatives I used, which pretty much has the same speed though.

from itertools import combinations, permutations
import itertools
import time

def getExpression(digits, target):

    operation = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
    }

    seen = {}

    def calculate2(e,sign):

        e = list(e)
        sign = list(sign)

        operands = [int(e.pop())]
        operators = []

        for i in reversed(range(len(sign))):
            operator = sign[i]

            if operator == '*':
                operators.append(operator)
                operands.append(int(e[i]))
            elif operator == '+' or operator == '-':
                while operators and operators[-1] == '*':
                    compute(operands, operators)
                operators.append(operator)
                operands.append(int(e[i]))

        while operators:
            compute(operands, operators)

        return operands[-1]

    def compute(operands, operators):         ## PERFORMS MATHEMATICAL OP.
        left, right = operands.pop(), operands.pop()
        op = operators.pop()

        operands.append(operation[op](left,right))



        ## BELOW ALSO HAS SIMILAR SPEED
        # if op == '+':
        #     operands.append(left + right)
        # elif op == '-':
        #     operands.append(left - right)
        # elif op == '*':
        #     operands.append(left * right)




        ## USING A HASH TABLE IMPLEMENTATION.  BASICALLY DONT CALCULATE IF IT WAS CALCULATED BEFORE
        ## BUT WITH ALL THE OVERHEAD NECESSARY, TAKES MORE TIME AND SPACE
        # if op == '+':
        #     seenKey = str(left) + "+" + str(right)
        #     key = seen.get(seenKey)
        #     if key:
        #         operands.append(key)
        #     else:
        #         val = left + right
        #         operands.append(val)
        #         seen[seenKey] = val
        # elif op == '-':
        #     seenKey = str(left) + "-" + str(right)
        #     key = seen.get(seenKey)
        #     if key:
        #         operands.append(key)
        #     else:
        #         val = left - right
        #         operands.append(val)
        #         seen[seenKey] = val
        # elif op == '*':
        #     seenKey = str(left) + "*" + str(right)
        #     key = seen.get(seenKey)
        #     if key:
        #         operands.append(key)
        #     else:
        #         val = left * right
        #         operands.append(val)
        #         seen[seenKey] = val


    def isValid(e):              ## DIGITS WITH LEADING 0 IS NOT VALID
        valid = True
        for num in e:
            if num[0] == '0' and len(num) > 1:
                valid = False
                break

        return valid

    def getStringForm(e,sign):             ## RETURNS STRING FORMAT
        temp = ""
        for num, operator in zip(e, sign):
            temp += num
            temp += operator

        temp += e[-1]

        return temp

    def getSign_combination(length):       ## GET ALL COMBO OF +,-,*
        signCombo = {}
        for i in range(0, length):
            signCombo[i] = [c for c in itertools.product(('+', '-', '*'), repeat=i)]
        return signCombo

    def generate_combination(source, comb):     ## GET ALL COMBO OF DIGITS
        res = []
        for x, action in zip(source, comb + (0,)):
            res.append(x)
            if action == 0:
                yield "".join(res)
                res = []

        ## STRING OR LIST (ABOVE) SEEMS TO BE THE SAME EFFICIENCY FOR THIS EXAMPLE
        # res = ""
        # for x, action in zip(source, comb + (0,)):
        #     res += x
        #     if action == 0:
        #         yield res
        #         res = ""


    elementCombo = [list(generate_combination(digits, c)) for c in itertools.product((0, 1), repeat=len(digits) - 1)]

    signCombo = getSign_combination(len(digits))

    ## THIS IS USING LIST COMPREHENSION, SHOULD BE FASTER BUT SEEMS THE SAME (BELOW MAY EVEN BE FASTER)
    return sorted([ getStringForm(e, sign) for e in elementCombo if isValid(e) for i,sign in enumerate(signCombo[len(e)-1]) if calculate2(e,sign) == target ])


    ## BELOW ALSO HAS SIMILAR SPEED MAYBE EVEN A LITTLE FASTER THAN THE LIST COMPREHENSION ABOVE
    # result = []
    # for e in elementCombo:
    #     if isValid(e):
    #         signs = signCombo[len(e)-1]
    #         for i,sign in enumerate(signs):
    #             if calculate2(e, sign) == target:
    #                 result.append(getStringForm(e, sign))
    # return sorted(result)


digits = "1234506789"
target = 6
start = time.clock()
print("Answer:", getExpression(digits, target))
print(time.clock() - start)

Answer 1

• Separation of concerns is an important design goal, and you have aimed for that by separating the generation of expressions from their evaluation. However, this slows you down compared to a more direct approach that updates partial results while exploring the possibilities.
• Evaluating each expression separately does not allow you to exploit similarities between expressions.
• Sorting the results can be avoided by exploring the possibilities in lexicographic order to begin with.
• Timing is best handled by the timeit module. To focus on the performance of the algorithm itself, do not print while timing.

The problem lends itself to a concise recursive solution that runs in 0.22 s while your version takes 2.6 s on my computer:

def expressions(digits, target, k=1):
    """Generate all expressions that evaluate to target
    using given digits and operators *,+,-, while multiplying first term by k
    """
    for i in range(1, len(digits)):
        left = digits[:i]
        right = digits[i:]
        n = k * int(left)
        for e in expressions(right, target, n):
            yield left + '*' + e
        for e in expressions(right, target - n):
            yield left + '+' + e
        for e in expressions(right, target - n, -1):
            yield left + '-' + e
        if left == '0': # catch leading zero
            return
    if k * int(digits) == target:
        yield digits

if __name__ == '__main__':
    import timeit     

    digits = "1234506789"
    target = 6
    print(timeit.repeat(lambda : list(expressions(digits, target)), number=1))

Answer 2

The only (obvious) issue I found was that isValid can be simplified:

def isValid(e):
    for num in e:
        if num[0] == '0' and len(num) > 1:
            return False
    return True

This way, you don't need a variable valid to store the boolean value. That could improve the performance, but if it does, it's probably a very low improvement. I just want to mention it. Maybe there are similar issues in your code which I didn't see.