Just for fun: Countdown numbers game solver

Arnaud Delobelle arnodel at googlemail.com
Mon Jan 21 08:21:04 CET 2008


On Jan 21, 3:19 am, Terry Jones <te... at jon.es> wrote:
> Here's a solution that doesn't use any copying of lists in for recursion.
> It also eliminates a bunch of trivially equivalent solutions. The countdown
> function is 37 lines of non-comment code.  Sample (RPN) output below.
>
> Terry

[snip code]

> This produces:
[...]
> Target 234, numbers = (100, 9, 7, 6, 3, 1)
>         (6, 1, 'add', 100, 'mul', 7, 'sub', 9, 'add', 3, 'div')
>         (100, 1, 'sub', 3, 'div', 7, 'mul', 6, 'sub', 9, 'add')
>         (7, 6, 'mul', 3, 'mul', 100, 'sub', 9, 'mul', 1, 'mul')
>         (100, 7, 'sub', 3, 'div', 6, 'sub', 1, 'add', 9, 'mul')
>         (7, 6, 'mul', 3, 'mul', 1, 'sub', 100, 'add', 9, 'add')
>         (6, 9, 'sub', 7, 'mul', 1, 'sub', 100, 'add', 3, 'mul')
>         (100, 9, 'sub', 7, 'sub', 6, 'sub', 3, 'mul', 1, 'mul')
>         (100, 7, 'mul', 3, 'mul', 6, 'add', 9, 'div', 1, 'mul')
>         (100, 1, 'sub', 7, 'mul', 9, 'sub', 3, 'div', 6, 'add')
>         (100, 7, 'sub', 3, 'div', 1, 'sub', 9, 'add', 6, 'mul')
>         (7, 3, 'mul', 6, 'sub', 9, 'mul', 1, 'sub', 100, 'add')
>         (100, 7, 'mul', 6, 'sub', 1, 'sub', 9, 'add', 3, 'div')
>         (100, 9, 'add', 7, 'add', 1, 'add', 3, 'div', 6, 'mul')
>         (100, 9, 'sub', 7, 'div', 6, 'mul', 3, 'mul', 1, 'mul')

In countdown you are not required to use all numbers to reach the
target.  This means you are missing solutions, e.g.
        (1, 3, 6, 'mul', 'add', 7 , 'add', 9, 'mul')

After a quick glance at your code it seems to me that you can only
have solutions of the type:
        (num, num, op, num, op, num, op, num, op, num, op)
this omits many possible solutions (see the one above).

--
Arnaud




More information about the Python-list mailing list