SEND + MORE = MONEY, Part 1

July 31, 2012

A classic puzzle of recreational mathematics is the cryptarithm, where the solver is given a math problem in words and must systematically substitute digits for the letters of the puzzle to form a valid calculation. For instance, the famous cryptarithm SEND + MORE = MONEY is solved as M=1, Y=2, E=5, N=6, D=7, R=8, S=9 and O=0, giving 9567 + 1085 = 10652. Cryptarithms were invented by H. E. Dudeney in the July 1924 edition of Strand Magazine.

We are going to give four solutions to this puzzle, two slow ones today and two fast ones in the next exercise. Our first solution is simple brute force, using nested loops to generate all possible solutions and testing each to see if it forms a valid calculation. Our second solution is backtracking, which is similar to the generate-and-test solution.

Your task is to write the two solutions to the SEND + MORE = MONEY problem described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 577 other followers

%d bloggers like this: