bearophileh...@lycos.com wrote:
Raymond Hettinger:
for simple programs that take minutes to write and get the job done.
Thank you for posting this. It illustrates well the point you intended.
For fun here's a specific example:
from csp import Problem, timing
print "SEND+MORE=MONEY problem:"
p = Problem("recursivebacktracking")
p.addvars("sendmory", range(10))
p.addrule(lambda d,e,y: (d+e)%10 == y) # alternative syntax
p.addrule("(n*10+d+r*10+e)%100 == e*10+y")
This effectively include the first rule and makes it redundant in a way.
Better, I expect (but leave to you to check), would be
(n*10+d+r*10+e)%100 / 10 == e
p.addrule("(e*100+n*10+d+o*100+r*10+e)%1000 == n*100+e*10+y")
(e*100+n*10+d+o*100+r*10+e)%1000 / 100 == n
p.addrule("1000*s+100*e+10*n+d + 1000*m+100*o+10*r+e == 10000*m+1000*o
+100*n+10*e+y")
temp = 1000*s+100*e+10*n+d + 1000*m+100*o+10*r+e
temp%10000 / 1000 == o
temp / 10000 == m
p.notin([0], "sm")
p.alldifferent()
solutions, time = timing(p.solutions)
print "Computing time:", time, "s"
for s in solutions:
print "%(s)d%(e)d%(n)d%(d)d + %(m)d%(o)d%(r)d%(e)d = %(m)d%(o)d%(n)
d%(e)d%(y)d" % s
print
Given 'expression == char' for each column, the equalities could be
turned into assignments (or checks).
For every possible assignment to d and e, let y = (d+e) % 10.
For every possible assignment of unused numbers to unbound chars in
the second column expression, let e = (n*10+d+r*10+e)%100 / 10
To generalize, 0 pad all lines to match the sum. Then each nested loop
can be expressed in more detail as
for each possible assignment of unused numbers to unbound chars
in column_i: # break if none possible
div = 10**i
num = column_0_to_i_sum % (10*div) / div
if sum[i]_char is not bound:
Probably it's not too much difficult to write a code able to solve a
more general alphametric problem:
Hmm. For alphametric problems specifically, 'expression == char' for
each column could be turned into assignments (or checks).
0 pad all lines to match the sum. Then nest column loops right to left.
for each possible assignment of unused numbers to unbound chars
in column_i: # include non-zero constraint and break if none possible
div = 10**i
num = column_0_to_i_sum % (10*div) / div
if sum[i]_char is not bound: bind to num
else: check that is num and break if not
if last (leftmost) column: print solution
else loop on column to left
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
