## 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 `require`s 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.

Pages: 1 2

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

9. Bushra Hamed said

Can you provide code to solve any words user prompt in java script?