How to optimize finding missing arithmetic operations in expression?

Question

I was given the following task:

Richard likes to ask his classmates questions like the following:

4 x 4 x 3 = 13

In order to solve this task, his classmates have to fill in the missing arithmetic operators (+, -, *, /) that the created equation is true. For this example the correct solution would be 4 * 4 - 3. Write a piece of code that creates similar questions to the one above. It should comply the following rules:

1. The riddles should only have one solution (e.g. not 3 x 4 x 3 = 15, which has two solutions)
2. The operands are numbers between 1-9
3. The solution is a positive integer
4. Point before dashes is taken into account (e.g. 1 + 3 * 4 = 13) > 5) Every interim result is an integer (e.g. not 3 / 2 * 4 = 6)

Create riddles up to 15 arithmetic operands, which follow these rules.

My progress:

import random
import time
import sys


add = lambda a, b: a + b
sub = lambda a, b: a - b
mul = lambda a, b: a * b
div = lambda a, b: a / b if a % b == 0 else 0 / 0

operations = [(add, '+'),
              (sub, '-'),
              (mul, '*'),
              (div, '/')]

operations_mul = [(mul, '*'),
                  (add, '+'),
                  (sub, '-'),
                  (div, '/')]

res = []


def ReprStack(stack):
    reps = [str(item) if type(item) is int else item[1] for item in stack]
    return ''.join(reps)


def Solve(target, numbers):
    counter = 0

    def Recurse(stack, nums):
        global res
        nonlocal counter
        valid = True
        end = False
        for n in range(len(nums)):
            stack.append(nums[n])
            remaining = nums[:n] + nums[n + 1:]
            pos = [position for position, char in enumerate(stack) if char == operations[3]]
            for j in pos:
                if stack[j - 1] % stack[j + 1] != 0:
                    valid = False

            if valid:
                if len(remaining) == 0:
                    # Überprüfung, ob Stack == target
                    solution_string = str(ReprStack(stack))
                    if eval(solution_string) == target:
                        if not check_float_division(solution_string)[0]:
                            counter += 1
                            res.append(solution_string)
                            if counter > 1:
                                res = []
                                values(number_ops)
                                target_new, numbers_list_new = values(number_ops)
                                Solve(target_new, numbers_list_new)
                else:
                    for op in operations_mul:
                        stack.append(op)
                        stack = Recurse(stack, remaining)
                        stack = stack[:-1]
            else:
                if len(pos) * 2 + 1 == len(stack):
                    end = True
                if counter == 1 and end:
                    print(print_solution(target))
                    sys.exit()
            stack = stack[:-1]
            return stack

    Recurse([], numbers)


def simplify_multiplication(solution_string):
    for i in range(len(solution_string)):
        pos_mul = [position for position, char in enumerate(solution_string) if char == '*']
        if solution_string[i] == '*' and len(pos_mul) > 0:
            ersatz = int(solution_string[i - 1]) * int(solution_string[i + 1])
            solution_string_new = solution_string[:i - 1] + solution_string[i + 1:]
            solution_string_new_list = list(solution_string_new)
            solution_string_new_list[i - 1] = str(ersatz)
            solution_string = ''.join(str(x) for x in solution_string_new_list)
        else:
            return solution_string

    return solution_string


def check_float_division(solution_string):
    pos_div = []
    solution_string = simplify_multiplication(solution_string)
    if len(solution_string) > 0:
        for i in range(len(solution_string)):
            pos_div = [position for position, char in enumerate(solution_string) if char == '/']
            if len(pos_div) == 0:
                return False, pos_div
            for j in pos_div:
                if int(solution_string[j - 1]) % int(solution_string[j + 1]) != 0:
                    # Float division
                    return True, pos_div
            else:
                # No float division
                return False, pos_div


