Countdown solver in Python

countdown.py

import random

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, '/')]

def OneFromTheTop():
    return [25, 50, 75][random.randint(0,2)]

def OneOfTheOthers():
    return random.randint(1,10)

def Evaluate(stack):
    try:
        total = 0
        lastOper = add
        for item in stack:
            if type(item) is int:
                total = lastOper(total, item)
            else:
                lastOper = item[0]

        return total
    except:
        return 0

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):

    def Recurse(stack, nums):
        for n in range(len(nums)):
            stack.append( nums[n] )

            remaining = nums[:n] + nums[n+1:]

            if Evaluate(stack) == target:
                print(ReprStack(stack))

            if len(remaining) > 0:
                for op in operations:
                    stack.append(op)
                    stack = Recurse(stack, remaining)
                    stack = stack[:-1]

            stack = stack[:-1]

        return stack

    Recurse([], numbers)


target = random.randint(100,1000)

numbers = [ OneFromTheTop() ] + [ OneOfTheOthers() for i in range(5) ]

print("Target: {0} using {1}".format(target, numbers))

Solve(target, numbers)

Super clean code though. If a little unconventional to use pascal case function names in python 🏆

Hey! This works perfectly but i couldn't figure out the working of your solver algorithm. Could you explain it with some comments on the code please?

I have also written a Countdown numbers solver. I'm testing it by trying the numbers 1 to 6 with all target values from 1 to 720. My code gets an exact solution for 517 targets, whereas yours gets 498. As an example, your code does not find the solution for 279, which is:

6 + 2 = 8
4 + 3 = 7
8 * 7 * 5 = 280
280 - 1 = 279

However, your code is much shorter and simpler than mine (which was a nightmare to write), so I'd be interested to hear if it could be made to work while finding all the solutions. I don't know for sure that mine does find all solutions, the only way I have of testing it is to find other programs that do the same thing and see if they find solutions that mine doesn't.