Re: Factor

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.