Alphametric fun with Python

[Raymond Hettinger]

Thought you guys might enjoy this:

http://code.activestate.com/recipes/576615/

SEND + MORE == MONEY
9567 + 1085 == 10652


Raymond Hettinger

 

[bearophileHUGS]

Raymond Hettinger:

Thought you guys might enjoy this:
   http://code.activestate.com/recipes/576615/

Nice and short, but it's also very slow on my PC (Psyco may help).

This solves them in moments:
http://labix.org/python-constraint

Bye,
bearophile

 

[Raymond Hettinger]

Thought you guys might enjoy this:

Nice and short, but it's also very slow on my PC (Psyco may help).

This solves them in moments:http://labix.org/python-constraint

Intelligent search beats brute force permutation search.
The constraint solver is pretty nice.
The recipe is mainly about how to use itertools.permutations()
for simple programs that take minutes to write and get the job done.

Raymond

 

[bearophileHUGS]

Raymond Hettinger:

for simple programs that take minutes to write and get the job done.

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")
p.addrule("(e*100+n*10+d+o*100+r*10+e)%1000 == n*100+e*10+y")
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")
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

Probably it's not too much difficult to write a code able to solve a
more general alphametric problem: you can write it more or less like
yours, but it leads to a single equation, that is slow to solve. To
give the solver engine a chance to speed up the computation you have
to split the single equation into many equations. This allows the
solver to prune that large search space in a faster way (the search
space may have 3+ millions items so it's not huge anyway).

Bye,
bearophile

 

[Terry Reedy]

Raymond Hettinger:

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_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_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

 

[bearophileHUGS]

Terry Reedy:

It illustrates well the point you intended.

I don't know what my point was.

A suggestion: with that solver, to find solution in a faster way you
have to write many equations.

Bye,
bearophile

 

[Terry Reedy]

Terry Reedy:

I don't know what my point was.

I quoted and was responding to Raymond.

A suggestion: with that solver, to find solution in a faster way you
have to write many equations.

I did... one for each column + plus the implied one that digits
represented by the same letter get same value and that those represented
by different letters gets different values.