Just for fun: Countdown numbers game solver
Arnaud Delobelle
arnodel at googlemail.com
Mon Jan 21 02:21:04 EST 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