On Jan 20, 5:41 pm, [EMAIL PROTECTED] 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
--
http://mail.python.org/mailman/listinfo/python-list
