Just for fun: Countdown numbers game solver

[Arnaud Delobelle]

On Jan 20, 5:41 pm, dg.google.gro... at thesamovar.net wrote:
> Ever since I learnt to program I've always loved writing solvers for
> the Countdown numbers game problem in different languages, and so now
> I'm wondering what the most elegant solution in Python is.
>
> If you don't know the game, it's simple: you're given six randomly
> chosen positive integers, and a target (another randomly chosen
> positive integer), and you have to make the target using only the
> numbers you're given, and +,-,* and / (and any number of brackets you
> like). You're not allowed fractions as intermediate values. So, given
> 2, 3 and 5 say, and a target of 21, you could do (2+5)*3 = 21.
>

Neat problem!  I couldn't help but have a go.  I have no idea how
efficient it is, I didn't think too much before I started typing :)


def partitions(l):
    """"split(l) -> an iterator over all partitions of l into two
lists

    There is no repetition provided that all elements of l are
distinct."""
    # Works only for lists of length < 8*size(int) due to xrange
limitations
    for i in xrange(1, 2**len(l)-1, 2):
        partition = [], []
        for x in l:
            i, r = divmod(i, 2)
            partition[r].append(x)
        yield partition

def calc(l, filter=lambda *x:x):
    """calc(l, filter) -> an iterator over all expressions involving
all
    numbers in l

    filter is a function that returns its two arguments with possible
    side-effects. """
    if len(l) == 1:
        yield l[0], str(l[0])
    else:
        for l1, l2 in partitions(l):
            for v1, s1 in calc(l1, filter):
                for v2, s2 in calc(l2, filter):
                    yield filter(v1 + v2, '(%s+%s)' % (s1, s2))
                    yield filter(v1 * v2, '(%s*%s)' % (s1, s2))
                    if v1 > v2:
                        yield filter(v1 - v2, '(%s-%s)' % (s1, s2))
                    elif v2 > v1:
                        yield filter(v2 - v1, '(%s-%s)' % (s2,
s1))
                    if not v1 % v2:
                        yield filter(v1 / v2, '(%s/%s)' % (s1, s2))
                    elif not v2 % v1:
                        yield filter(v2 / v1, '(%s/%s)' % (s2, s1))


def print_filter(target):
    """print_filter(target) -> filter that prints all expressions that
    equal target"""
    def filter(v, s):
        if v == target: print s
        return v, s
    return filter

class ShortestFilter(object):
    def __init__(self, target):
        self.shortest = None
        self.target = target
    def __call__(self, v, s):
        if v == self.target:
            if not self.shortest or len(self.shortest) > len(s):
                self.shortest = s
        return v, s

def countdown(numbers, target):
    """countown(numbers, target) -> None -- print all countdown
solutions"""
    for dummy in calc(numbers, print_filter(target)): pass

def best_countdown(numbers, target):
    """best_countdown(numbers, target) -> str -- return shortest
solution"""
    filter = ShortestFilter(target)
    for dummy in calc(numbers, filter): pass
    return filter.shortest

>>> countdown([7,8,50,8,1,3], 923)
(((((50*8)-1)/3)*7)-8)
(((((50*8)-1)*7)/3)-8)
(((((8*50)-1)/3)*7)-8)
(((((8*50)-1)*7)/3)-8)
>>> print best_countdown([100,9,7,6,3,1], 234)
(((1+(3*6))+7)*9)


--
Arnaud