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