Alphametric fun with Python

Discussion in 'Python' started by Raymond Hettinger, Jan 15, 2009.

  1. Raymond Hettinger, Jan 15, 2009
    #1
    1. Advertising

  2. Raymond Hettinger

    Guest

    , Jan 15, 2009
    #2
    1. Advertising

  3. > > 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


    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
    Raymond Hettinger, Jan 15, 2009
    #3
  4. Raymond Hettinger

    Guest

    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
    , Jan 15, 2009
    #4
  5. Raymond Hettinger

    Terry Reedy Guest

    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_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
    Terry Reedy, Jan 16, 2009
    #5
  6. Raymond Hettinger

    Guest

    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
    , Jan 16, 2009
    #6
  7. Raymond Hettinger

    Terry Reedy Guest

    wrote:
    > Terry Reedy:
    >> It illustrates well the point you intended.

    >
    > 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.
    Terry Reedy, Jan 16, 2009
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andy Fish
    Replies:
    65
    Views:
    1,702
    Mabden
    May 18, 2004
  2. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    382
    bruno modulix
    Feb 11, 2005
  3. Replies:
    1
    Views:
    313
    Andy Robinson
    Feb 24, 2005
  4. dolphin
    Replies:
    4
    Views:
    312
    Jorgen Grahn
    Aug 25, 2007
  5. er
    Replies:
    2
    Views:
    487
Loading...

Share This Page