I was given a puzzle to solve recently. The puzzles is a cryptarithmetic problem: 5’s twelve + thirty = ninety.

T W E L V E
T W E L V E
T W E L V E
T W E L V E
T W E L V E
T H I R T Y
————
N I N E T Y

Each letter represents a unique number from 0 to 9.

As a software engineer, I naturally wanted to solve this problem by writing a program, and I decided to use F#, in functional way.

Here is the code I wrote:

open System

let digits = [0..9] |> Set.ofList

let remainingDigits removedDigits =
    Set.difference digits (Set.ofList removedDigits)

let toNumber digits =
    digits |> List.fold (fun number i -> number * 10 + i) 0

type PuzzleSolver() =
    member this.Bind(xs, f) =
        xs
        |> Set.map (fun x -> f(x))
        |> Set.filter (fun x -> x |> List.isEmpty |> not)
        |> Set.toList
        |> List.concat

    member this.Return(x) = [x]
    member this.ReturnFrom(x) = x

let solver = PuzzleSolver()

let solutions = solver {
    let! t = remainingDigits [0]
    let! w = remainingDigits [t]
    let! e = remainingDigits [t; w]
    let! l = remainingDigits [t; w; e]
    let! v = remainingDigits [t; w; e; l]
    let! h = remainingDigits [t; w; e; l; v]
    let! i = remainingDigits [t; w; e; l; v; h]
    let! r = remainingDigits [t; w; e; l; v; h; i]
    let! y = remainingDigits [t; w; e; l; v; h; i; r]
    let! n = remainingDigits [t; w; e; l; v; h; i; r; y]

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        return! [ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v); 
                  ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ]
    else return! []
}

solutions |> List.iter (fun (l, v) -> printfn "%s = %d" l v)

And the following is the result copied from the F# Interactive console of Visual Studio:

T = 1
W = 3
E = 0
L = 7
V = 6
H = 9
I = 4
R = 2
Y = 5
N = 8

val digits : Set<int> = set [0; 1; 2; 3; 4; 5; 6; 7; 8; ...]
val remainingDigits : removedDigits:int list -> Set<int>
val toNumber : digits:int list -> int
type PuzzleSolver =
    class
        new : unit -> PuzzleSolver
        member
            Bind : xs:Set<'c> * f:('c -> 'd list) -> 'd list
                when 'c : comparison and 'd : comparison
        member Return : x:'b -> 'b list
        member ReturnFrom : x:'a -> 'a
end

val solver : PuzzleSolver

val solutions : (string * int) list =
[("T", 1); ("W", 3); ("E", 0); ("L", 7); ("V", 6); ("H", 9); ("I", 4);
("R", 2); ("Y", 5); ("N", 8)]
val it : unit = ()

Let’s look at the F# code. The digits value is a set of 10 integers from 0 to 9. The remainingDigits function removes the given integers from the digits set and returns the remaining digits. The toNumber function converts the given digits to an integer.

At the heart of the algorithm is the PuzzleSolver computation expression. The Bind method takes a Set and a function that maps a value to a list, and returns a list.

member this.Bind(xs, f) =
    xs
    |> Set.map (fun x -> f(x))
    |> Set.filter (fun x -> x |> List.isEmpty |> not)
    |> Set.toList
    |> List.concat

The Bind() method pipes the given set to the Set.map function to create a set of list by mapping each element in the set to a list by calling the f function passed in. It then pipes the set of lists to Set.filter to create a new set by removing all empty lists. The new set of lists is then converted to a list of lists, which is passed to List.concat to flatten to a list.

The Return method just wraps the given value as a list. And the ReturnFrom method just returns the given value.

With the PuzzleSolver computation expression, we can solve the puzzle with following code:

let solutions = solver {
    let! t = remainingDigits [0]
    let! w = remainingDigits [t]
    let! e = remainingDigits [t; w]
    let! l = remainingDigits [t; w; e]
    let! v = remainingDigits [t; w; e; l]
    let! h = remainingDigits [t; w; e; l; v]
    let! i = remainingDigits [t; w; e; l; v; h]
    let! r = remainingDigits [t; w; e; l; v; h; i]
    let! y = remainingDigits [t; w; e; l; v; h; i; r]
    let! n = remainingDigits [t; w; e; l; v; h; i; r; y]

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        return! [ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v);
                  ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ]
    else return! []
}

The code essentially says that:

Let the identifier t be one of the digits from 1 to 9,

Let the identifier w be one of the digits from 0 to 9 except for t,

…

We bind each of the 10 identifiers to a different digit, we then calculate the values of TWELVE, THIRTY, and NINETY, if the 3 values meet the condition, which is TWELVE * 5 + THIRTY = NINETY, we return a list of pairs of a letter and the digit it represents, otherwise, an empty list is returned.

The let! Expression is just a syntax sugar for the Bind method. So

let! t = remainingDigits [0]

is essentially translated into

solver.Bind(remainingDigits [0], (fun t -> …) )

And the whole solutions expression is translated into nested method calls to the solver.Bind() method:

let solutions =
    solver.Bind(remainingDigits [0], fun t ->
    solver.Bind(remainingDigits [t], fun w ->
    solver.Bind(remainingDigits [t; w], fun e ->
    solver.Bind(remainingDigits [t; w; e], fun l ->
    solver.Bind(remainingDigits [t; w; e; l], fun v ->
    solver.Bind(remainingDigits [t; w; e; l; v], fun h ->
    solver.Bind(remainingDigits [t; w; e; l; v; h], fun i ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i], fun r ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i; r], fun y ->
    solver.Bind(remainingDigits [t; w; e; l; v; h; i; r; y], fun n ->

    let TWELVE = toNumber [t; w; e; l; v; e]
    let THIRTY = toNumber [t; h; i; r; t; y]
    let NINETY = toNumber [n; i; n; e; t; y]

    if (TWELVE * 5 + THIRTY = NINETY) then
        solver.ReturnFrom([ ("T", t); ("W", w); ("E", e); ("L", l); ("V", v);
                            ("H", h); ("I", i); ("R", r); ("Y", y); ("N", n) ])
    else solver.ReturnFrom([])
))))))))))

This is not too difficult to understand compared to the nested for loops if we were to solve it in imperative way.

let solutions2 =
    for t in (remainingDigits [0]) do
    for w in (remainingDigits [t]) do
    for e in (remainingDigits [t; w]) do
    for l in (remainingDigits [t; w; e]) do
    for v in (remainingDigits [t; w; e; l]) do
    for h in (remainingDigits [t; w; e; l; v]) do
    for i in (remainingDigits [t; w; e; l; v; h]) do
    for r in (remainingDigits [t; w; e; l; v; h; i]) do
    for y in (remainingDigits [t; w; e; l; v; h; i; r]) do
    for n in (remainingDigits [t; w; e; l; v; h; i; r; y]) do

        let TWELVE = toNumber [t;w;e;l;v;e]
        let THIRTY = toNumber [t;h;i;r;t;y]
        let NINETY = toNumber [n;i;n;e;t;y]

        if (TWELVE * 5 + THIRTY = NINETY) then
            printfn "TWELVE=%d, THIRTY=%d, NINETY=%d" TWELVE THIRTY NINETY