8
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ What are the restrictions (length of a digit string, target value)? \$\endgroup\$ – vnp May 10 '17 at 0:01
  • \$\begingroup\$ I updated the question to include the restrictions. Please see above \$\endgroup\$ – user1179317 May 10 '17 at 0:20
  • \$\begingroup\$ Are you sure that putting more digits togheter is allowed by the rules? Like 12 + 3 \$\endgroup\$ – Caridorc May 10 '17 at 17:59
  • 1
    \$\begingroup\$ @Caridorc Yes, "123" is also valid if the target was 123 \$\endgroup\$ – user1179317 May 10 '17 at 18:12
5
\$\begingroup\$
  • 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))
\$\endgroup\$
  • \$\begingroup\$ This answer is quite simple, yet the best answer i got. I was able to optimize my answer a bit more by eliminating multiple int() conversions and eliminating list() copy, but those only dropped it to a little below 2 seconds. This is definitely way faster. Thanks for the input. \$\endgroup\$ – user1179317 May 14 '17 at 17:35
  • \$\begingroup\$ Quick question, how does 'k' handle the order of evaluation, meaning if theres 1*5+2 that the 1*5 to be evaluated first. \$\endgroup\$ – user1179317 May 14 '17 at 21:38
  • \$\begingroup\$ @user1179317 When considering 1*, we pass 1 forward as k, and the next level of recursion performs the multiplication by k. With 1+ we can evaluate the left hand side without knowing the right hand side, so we can simply shift the target and evaluate the right hand side independently. \$\endgroup\$ – Janne Karila May 15 '17 at 5:57
  • \$\begingroup\$ Yea i figured it out after looking at it some more. Your ways were very smart in optimizing the algorithm. \$\endgroup\$ – user1179317 May 15 '17 at 14:33
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.