Recursive function call in Python

user_2390654 0
Viewed 102

I am a beginner in Python and want to solve the following problem: Given a list of n integer numbers and an integer result the correct operators (+, -, *, /) shall be found that solve a corresponding simple math equation.

Example:
For numbers = [2, 3, 4, 1] and result=13 the following solution should be found:
2 + 3 * 4 - 1 = 13.

I wrote the following code which finds a solution for n=4 by doing a brute force approach with 3 nested for loops in which the operators are alternated. I struggle though, when I try to write an algorithm where n is arbitrary. Can this be solved with a recursive function call and if so how?

numbers = [2, 3, 4, 1]
result = 13
op = ['+','-','*', '/']

Found=0
for i in op:
    for j in op:
        for k in op:
            #Build string for left side of the equation: e.g. '2 + 3 + 4 + 1'
            exp = str(numbers[0]) + i + str(numbers[1]) + j + str(numbers[2]) + k + str(numbers[3])
            if eval(exp) == result:
                Found += 1
                if Found == 1:
                    print('Found Solution(s):')
                print(f'{numbers[0]} {i} {numbers[1]} {j} {numbers[2]} {k} {numbers[3]} = {result}')

if Found == 0:
    print('No solution found!')
nested-loops recursion python
1 Answers

Not a recursive solution, not any efficient than yours, but this deals with any number of operations.

itertools.product is used to get what you want, if I can come up with an efficient recursive solution I will edit this.

from itertools import product

def check_result(numbers,result):
    op = ['+','-','*', '/']
    for i in product(op,repeat=len(numbers)-1):
        t=[None]*(len(numbers)+len(i))
        t[::2],t[1::2]=numbers,i
        t=[str(i) for i in t]
        expr=''.join(t)
        if eval(expr)==result:
            return 'Found'
    return 'Not Found'

print(check_result([2, 3, 4, 1],13)) # Found
print(check_result([2, 3, 4, 1,2],14)) # Found
print(check_result([2, 3, 4, 1,2,3,3,1,2],242)) # Not Found
user_125029590
Related