# Jacques's Blog

## How to solve the MONEY problem with Go

Jun 4, 2018 | 6 minutes read

Tags: golang, algorithm

Learning Go could probably help you get a good job, but this is not the subject of this post. Here we will show you how to solve the classical verbal arithmetic puzzle, “SEND + MORE = MONEY”. The goal is to find the mapping between the letters and the digits such that the addition is correct.

## Data structure

We will use object-oriented style of programming, so we start by defining a type for the puzzle:

 ``````11 12 13 14 `````` ``````type verbalSum struct { operands []string result string }``````

This type stores the operands of the addition (e.g. “SEND” and “MORE”) and the result (e.g. “MONEY”).

We want to be able to print the puzzle, so we implement the `String` method:

 ``````112 113 114 `````` ``````func (v verbalSum) String() string { return strings.Join(v.operands, " + ") + " = " + v.result }``````

Solving this puzzle actually means to find the correct mapping between the letters and the digits. In Go, we can simply use a `map` where the keys are runes and the values are integers.

When we have a mapping, here is how we can convert a text to the corresponding number:

 ``````16 17 18 19 20 21 22 23 24 25 `````` ``````func verbToInt(verb string, mapping map[rune]int) int { if mapping[[]rune(verb)] == 0 { return -1 } result := 0 for _, c := range []rune(verb) { result = result*10 + mapping[c] } return result }``````

The test at line 17 returns an error if the resulting number would start with a zero. It would probably be more elegant to return an error in Go, but this would occur so many times that the impact on the performance would be too high.

Having this function, we can now easily implement a method that takes a mapping and returns the numerical representation of the solution:

 ``````116 117 118 119 120 121 122 123 124 `````` ``````func (v verbalSum) solutionString(mapping map[rune]int) string { args := make([]string, len(v.operands)) for i, x := range v.operands { n := verbToInt(x, mapping) args[i] = strconv.Itoa(n) } n := verbToInt(v.result, mapping) return strings.Join(args, " + ") + " = " + strconv.Itoa(n) }``````

## Algorithm

The “heart” of the solution is a recursive functions that take 3 arguments:

• A list of letters that are not yet assigned to a digit
• A list of available digits
• The current letter to digit mapping

For statistical purposes, the recursive function returns the number of combinations evaluated and the number of solutions found.

 ``````70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 `````` ``````func (v verbalSum) recursiveSolve( letters []rune, digits []int, mapping map[rune]int, ) (combinations int, solutions int) { if len(letters) == 0 { if v.isValidSolution(mapping) { fmt.Printf("Found %v\n", v.solutionString(mapping)) return 1, 1 // one solution tried, one solution found } return 1, 0 // one solution tried, zero solution found } letter := letters // take the first letter combinations, solutions = 0, 0 for i, digit := range digits { // try all digits for the letter "letter" mapping[letter] = digit c, s := v.recursiveSolve(letters[1:], withoutItem(digits, i), mapping) combinations += c solutions += s } delete(mapping, letter) // backtrack return }``````

The algorithm check first we all letters are assigned to a digit (line 73). If this is the case, we check if the current mapping is valid (line 74) we display the solution.

If we still have unassigned letters, we assigned all remaining digits to the first unassigned letter (lines 80–83) and we call the function recursively (line 84). Then we update the statistics (lines 85–86). Finally, we “backtrack” by removing the handled letter.

Checking if a solution is easy and we re-use our function `verbToInt`:

 ``````54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 `````` ``````func (v verbalSum) isValidSolution(mapping map[rune]int) bool { sum := 0 for _, arg := range v.operands { n := verbToInt(arg, mapping) if n < 0 { return false } sum += n } n := verbToInt(v.result, mapping) if n < 0 { return false } return sum == n }``````

When we iterate over the digits, we actually need to remove the current digit from the set before we go deeper in the recursion. We could have implemented the digits as a set (using `map[int]bool`), but we decided to rather use slices here. So here is a function that removes the ith element of a slice of integers:

 ``````27 28 29 30 31 32 `````` ``````func withoutItem(list []int, i int) []int { res := make([]int, 0, len(list)-1) res = append(res, list[:i]...) res = append(res, list[i+1:]...) return res }``````

## The rest of the program

The recursive algorithm is called from the `solve` method. This method collect all letters from the puzzle and prepares the list of digits. At the end, the method prints the statistical information.

 ``````92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 `````` ``````func (v verbalSum) solve() error { fmt.Printf("Solving %v\n", v) // Build a letters array with all letter from all operands and from the result letters := v.allLetters() // Build a numbers array with all digits from 0 to 9 digits := make([]int, 10) for i := 0; i < 10; i++ { digits[i] = i } if len(letters) > len(digits) { return errors.Errorf("Too many letters") } mapping := make(map[rune]int) count, sols := v.recursiveSolve(letters, digits, mapping) fmt.Printf("I tried %v combinations\n", count) fmt.Printf("I found %v solution(s)\n", sols) return nil }``````

To collect all letters, we use a set and add all characters of the puzzle. Go does not have set, but we can simulate a set with a map (`map[rune]bool`):

 ``````34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 `````` ``````func (v verbalSum) allLetters() []rune { letterSet := make(map[rune]bool) for _, arg := range v.operands { for _, l := range arg { letterSet[l] = true } } for _, l := range v.result { letterSet[l] = true } letters := make([]rune, len(letterSet)) i := 0 // The order of the letters is not deterministic, but it doesn't matter for k := range letterSet { letters[i] = k i++ } return letters }``````

Finally, here is the main function that solves the puzzle:

 ``````126 127 128 129 130 131 132 133 134 135 136 `````` ``````func main() { challenge := verbalSum{ operands: []string{"SEND", "MORE"}, result: "MONEY", } err := challenge.solve() if err != nil { fmt.Printf("Error: %v", err) } }``````

## Output

``````Solving SEND + MORE = MONEY
Found   9567 + 1085 = 10652
I tried 1814400 combinations
I found 1 solution(s)
``````

## Conclusion

The solution presented here is elegant and efficient. A modern notebook finds the solution of this puzzle is a little more than 500ms. A a future work, we could implement a multi-thread solution based on the workers models and see if we can do better.

The complete code is available in github.