def new_equation(number_ops):
    equation = []
    operators = ['+', '-', '*', '/']
    ops = ""
    if number_ops > 1:
        for i in range(number_ops):
            ops = ''.join(random.choices(operators, weights=(4, 4, 4, 4), k=1))
            const = random.randint(1, 9)
            equation.append(const)
            equation.append(ops)
        del equation[-1]
        pos = check_float_division(equation)[1]
        if check_float_division(equation):
            if len(pos) == 0:
                return equation
            for i in pos:
                equation[i] = ops
        else:
            '''for i in pos:
                if equation[i+1] < equation[i-1]:
                    while equation[i-1] % equation[i+1] != 0:
                        equation[i+1] += 1'''
            new_equation(number_ops)
    else:
        print("No solution with only one operand")
        sys.exit()
    return equation


def values(number_ops):
    target = 0
    equation = ''
    while target < 1:
        equation = ''.join(str(e) for e in new_equation(number_ops))
        target = eval(equation)
    numbers_list = list(
        map(int, equation.replace('+', ' ').replace('-', ' ').replace('*', ' ').replace('/', ' ').split()))
    return target, numbers_list


def print_solution(target):
    equation_encrypted_sol = ''.join(res).replace('+', '○').replace('-', '○').replace('*', '○').replace('/', '○')
    print("Try to find the correct operators " + str(equation_encrypted_sol) + " die Zahl " + str(
        target))
    end_time = time.time()
    print("Duration: ", end_time - start_time)
    input(
        "Press random button and after that "ENTER" in order to generate result")
    print(''.join(res))


if __name__ == '__main__':
    number_ops = int(input("Number of arithmetic operators: "))
    # number_ops = 10
    target, numbers_list = values(number_ops)
    # target = 590
    # numbers_list = [9, 3, 5, 3, 5, 2, 6, 3, 4, 7]
    start_time = time.time()
    Solve(target, numbers_list)

Solve(target, numbers) uses brute-force. It receives an equation and corresponding result as input, which was generated in new_equation(number_ops).

Solve(target, numbers) finds the solution using a stack. It takes about two hours for a task with 15 operators. How to make it faster?

Answer 1

This is mostly brute force but it only takes a few seconds for a 15 operation formula.

In order to check the result, I first made a solve function (recursive iterator) that will produce the solutions:

