The Samovar


Countdown numbers game in Python

One of the things about being ill is that you have to spend a lot of time in bed with nothing much to do. Having watched the whole first series of the Sopranos, I had to find something else. So here’s the result. I revisited an old program I wrote many years ago to solve the Countdown numbers game.

In this game, you’re given six numbers between 1 and 100 and a target number between 100 and 999. You’re given 30 seconds to try to make the target using the six numbers and the operations plus, minus, times and divide.

I originally wrote a program to solve this many years ago (when I was about 14 I think), but the algorithm I used was pretty horrible. I worked out by hand all the possible arrangements of brackets you could have for six numbers, and then tried each operator and number in each appropriate slot. It worked, but it was ugly programming.

Recently I’ve been learning Python for an academic project, and so I thought I may as well try rewriting it in Python. I think the solution I’ve come up with is nicer than any of the solutions I’ve found on the internet (mostly written in Java or C), although having written it I found this paper which uses a very similar solution to mine (but in Haskell rather than Python).

Python programmers might get something from the minimal code below (all comments and docs stripped out), or you can take a look at the full source code here, including detailed comments and docs explaining the code and algorithm.

My ideal (as always with Python) was to write a program you could just look at and understand the source code without comments, but I don’t think I achieved that. I’d be interested if a more experienced Python programmer could do so. Let me know.

This version is incomplete, from the slower version, and is supposed to be understandable without explanations (takes about 40 seconds to find all solutions, too slow for Countdown):

def ValidExpressions(sources,operators=standard_operators,minimal_remaining_sources=0):
    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: 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

This version is actually complete, from the faster version which needs the comments to explain (takes about 15 seconds to run, good enough to win Countdown):

sub = lambda x,y: x-y
def add(x,y):
    if x<=y: return x+y
    raise ValueError
def mul(x,y):
    if x=2+minremsources:
        for e1, rs1, v1 in expressions(sources,ops,minremsources+1):
            for e2, rs2, v2 in expressions(rs1,ops,minremsources):
                for o in ops:
                    try: yield ([o,e1,e2],rs2,o(v1,v2))
                    except ValueError: pass

def findfirsttarget(target,sources,ops=standard_ops):
    for e,s,v in expressions(sources,ops):
        if v==target:
            return e
    return []
Advertisements

6 Comments

i hate you so much your rubbish and discusting you eat poo and you drink wee so there GOODBYE

Comment by bill

you stink at rugby and you have hair like billy idoel and you strip naked in the street you are fat and you frightend little children and aboat these politics no,1 wants to Know and does my face look bovverd because i ain’nt even bovverd so you are not funny you look like a trany and you are guy lol!

Comment by bill

you are a guy lesbeon from bill.

Comment by bill

sorry about the politics and billy idoel hair but its true you are guy bye from bill ,ben and bob sorry bill is still in his flower pot bye! lol lol lol lol lol lol

Comment by bill

Ignore Bill. I suspect you know who he is in real life, but ignore him anyway.
Nice work with the numbers game algorithm. I didn’t look too closely since I’m attempting to write a solver in C. Code looks short and sweet, though. Good work!

Comment by James Stanley

Hi James, I don’t know him/them I figure they’re just some kids that found their way here.

Good luck with writing your solver. You should be able to write one that’s a lot more efficient than that, I wrote it for maximum comprehensibility rather than speed. Once you’ve written your algorithm, you might find it interesting to read the discussion we had about this on the comp.lang.python group (search for countdown numbers game).

Comment by Dan | thesamovar




Comments are closed.



%d bloggers like this: