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.
I've tried a completely different approach, that I imagine as
'folding'. I thought it would improve performance over my previous
effort but extremely limited and crude benchmarking seems to indicate
disappointingly comparable performance...
def ops(a, b):
"Generate all possible ops on two numbers with histories"
x, hx = a
y, hy = b
if x < y:
x, y, hx, hy = y, x, hy, hx
yield x + y, (hx, '+', hy)
if x != 1 and y != 1:
yield x * y, (hx, '*', hy)
if x != y:
yield x - y, (hx, '-', hy)
if not x % y and y != 1:
yield x / y, (hx, '/', hy)
def fold(nums, action, ops=ops):
"""Perform all possible ways of folding nums using ops.
Side-effect action triggered for every fold."""
nums = zip(nums, nums) # Attach a history to each number
def recfold():
for i in xrange(1, len(nums)):
a = nums.pop(i) # Take out a number;
for j in xrange(i):
b = nums[j] # choose another before it;
for x in ops(a, b): # combine them
nums[j] = x # into one;
action(x) # (with side-effect)
recfold() # then fold the shorter list.
nums[j] = b
nums.insert(i, a)
recfold()
def all_countdown(nums, target):
"Return all ways of reaching target with nums"
all = set()
def action(nh):
if nh[0] == target:
all.add(pretty(nh[1]))
fold(nums, action)
return all
def print_countdown(nums, target):
"Print all solutions"
print '\n'.join(all_countdown(nums, target))
class FoundSolution(Exception):
def __init__(self, sol):
self.sol = sol
def first_countdown(nums, target):
"Return one way of reaching target with nums"
def action(nh):
if nh[0] == target:
raise FoundSolution(nh[1])
try:
fold(nums, action)
except FoundSolution, fs:
return pretty(fs.sol)
# pretty helpers
def getop(h): return 'n' if isinstance(h, int) else h[1]
lbracket = ['+*', '-*', '+/', '-/', '/*', '//']
rbracket = ['*+', '*-', '/+', '/-', '/*', '//', '-+', '--']
def pretty(h):
"Print a readable form of a number's history"
if isinstance(h, int):
return str(h)
else:
x, op, y = h
x, y, xop, yop = pretty(x), pretty(y), getop(x), getop(y)
if xop + op in lbracket: x = "(%s)" % x
if op + yop in rbracket: y = "(%s)" % y
return ''.join((x, op, y))
--
Arnaud
--
http://mail.python.org/mailman/listinfo/python-list
