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

[...] 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):

Prolog solution :-

[...] Pages: 1 2 [...]

A Python 2.7 solution (with a simple timing utility):

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.

[...] 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;

}