# send+more=money

## Problem

```   send
+ more
------
money
```

The problem is to, given the above equation, assign digits to each letter so that the equation holds when the letter are substituted with the assigned digits. No two letter may be assigned the same digit and the first letter of a word is not allowed to be assigned 0 (i.e. a number may not start with 0 in the equation).

## Code

``` 1 require 'rubygems'
2 require 'gecoder'
3
4 # Solves the send+more=money problem:
5 # http://en.wikipedia.org/wiki/Send%2Bmore%3Dmoney
6 solution = Gecode.solve do
7   # A helper to make the linear equation a bit tidier. Takes a number of
8   # variables and computes the linear combination as if the variable
9   # were digits in a base 10 number. E.g. x,y,z becomes
10   # 100*x + 10*y + z .
11   def equation_row(*variables)
12     variables.inject{ |result, variable| variable + result*10 }
13   end
14
15   # Set up the variables.
16   # Let "letters" be an array of 8 integer variables with domain 0..9.
17   # The elements represents the letters s, e, n, d, m, o, r and y.
18   letters_is_an int_var_array(8, 0..9)
19   s,e,n,d,m,o,r,y = letters
20
21   # Set up the constraints.
22   # The equation must hold.
23   (equation_row(s, e, n, d) + equation_row(m, o, r, e)).must ==
24     equation_row(m, o, n, e, y)
25
26   # The initial letters may not be 0.
27   s.must_not == 0
28   m.must_not == 0
29
30   # All letters must be assigned different digits.
31   letters.must_be.distinct
32
33   # Tell Gecode what variables we want to know the values of.
34   branch_on letters, :variable => :smallest_size, :value => :min
35 end
36
37 puts 's e n d m o r y'
38 puts solution.letters.values.join(' ')
```

## Output

``````s e n d m o r y
9 5 6 7 1 0 8 2``````

A more general solution is available as a submission to Ruby Quiz #128 – Verbal Arithmetic.