python - Check result using 4 operations based with Python

Question

I'm struggling to make a Python program that can solve riddles such as:

get 23 using [1,2,3,4] and the 4 basic operations however you'd like.

I expect the program to output something such as # 23 reached by 4*(2*3)-1

So far I've come up with the following approach as reduce input list by 1 item by checking every possible 2-combo that can be picked and every possible result you can get to.
With [1,2,3,4] you can pick: [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]

With x and y you can get to: (x+y),(x-y),(y-x),(x*y),(x/y),(y/x) Then I'd store the operation computed so far in a variable, and run the 'reducing' function again onto every result it has returned, until the arrays are just 2 items long: then I can just run the x,y -> possible outcomes function.

My problem is this "recursive" approach isn't working at all, because my function ends as soon as I return an array. If I input [1,2,3,4] I'd get

[(1+2),3,4] -> [3,3,4]
[(3+3),4] -> [6,4]
# [10,2,-2,24,1.5,0.6666666666666666]

My code so far:

from collections import Counter

def genOutputs(x,y,op=None):
    results = []
    if op == None:
        op = str(y)
    else:
        op = "("+str(op)+")"
    ops = ['+','-','*','/','rev/','rev-']
    z = 0
    #will do every operation to x and y now.
    #op stores the last computated bit (of other functions)
    while z < len(ops):
        if z == 4:
            try:
                results.append(eval(str(y) + "/" + str(x)))
                #yield eval(str(y) + "/" + str(x)), op + "/" + str(x)
            except:
                continue
        elif z == 5:
            results.append(eval(str(y) + "-" + str(x)))
            #yield eval(str(y) + "-" + str(x)), op + "-" + str(x)
        else:
            try:
                results.append(eval(str(x) + ops[z] + str(y)))
                #yield eval(str(x) + ops[z] + str(y)), str(x) + ops[z] + op
            except:
                continue
        z = z+1
    return results

def pickTwo(array):
    #returns an array with every 2-combo
    #from input array
    vomit = []
    a,b = 0,1
    while a < (len(array)-1):
        choice = [array[a],array[b]]
        vomit.append((choice,list((Counter(array) - Counter(choice)).elements())))
        if b < (len(array)-1):
            b = b+1
        else:
            b = a+2
            a = a+1
    return vomit

def reduceArray(array):
    if len(array) == 2:
        print("final",array)
        return genOutputs(array[0],array[1])
    else:
        choices = pickTwo(array)
        print(choices)
        for choice in choices:
            opsofchoices = genOutputs(choice[0][0],choice[0][1])
            for each in opsofchoices:
                newarray = list([each] + choice[1])
                print(newarray)
                return reduceArray(newarray)

reduceArray([1,2,3,4])

标签： pythonrecursionmath

Answer 1

The largest issues when dealing with problems like this is handling operator precedence and parenthesis placement to produce every possible number from a given set. The easiest way to do this is to handle operations on a stack corresponding to the reverse polish notation of the infix notation. Once you do this, you can draw numbers and/or operations recursively until all n numbers and n-1 operations have been exhausted, and store the result. The below code generates all possible permutations of numbers (without replacement), operators (with replacement), and parentheses placement to generate every possible value. Note that this is highly inefficient since operators such as addition / multiplication commute so a + b equals b + a, so only one is necessary. Similarly by the associative property a + (b + c) equals (a + b) + c, but the below algorithm is meant to be a simple example, and as such does not make such optimizations.

def expr_perm(values, operations="+-*/", stack=[]):
    solution = []
    if len(stack) > 1:
        for op in operations:
            new_stack = list(stack)
            new_stack.append("(" + new_stack.pop() + op + new_stack.pop() + ")")
            solution += expr_perm(values, operations, new_stack)
    if values:
        for i, val in enumerate(values):
            new_values = values[:i] + values[i+1:]
            solution += expr_perm(new_values, operations, stack + [str(val)])
    elif len(stack) == 1:
        return stack
    return solution

Usage:

result = expr_perm([4,5,6])
print("\n".join(result))