## SEND + MORE = MONEY?

Monday, June 1, 2015

There’s a classic verbal arithmetic puzzle that was published in 1924 by Henry Dudeney, where you solve the equation:

```
S E N D
+ M O R E
-----------
= M O N E Y
```

Note: Each letter is a unique digit and`S`

and`M`

can’t be zero.

A few days ago, I noticed a blog post with solutions in Perl
6 that
references another blog post with a solution in
Haskell. I
thought I’d show a solution in Factor using the
backtrack
vocabulary that provides something like John McCarthy’s `amb`

ambiguous
operator.

First, we need a list of available digits, just the numbers 0 through 9:

```
CONSTANT: digits { 0 1 2 3 4 5 6 7 8 9 }
```

Next, we turn a sequence of digits into a number (e.g., `{ 1 2 3 4 }`

becomes `1234`

):

```
: >number ( seq -- n ) 0 [ [ 10 * ] dip + ] reduce ;
```

We can then implement our solver, by choosing digits while progressively restricting the possible values for future digits using the ones we’ve chosen so far (using local variables to store the digits):

```
:: send-more-money ( -- )
[
digits { 0 } diff amb-lazy :> s
digits { s } diff amb-lazy :> e
digits { s e } diff amb-lazy :> n
digits { s e n } diff amb-lazy :> d
{ s e n d } >number :> send
digits { 0 s e n d } diff amb-lazy :> m
digits { s e n d m } diff amb-lazy :> o
digits { s e n d m o } diff amb-lazy :> r
{ m o r e } >number :> more
digits { s e n d m o r } diff amb-lazy :> y
{ m o n e y } >number :> money
send more + money = [
send more money " %s\n+ %s\n= %s\n" printf
] when
] amb-all ;
```

Note: We search all solutions using amb-all (even though there is only one). In this case, it is effectively an iterative search, which we could implement without backtracking. If we wanted the first solution, we could use if-amb.

So, what’s the answer? Let’s see!

```
IN: scratchpad send-more-money
9567
+ 1085
= 10652
```

Neat! And it’s fast too – solving this puzzle in about 2.5 seconds on my laptop.

The code for this is on my GitHub.