# send+most=money

## Problem

```   send
+ most
------
money
```

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). There are multiple valid assignments, the one which maximizes the value of “money” is sought.

## Code

``` 1 require 'rubygems'
2 require 'gecoder'
3
4 # Solves the cryptarithmetic send+most=money problem while maximizing the value
5 # of "money".
6 class SendMostMoney
7   include Gecode::Mixin
8
9   attr :money
10
11   def initialize
12     # Set up the variables, 9 letters with domain 0..9.
13     s,e,n,d,m,o,s,t,y = letters_is_an int_var_array(9, 0..9)
14     # Express the quantity we are optimizing, in this case money.
15     # This utilises that any operand can be converted into a variable.
16     @money = equation_row(m,o,n,e,y).to_int_var
17
18     # Set up the constraints.
19     # The equation must hold.
20     (equation_row(s, e, n, d) + equation_row(m, o, s, t)).must ==
21       equation_row(m, o, n, e, y)
22
23     # The initial letters may not be 0.
24     s.must_not == 0
25     m.must_not == 0
26
27     # All letters must be assigned different digits.
28     letters.must_be.distinct
29
30     # Set the branching.
31     branch_on letters, :variable => :smallest_size, :value => :min
32   end
33
34   private
35
36   # A helper to make the linear equation a bit tidier. Takes a number of
37   # variables and computes the linear combination as if the variable
38   # were digits in a base 10 number. E.g. x,y,z becomes
39   # 100*x + 10*y + z .
40   def equation_row(*variables)
41     variables.inject{ |result, variable| variable + result * 10 }
42   end
43 end
44
45 solution = SendMostMoney.new.maximize! :money
46 puts 's e n d m o s t y'
47 puts solution.letters.values.join(' ')
48 puts "money: #{solution.money.value}"
```

## Output

``````s e n d m o s t y
3 7 8 2 1 0 9 4 6
money: 10876``````