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

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 […]

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

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;
}