Algorithms – Efficiency Considerations: Nested Loop vs Recursion

I would consider myself an intermediate Python programmer. One of my recent challenges was creating a list of all possible solutions to a given
Countdown problem.
Without getting into too much detail, I have approached the problem through:

• first generating a list of all possible Number-Operator arrangements using RPN

• and then bruteforcing all possible permutations numbers/operators for all possible arrangements, recording the patterns that give me the answer.

The full code listing is further below.

I am aware that this is utterly inefficient and my program takes on the scale of 5-10 minutes to complete.

I have come across an alternative approach here, which uses recursion and generators and finishes considerably faster – on the scale of 30 seconds. My level of understanding of Python does not allow me to just read through the code I found and fully understand the nuances.

I understand that it recursively creates branched expressions with all possible permutations and evaluates them until the correct result is reached, which is essentially another take of what I am doing. I do not understand why that code is orders of magnitude faster than mine.

Operations-wise, the faster code makes on the scale of 5 million attempts, mine makes 15 million attempts, but that still does not match up to the difference in time of execution.

My question: I would be very grateful for a pointer as to what exactly about the class/recursion approach makes it this much more efficient than my rather naive approach to basically the same method.

After tinkering with switching off various modules in the nested loop, I think I narrowed it down. I think, quite disappointingly, that the slowest part is the way I evaluate RPN expressions.

What I did:

• Replaced the line result = RPN_eval(...) with result = [0]. This completes the program in under 9 seconds.

• I then restored the line back to call the RPN_eval(…) function. Instead, I got rid of the attempt string generation and replaced it with a fixed 2 2 + – this version terminated in under 69 seconds…

• Finally, fixing attempt to be 2 2 + 2 + increased the running time to 120 seconds.

Extrapolating (roughly) this finding that each additional number and operator in the expression increases the program time by a factor of around 1.7 – I get total run time of 10-11 minutes, which is what my program shows under normal conditions.

My new question: Therefore, what is the part of the RPN_eval function that seems to be so awkward and slow? Will do more research and formalise this into an actual separate question, not relevant here as such

I think I am onto something – I am trying to dynamically convert RPN pattern expressions into a (horrendous) lambda function, that I can then feed individual number permutations to and yield outcomes, without having to remake the lambda function until the next pattern kicks in. Will add code here once it cooperates…

My code listing:

import itertools as it
import random
import time
operators = ["+", "-", "/", "*"]
count = 0

def RPN_eval(expression, answer): #a standard stack approach to evaluating RPN expressions
    explist = expression.split(" ")
    explist.pop(-1)
    stack = []

    for char in explist:

        if not char in operators:
            stack.append(int(char))
        else:
            if char == "+":
                num1 = stack.pop()
                num2 = stack.pop()

                if num1 > num2:
                    return[-1]

                result = num1 + num2
                stack.append(result)

            if char == "-":
                num1 = stack.pop()
                num2 = stack.pop()
                result = -num1 + num2
                stack.append(result)

            if char == "*":
                num1 = stack.pop()
                num2 = stack.pop()

                if num1 > num2:
                    return [-1]

                result = num1 * num2
                stack.append(result)

            if char == "/":
                divisor = stack.pop()
                divident = stack.pop()

                try:
                    result = divident / divisor
                except:
                    return [-1]

                stack.append(result)

            if result<=0 or result != int(result):
                return [-1]

    return stack

################### This part runs once and generates 37 possible RPN patterns for 6 numbers and 5 operators
def generate_patterns(number_of_numbers): 
#generates RPN patterns in the form NNoNNoo where N is number and o is operator

    patterns = ["N "]

    for pattern1 in patterns:
        for pattern2 in patterns:
            new_pattern = pattern1 + pattern2 + "o "
            if new_pattern.count("N")<=number_of_numbers and new_pattern not in patterns:
                patterns.append(new_pattern)

    return patterns
#######################################


