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
--
http://mail.python.org/mailman/listinfo/python-list
