Arnaud Delobelle <[EMAIL PROTECTED]> writes:
> 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).
Here's my latest, which I think is exhaustive, but it is very slow.
It prints a progress message now and then just to give the user some
sign of life. It should print a total of 256-8 = 248 of those
messages and it takes around 20 minutes on my old 1 Ghz Pentium 3. It
does find plenty of solutions for 234, e.g.
234 mul(9,sub(mul(mul(6,mul(3,1)),7),100))
There are some obvious clunky ways to speed it up through memoizing
and symmetry folding but I can't help thinking there's a concise
elegant way to do that too.
================================================================
from operator import *
from time import time, ctime
start_time = time()
def partition(k):
for i in xrange(1, (1<<k) - 1):
yield tuple(bool(i & (1<<j)) for j in xrange(k))
ams = [add,mul,sub]
def countdown(nums, trace='', ops=[add,mul,sub,div]):
d = div in ops
if len(nums) == 1:
yield nums[0], str(nums[0])
for p1 in partition(len(nums)):
n0s = list(a for p,a in zip(p1, nums) if p)
n1s = list(a for p,a in zip(p1, nums) if not p)
for f in ops:
if d: print '->', n0s, f, '%.3f'%(time()-start_time)
for r0,t0 in countdown(n0s, trace, ams):
for r1,t1 in countdown(n1s, trace, ams):
if f != div or r1 != 0 and r0 % r1 == 0:
yield f(r0, r1), \
'%s(%s,%s)'% (f.__name__, t0, t1)
def find_repr(target, nums):
for x,t in countdown(nums):
if x == target:
print x,t
print ctime()
find_repr(234, [100,9,7,6,3,1])
--
http://mail.python.org/mailman/listinfo/python-list
