Skip to content

Alphametics

Solve a letter-sum puzzle such as SEND + MORE == MONEY: give each letter a different digit so the sum is true, with no word of more than one letter starting with zero.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: alphametics.nomi
//# Solves alphametics puzzles such as `SEND + MORE == MONEY`, where each
//# letter stands for a different digit.

/// A letter of the puzzle and what it adds to the sum: `weight` is the
/// total of its place values, positive in the addends and negative in the
/// result, so a solution makes the weighted digits add up to zero.
struct Letter
    name:    String
    weight:  Int
    leading: Bool
end

/// The digit of each letter that makes `puzzle`, written as
/// `"SEND + MORE == MONEY"`, a true sum, with a different digit for each
/// letter and no leading zero in a word of more than one letter; `None`
/// when no digits do.
pub fn solve(puzzle: String) -> Maybe<Map<String, Int>>
    [left, right] = String.split(puzzle, "==") else return None

    addends = left |> String.split("+") |> Iter.map(fn word -> (String.trim(word), 1))

    letters =
        [..addends, (String.trim(right), -1)]
        |> Iter.flat_map(fn (word, sign) -> places(word, sign))
        |> Iter.group_by(.first)
        |> Iter.map(fn (name, uses) -> letter(name, uses))
        |> Iter.sort_by(.Descending, fn letter -> Int.abs(letter.weight))

    assign(letters, [], 0, {})
end

/// Each letter of `word` with its place value times `sign`, and whether it
/// leads a word of more than one letter.
fn places(word: String, sign: Int) -> List<(String, Int, Bool)>
    last = String.length(word) - 1

    word
    |> Iter.reverse()
    |> Iter.with_index()
    |> Iter.map(fn (place, name) ->
        (name, sign * Int.pow(10, place), place == last and last > 0)
    end)
    |> Iter.to_list()
end

fn letter(name: String, uses: List<(String, Int, Bool)>) -> Letter
    {
        name:,
        weight:  uses |> Iter.map(fn (_name, value, _leading) -> value) |> Iter.sum(),
        leading: Iter.any_match(uses, fn (_name, _value, leading) -> leading),
    }
end

/// Gives each of `letters` an unused digit in turn, keeping the weighted
/// `total` of the digits given so far, and backs out of a digit after which
/// the letters left cannot bring the total back to zero. The letters come
/// heaviest first, so the digits that move the total most are fixed first
/// and the bound cuts early.
fn assign(
    letters: List<Letter>,
    used:    Set<Int>,
    total:   Int,
    digits:  Map<String, Int>,
) -> Maybe<Map<String, Int>>
    [letter, ..rest] = letters else
        return if total == 0 then Some(digits) else None
    end

    0..=9
    |> Iter.filter(fn digit ->
        not digit in used and not (letter.leading and digit == 0)
    end)
    |> Iter.map(fn digit -> (digit, total + letter.weight * digit))
    |> Iter.filter(fn (_digit, after) -> is_reachable(after, rest))
    |> Iter.find_map(fn (digit, after) ->
        assign(rest, Set.insert(used, digit), after, Map.put(digits, letter.name, digit))
    end)
end

/// Whether the letters `rest` could still bring `total` to zero: each adds
/// at most nine times its weight when the weight is positive, and takes
/// away at most nine times its size when it is negative.
fn is_reachable(total: Int, rest: List<Letter>) -> Bool
    weights = Iter.map(rest, .weight)
    gains = weights |> Iter.filter(&(&1 > 0)) |> Iter.sum()
    losses = weights |> Iter.filter(&(&1 < 0)) |> Iter.sum()
    total + 9 * losses <= 0 and 0 <= total + 9 * gains
end

// FILE: alphametics_test.nomi
import alphametics

