SEND + MORE = MONEY, Part 1

July 31, 2012

Our first solution uses a set of nested lists to generate all possible solutions, then tests each, stopping as soon as it finds a valid solution. Non-Scheme programmers can ignore the call-with-current-continuation at the top, which is the Scheme idiom that creates a return statement that can interrupt a computation:

(define (send-more-money)
  (call-with-current-continuation
    (lambda (return)
      (do ((s 1 (+ s 1))) ((= s 10))
        (do ((e 0 (+ e 1))) ((= e 10))
          (do ((n 0 (+ n 1))) ((= n 10))
            (do ((d 0 (+ d 1))) ((= d 10))
              (do ((m 1 (+ m 1))) ((= m 10))
                (do ((o 0 (+ o 1))) ((= o 10))
                  (do ((r 0 (+ r 1))) ((= r 10))
                    (do ((y 0 (+ y 1))) ((= y 10))
                      (when (and (distinct? (list s e n d m o r y))
                                 (= (+ (* 1000 s) (* 100 e) (* 10 n) d
                                       (* 1000 m) (* 100 o) (* 10 r) e)
                                    (+ (* 10000 m) (* 1000 o) (* 100 n) (* 10 e) y)))
                        (return (list (list s e n d) (list m o r e) (list m o n e y)))))))))))))))

The termination test checks if all digits are distinct using the following function:

