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.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to provide two different solutions for the well known SEND […]
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]Prolog solution :-
[…] Pages: 1 2 […]
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; } } } }[…] 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 […]
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
//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;
}
Can you provide code to solve any words user prompt in java script?