Just for fun: Countdown numbers game solver

marek.rocki at wp.pl marek.rocki at wp.pl
Sun Jan 20 21:06:57 CET 2008


Nice challenge! I came up with something like this:

def find_repr(target, numbers):
	org_reprs = dict((number, str(number)) for number in numbers)
	curr_reprs = org_reprs
	while target not in curr_reprs:
		old_reprs, curr_reprs = curr_reprs, {}
		for x in old_reprs:
			for y in org_reprs:
				repr_x, repr_y = old_reprs[x], old_reprs[y]
				curr_reprs[x + y] = '(%s)+(%s)' % (repr_x, repr_y)
				curr_reprs[x - y] = '(%s)-(%s)' % (repr_x, repr_y)
				curr_reprs[x * y] = '(%s)*(%s)' % (repr_x, repr_y)
				if y <> 0 and x % y == 0:
					curr_reprs[x // y] = '(%s)/(%s)' % (repr_x, repr_y)
		curr_reprs.update(old_reprs)
	return curr_reprs[target]

print '21 =', find_repr(21, [2, 3, 5])
print '923 =', find_repr(923, [7, 8, 50, 8, 1, 3])

Unfortunately, this yields solutions that are a bit lispish (as in
'lots of superfluous parentheses' in the result). Nothing a simple
regex or two wouldn't fix ;-) And the solution found would be minimal
not with respect to the string length, but rather to the number of
operations to be performed.

Apart from that, I find it quite elegant. I'd like to know if it has
any flaws.

Regards,
Marek



More information about the Python-list mailing list