## Monday, June 1, 2015

### SEND + MORE = MONEY?

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.