######### Slowest part of program ################
def calculate_solutions(numbers, answer):
    global count
    patterns = generate_patterns(len(numbers)) #RPN symbolic patterns for a given number pool, runs once, takes less than 1 second
    random.shuffle(patterns) #not necessary, but yields answers to look at faster on average
    print(patterns)
    solutions = [] #this list will store answer strings of good solutions. This particular input produces 56 answers.

    for pattern in patterns:
        nn = pattern.count("N") #counts the number of numbers in a symbolic pattern to produce corresponding number group permutations
        no = pattern.count("o") #same for operators
        numpermut = it.permutations(numbers,nn) #all possible permutations of input numbers, is an itertools.permutations object, not a list. Takes 0 seconds to define.

        print(pattern)

        for np in numpermut:
            oppermut = it.product(["+","-","*","/"],repeat=no) #all possible permutations of operator order for a given pattern, itertools object, not a list. Takes 0 seconds to define
            for op in oppermut:
                attempt = ""
                ni = 0
                oi = 0
                for sym in pattern:
                    if "N" in sym:
                        attempt+=str(np[ni])+" " #replace Ns in pattern with corresponding numbers from permutations
                        ni+=1
                    if "o" in sym:
                        attempt+=str(op[oi])+" " #replace os in pattern with corresponding operators from permutations
                        oi+=1

                count+=1
                result = RPN_eval(attempt, answer) #evaluate attempt

                if result[0] == answer:
                    solutions.append(attempt) #if correct, append to list

                    print(solutions)
    return solutions
#####################################    




solns = calculate_solutions([50 , 8 , 3 , 7 , 2 , 10],556)
print(len(solns), count)

And faster code listing:

class InvalidExpressionError(ValueError):
    pass

subtract = lambda x,y: x-y
def add(x,y):
    if x<=y: return x+y
    raise InvalidExpressionError
def multiply(x,y):
    if x<=y or x==1 or y==1: return x*y
    raise InvalidExpressionError
def divide(x,y):
    if not y or x%y or y==1:
        raise InvalidExpressionError
    return x/y

count = 0
add.display_string = '+'
multiply.display_string = '*'
subtract.display_string = '-'
divide.display_string = '/'

standard_operators = [ add, subtract, multiply, divide ]

class Expression(object): pass

class TerminalExpression(Expression):
    def __init__(self,value,remaining_sources):
        self.value = value
        self.remaining_sources = remaining_sources
    def __str__(self):
        return str(self.value)
    def __repr__(self):
        return str(self.value)

class BranchedExpression(Expression):
    def __init__(self,operator,lhs,rhs,remaining_sources):
        self.operator = operator
        self.lhs = lhs
        self.rhs = rhs
        self.value = operator(lhs.value,rhs.value)
        self.remaining_sources = remaining_sources
    def __str__(self):
        return '('+str(self.lhs)+self.operator.display_string+str(self.rhs)+')'
    def __repr__(self):
        return self.__str__()

def ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0):
    global count
    for value, i in zip(sources,range(len(sources))):
        yield TerminalExpression(value=value, remaining_sources=sources[:i]+sources[i+1:])
    if len(sources)>=2+minimal_remaining_sources:
        for lhs in ValidExpressions(sources,operators,minimal_remaining_sources+1):
            for rhs in ValidExpressions(lhs.remaining_sources, operators, minimal_remaining_sources):
                for f in operators:
                    try:
                        count+=1
                        yield BranchedExpression(operator=f, lhs=lhs, rhs=rhs, remaining_sources=rhs.remaining_sources)
                    except InvalidExpressionError: pass

def TargetExpressions(target,sources,operators=standard_operators):
    for expression in ValidExpressions(sources,operators):
        if expression.value==target:
            yield expression

def FindFirstTarget(target,sources,operators=standard_operators):
    for expression in ValidExpressions(sources,operators):
        if expression.value==target:
            return expression
    raise (IndexError, "No matching expressions found")

if __name__=='__main__':
    import time
    start_time = time.time()
    target_expressions = list(TargetExpressions(556,[50,8,3,7,2,10]))
    #target_expressions.sort(lambda x,y:len(str(x))-len(str(y)))
    print ("Found",len(target_expressions),"solutions, minimal string length was:")
    print (target_expressions[0],'=',target_expressions[0].value)
    print()
    print ("Took",time.time()-start_time,"seconds.")
    print(target_expressions)
    print(count)