def multiplyDivide(numbers):
    if len(numbers) == 1:     # only one number, output it directly
        yield numbers[0],numbers
        return
    product,n,*numbers = numbers
    if product % n == 0: # can use division.
        for value,ops in multiplyDivide([product//n]+numbers):
            yield value, [product,"/",n] + ops[1:]
    for value,ops in multiplyDivide([product*n]+numbers):
        yield value, [product,"*",n] + ops[1:]    

def solve(target,numbers,canGroup=True): 
    *others,last = numbers
    if not others:             # only one number
        if last == target:     # output it if it matches target
            yield [last]
        return
    yield from ( sol + ["+",last] for sol in solve(target-last,others)) # additions
    yield from ( sol + ["-",last] for sol in solve(target+last,others)) # subtractions
    if not canGroup: return
    for size in range(2,len(numbers)+1):
        for value,ops in multiplyDivide(numbers[-size:]): # multiplicative groups
            for sol in solve(target,numbers[:-size]+[value],canGroup=False):
                yield sol[:-1] + ops  # combined multipicative with rest

The solve function recurses through the numbers building an addition or subtraction with the last number and recursing to solve a smaller problem with the adjusted target and one less number.

In addition to the additions and subtraction, the solve function groups the numbers (from the end) into consecutive multiplications/divisions and processes them (recursing into solve) using the resulting value that will have calculation precedence over additions/subtractions.

The multiplyDivide function (also a recursive generator) combines the group of numbers it is given with multiplications and divisions performed from left to right. Divisions are only added when the current product divided by the additional number produces an integer intermediate result.

Using the solve iterator, we can find a first solution and know if there are more by iterating one additional time:

def findOper(S):
    expression,target = S.split("=")
    target   = int(target.strip())
    numbers  = [ int(n.strip()) for n in expression.split("x") ]
    iSolve   = solve(target,numbers)
    solution = next(iSolve,["no solution"])
    more     = " and more" * bool(next(iSolve,False))
    return " ".join(map(str,solution+ ["=",target])) + more

Output:

print(findOper("10 x 5 = 2"))
# 10 / 5 = 2

print(findOper("10 x 5 x 3 = 6"))
# 10 / 5 * 3 = 6

print(findOper("4 x 4 x 3 = 13"))
# 4 * 4 - 3 = 13

print(findOper("1 x 3 x 4 = 13"))
# 1 + 3 * 4 = 13

print(findOper("3 x 3 x 4 x 4 = 25"))
# 3 * 3 + 4 * 4 = 25

print(findOper("2 x 6 x 2 x 4 x 4 = 40"))
# 2 * 6 * 2 + 4 * 4 = 40 and more

print(findOper("7 x 6 x 2 x 4 = 10"))
# 7 + 6 * 2 / 4 = 10

print(findOper("2 x 2 x 3 x 4 x 5 x 6 x 3 = 129"))
# 2 * 2 * 3 + 4 * 5 * 6 - 3 = 129

print(findOper("1 x 2 x 3 x 4 x 5 x 6 = 44"))
# 1 * 2 + 3 * 4 + 5 * 6 = 44

print(findOper("1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 8 x 7 x 6 x 5 x 4 x 1= 1001"))
# 1 - 2 - 3 + 4 * 5 * 6 * 7 / 8 * 9 + 8 * 7 - 6 + 5 + 4 + 1 = 1001 and more

print(findOper("1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 8 x 7 x 6 x 5 x 4 x 1= 90101"))
# no solution = 90101  (15 seconds, worst case is not finding any solution)

In order to create a single solution riddle, the solve function can be converted to a result generator (genResult) that will produce all possible computation results. This will allow us to find a result that only has one combination of operations for a given list of random numbers. Given that the multiplication of all numbers is very likely to be a unique result, this will converge rapidly without having to go through too many random lists:

import random

def genResult(numbers,canGroup=True):
    *others,last = numbers
    if not others:
        yield last
        return    
    for result in genResult(others):
        yield result - last
        yield result + last
    if not canGroup: return
    for size in range(2,len(numbers)+1):
        for value,_ in multiplyDivide(numbers[-size:]): 
            yield from genResult(numbers[:-size]+[value],canGroup=False)

def makeRiddle(size=5):
    singleSol = []
    while not singleSol:
        counts  = dict()
        numbers = [random.randint(1,9) for _ in range(size)]
        for final in genResult(numbers):
            if final < 0 : continue
            counts[final] = counts.get(final,0) + 1
        singleSol = [n for n,c in counts.items() if c==1]        
    return " x ".join(map(str,numbers)) + " = " + str(random.choice(singleSol))

The reason we have to loop for singleSol (single solution results) is that there are some cases where even the product of all numbers is not a unique solution. For example: 1 x 2 x 3 = 6 could be the product 1 * 2 * 3 = 6 but could also be the sum 1 + 2 + 3 = 6. There aren't too many of those cases but it's still a possibility, hence the loop. In a test generating 1000 riddles with 5 operators, this occurred 4 times (e.g. 4 x 1 x 1 x 4 x 2 has no unique solution). As you increase the size of the riddle, the occurrence of these no-unique-solution patterns becomes more frequent (e.g. 6 times generating 20 riddles with 15 operators).

output:

S = makeRiddle(15)  # 7 seconds

print(S)

# 1 x 5 x 2 x 5 x 8 x 2 x 3 x 4 x 1 x 2 x 8 x 9 x 7 x 3 x 2 = 9715

print(findOper(S)) # confirms that there is only one solution

# 1 * 5 * 2 * 5 * 8 * 2 * 3 * 4 - 1 + 2 + 8 * 9 + 7 * 3 * 2 = 9715