test "solve"
    [
        ("puzzle with three letters", "I + BB == ILL", Some({"I" => 1, "B" => 9, "L" => 0})),
        ("solution must have unique value for each letter", "A == B", None),
        ("leading zero solution is invalid", "ACA + DD == BD", None),
        (
            "puzzle with two digits final carry",
            "A + A + A + A + A + A + A + A + A + A + A + B == BCC",
            Some({"A" => 9, "B" => 1, "C" => 0}),
        ),
        (
            "puzzle with four letters",
            "AS + A == MOM",
            Some({"A" => 9, "S" => 2, "M" => 1, "O" => 0}),
        ),
        (
            "puzzle with six letters",
            "NO + NO + TOO == LATE",
            Some({"N" => 7, "O" => 4, "T" => 9, "L" => 1, "A" => 0, "E" => 2}),
        ),
        (
            "puzzle with seven letters",
            "HE + SEES + THE == LIGHT",
            Some({"E" => 4, "G" => 2, "H" => 5, "I" => 0, "L" => 1, "S" => 9, "T" => 7}),
        ),
        (
            "puzzle with eight letters",
            "SEND + MORE == MONEY",
            Some({"S" => 9, "E" => 5, "N" => 6, "D" => 7, "M" => 1, "O" => 0, "R" => 8, "Y" => 2}),
        ),
        (
            "puzzle with ten letters",
            "AND + A + STRONG + OFFENSE + AS + A + GOOD == DEFENSE",
            Some(
                {
                    "A" => 5,
                    "D" => 3,
                    "E" => 4,
                    "F" => 7,
                    "G" => 8,
                    "N" => 0,
                    "O" => 2,
                    "R" => 1,
                    "S" => 6,
                    "T" => 9,
                }
            ),
        ),
        (
            "puzzle with ten letters and 199 addends",
            "THIS + A + FIRE + THEREFORE + FOR + ALL + HISTORIES + I + TELL + A + TALE + THAT + FALSIFIES + ITS + TITLE + TIS + A + LIE + THE + TALE + OF + THE + LAST + FIRE + HORSES + LATE + AFTER + THE + FIRST + FATHERS + FORESEE + THE + HORRORS + THE + LAST + FREE + TROLL + TERRIFIES + THE + HORSES + OF + FIRE + THE + TROLL + RESTS + AT + THE + HOLE + OF + LOSSES + IT + IS + THERE + THAT + SHE + STORES + ROLES + OF + LEATHERS + AFTER + SHE + SATISFIES + HER + HATE + OFF + THOSE + FEARS + A + TASTE + RISES + AS + SHE + HEARS + THE + LEAST + FAR + HORSE + THOSE + FAST + HORSES + THAT + FIRST + HEAR + THE + TROLL + FLEE + OFF + TO + THE + FOREST + THE + HORSES + THAT + ALERTS + RAISE + THE + STARES + OF + THE + OTHERS + AS + THE + TROLL + ASSAILS + AT + THE + TOTAL + SHIFT + HER + TEETH + TEAR + HOOF + OFF + TORSO + AS + THE + LAST + HORSE + FORFEITS + ITS + LIFE + THE + FIRST + FATHERS + HEAR + OF + THE + HORRORS + THEIR + FEARS + THAT + THE + FIRES + FOR + THEIR + FEASTS + ARREST + AS + THE + FIRST + FATHERS + RESETTLE + THE + LAST + OF + THE + FIRE + HORSES + THE + LAST + TROLL + HARASSES + THE + FOREST + HEART + FREE + AT + LAST + OF + THE + LAST + TROLL + ALL + OFFER + THEIR + FIRE + HEAT + TO + THE + ASSISTERS + FAR + OFF + THE + TROLL + FASTS + ITS + LIFE + SHORTER + AS + STARS + RISE + THE + HORSES + REST + SAFE + AFTER + ALL + SHARE + HOT + FISH + AS + THEIR + AFFILIATES + TAILOR + A + ROOFS + FOR + THEIR + SAFE == FORTRESSES",
            Some(
                {
                    "A" => 1,
                    "E" => 0,
                    "F" => 5,
                    "H" => 8,
                    "I" => 7,
                    "L" => 2,
                    "O" => 6,
                    "R" => 3,
                    "S" => 4,
                    "T" => 9,
                }
            ),
        ),
    ]
    |> subtests (description, puzzle, expected), description
        assert alphametics.solve(puzzle) == expected
    end
end
  • solve returns Maybe<Map<String, Int>>, each letter’s digit or None, as the canonical data maps letters to digits or gives null.
  • The puzzle becomes one equation. Each letter’s weight is the sum of its place values, positive in the addends and negative in the result (S in SEND + MORE == MONEY weighs 1000, M 1000 - 10000), so a solution is digits whose weighted sum is zero. The 199 addends of the largest case fold into ten weights before the search starts, and the search never reads the words again.
  • The search is a depth-first backtrack over the letters, heaviest first. After each digit, is_reachable checks that the letters left could still bring the total back to zero, at most nine times each positive weight up and nine times each negative weight down, and the search backs out when they cannot. Taking the heavy letters first makes that bound cut early: the 199-addend case visits about 2,800 assignments and runs in about 30 ms on the VM. An earlier version took the letters by their lowest column and checked the total modulo that column’s place value, as a column-by-column solver does; in the 199-addend puzzle all ten letters end some word, so every letter sits in the units column, it could not prune until the last letter, and it took 4.7 seconds.
  • A letter that leads a word of more than one letter is marked leading and never gets 0.
  • places lists each letter of a word with its place value, from Iter.reverse and Iter.with_index, and Iter.group_by gathers a letter’s uses into one Letter.
  • The ten canonical cases are one subtests table named by the description column.