(define (distinct? xs)
  (cond ((null? xs) #t)
        ((member (car xs) (cdr xs)) #f)
        (else (distinct? (cdr xs)))))

Here’s an example:

> (send-more-money)
((9 5 6 7) (1 0 8 5) (1 0 6 5 2))

The backtracking solution uses John McCarthy’s amb function, which we have seen previously. The programming is declarative rather than imperative; there is not a single loop or assignment, no control flow anywhere in the function, just a list of possibilities for each variable and a list of requirements that must be satisfied.

(define (send-more-money)
  (let ((s (amb   1 2 3 4 5 6 7 8 9))
        (e (amb 0 1 2 3 4 5 6 7 8 9))
        (n (amb 0 1 2 3 4 5 6 7 8 9))
        (d (amb 0 1 2 3 4 5 6 7 8 9))
        (m (amb   1 2 3 4 5 6 7 8 9))
        (o (amb 0 1 2 3 4 5 6 7 8 9))
        (r (amb 0 1 2 3 4 5 6 7 8 9))
        (y (amb 0 1 2 3 4 5 6 7 8 9)))
    (require (distinct? (list s e n d m o r y)))
    (require (=                (amb 0 1)      m))
    (require (= (modulo (+ s m (amb 0 1)) 10) o))
    (require (= (modulo (+ e o (amb 0 1)) 10) n))
    (require (= (modulo (+ n r (amb 0 1)) 10) e))
    (require (= (modulo (+ d e (amb 0 1)) 10) y))
    (require (= (+             (* 1000 s) (* 100 e) (* 10 n) d
                               (* 1000 m) (* 100 o) (* 10 r) e)
                (+ (* 10000 m) (* 1000 o) (* 100 n) (* 10 e) y)))
    (list (list s e n d) (list m o r e) (list m o n e y))))

The first require sets up the condition that all variables are distinct. The next five requires set up the column sums; note the amb for the carry. The final require ensures the solution is valid. Here’s an example:

> (send-more-money)
((9 5 6 7) (1 0 8 5) (1 0 6 5 2))

You can see the complete program, including amb, at http://programmingpraxis.codepad.org/NIkMrLqf. Unfortunately, both versions of the program are very slow, about a quarter of a minute, especially the backtracking version with all of the non-deterministic calls to amb. We’ll see a much faster version of the program in the next exercise.

About these ads

Pages: 1 2

9 Responses to “SEND + MORE = MONEY, Part 1”

  1. [...] today’s Programming Praxis exercise, our goal is to provide two different solutions for the well known SEND [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/31/programming-praxis-send-more-money-part-1/ for a version with comments):

    import Data.List
    
    send1 :: ([Integer], [Integer], [Integer])
    send1 = head [([s,e,n,d], [m,o,r,e], [m,o,n,e,y])
                 | s <- [1..9], e <- [0..9], n <- [0..9], d <- [0..9]
                 , m <- [1..9], o <- [0..9], r <- [0..9], y <- [0..9]
                 , length (group $ sort [s,e,n,d,m,o,r,y]) == 8
                 , 1000*(s+m) + 100*(e+o) + 10*(n+r) + d+e ==
                   10000*m + 1000*o + 100*n + 10*e + y]
    
    send2 :: (Integer, Integer, Integer)
    send2 = head [ (send, more, money) | (s:e:n:d:m:o:r:y:_) <- permutations [0..9]
                 , s /= 0, m /= 0, let fill = foldl ((+) . (* 10)) 0
                 , let send = fill [s,e,n,d], let more = fill [m,o,r,e]
                 , let money = fill [m,o,n,e,y], send + more == money]
    
  3. David said

    Prolog solution :-

    d1_9(1).
    d1_9(2).
    d1_9(3).
    d1_9(4).
    d1_9(5).
    d1_9(6).
    d1_9(7).
    d1_9(8).
    d1_9(9).
    
    digit(0).
    digit(X) :- d1_9(X).
    
    distinct([]).
    distinct([X|Xs]) :- not(member(X, Xs)), distinct(Xs).
    
    sendmoremoney :-
       d1_9(S), digit(E), digit(N), digit(D), d1_9(M), digit(O), digit(R), digit(Y),
       distinct([S, E, N, D, M, O, R, Y]),
       SEND is 1000*S + 100*E + 10*N + D,
       MORE is 1000*M + 100*O + 10*R + E,
       MONEY is 10000*M + 1000*O + 100*N + 10*E + Y,
       MONEY is SEND + MORE,
       print([[S, E, N, D], [M, O, R, E], [M, O, N, E, Y]]).
    
    ?- sendmoremoney.
    [[9,5,6,7],[1,0,8,5],[1,0,6,5,2]]
    
  4. A Python 2.7 solution (with a simple timing utility):

    
    import time
    import itertools
    
    
    def timeit(fn):
        def wrapper():
            start = time.clock()
            ret = fn()
            elapsed = time.clock() - start
            print("%s took %2.fs" % (fn.__name__, elapsed))
            return ret
        return wrapper
    
    
    @timeit
    def solve1():
        for s in xrange(1, 10):
            for e in xrange(0, 10):
                for n in xrange(0, 10):
                    for d in xrange(0, 10):
                        for m in xrange(1, 10):
                            for o in xrange(0, 10):
                                for r in xrange(0, 10):
                                    for y in xrange(0, 10):
                                        if distinct(s, e, n, d, m, o, r, y):
                                            send = 1000 * s + 100 * e + 10 * n + d
                                            more = 1000 * m + 100 * o + 10 * r + e
                                            money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
                                            if send + more == money:
                                                return send, more, money
    
    
    def distinct(*args):
        return len(set(args)) == len(args)
    
    
    @timeit
    def solve2():
        letters = ('s', 'e', 'n', 'd', 'm', 'o', 'r', 'y')
        digits = range(10)
        for perm in itertools.permutations(digits, len(letters)):
            sol = dict(zip(letters, perm))
            if sol['s'] == 0 or sol['m'] == 0:
                continue
            send = 1000 * sol['s'] + 100 * sol['e'] + 10 * sol['n'] + sol['d']
            more = 1000 * sol['m'] + 100 * sol['o'] + 10 * sol['r'] + sol['e']
            money = 10000 * sol['m'] + 1000 * sol['o'] + 100 * sol['n'] + 10 * sol['e'] + sol['y']
            if send + more == money:
                return send, more, money
    
    
    print(solve1())
    print(solve2())
    
    

    On my machine (i7-2630QM @ 2GHZ, Win7 64bit, Python 2.7.2 32bit) solve1() takes around 95s, solve2() around 5s.

  5. madscifi said

    OpenMP used to parallelize the search.

    #include <iostream>
    //
    // compile with: g++ -O3 -fopenmp -std=c++0x sendmoremoney.cpp
    //
    template<typename A>
    bool FirstNotAmoungRest( const A& a )
    {
        return true;
    }
    
    template<typename A, typename B, typename... R>
    bool FirstNotAmoungRest( const A& a, const B& b, const R&... r )
    {
        return a != b && FirstNotAmoungRest( a, r... );
    }
    
    template<typename A>
    bool Distinct( const A& a )
    {
        return true;
    }
    
    template<typename A, typename... R>
    bool Distinct( const A& a, const R&... r )
    {
        return FirstNotAmoungRest( a, r... ) && Distinct( r... );
    }
    
    int main( int argc, char**argv )
    {
        #pragma omp parallel for
        for( int s = 1; s < 10; ++s )
        for( int e = 0; e < 10; ++e )
        for( int n = 0; n < 10; ++n )
        for( int d = 0; d < 10; ++d )
        for( int m = 1; m < 10; ++m )
        for( int o = 0; o < 10; ++o )
        for( int r = 0; r < 10; ++r )
        for( int y = 0; y < 10; ++y )
        {
            if( Distinct( s, e, n, d, m, o, r, y ) )
            {
                int v1 = s*1000+e*100+n*10+d;
                int v2 = m*1000+o*100+r*10+e;
                int v3 = m*10000+o*1000+n*100+e*10+y;
                if( v1 + v2 == v3 )
                {
                    #pragma omp critical
                    std::cout << v1 << "+" << v2 << "=" << v3 << std::endl;
                }
            }
        }
    }
    
  6. [...] are a few ways that you could brute force the problem (discussed in a previous Programming Praxis article), but where’s the fun in that? I wanted to go ahead and work on the hill climbing version in [...]

  7. josé carlos said

    I solve this problem vith evolver 5.5 in best time of 00:44. Reálly is more easy reolve this problem with this excel excel addin.

    I can send this file

  8. casey said

    //casey cole
    //Lamar University
    #include
    using namespace std;

    int main()
    {

    for( int t = 0; t < 10; t++ )
    for( int o = 0; o < 10; o++ )
    // put g starting at 1 so != to 0
    for( int g = 1; g < 10; g++ )
    for( int d = 0; d < 10; d++)
    //first if makes sure none of the letter are the same
    if (t != o && t != d && t != g && g != o && g != d && d != o)
    //second if checks if they are equal
    if ((t*100 + o*10 + o) * 4 == g*1000 + o*100 +o*10 +d){
    cout << g << o << o << d << " = good\n";
    cout << t << o << o << " = too";
    }
    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 613 other followers

%d bloggers like this: