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
endok solve (10 cases)
test result: ok. 10 passed, 0 failed
How it’s written
Section titled “How it’s written”solvereturnsMaybe<Map<String, Int>>, each letter’s digit orNone, as the canonical data maps letters to digits or givesnull.- The puzzle becomes one equation. Each letter’s
weightis the sum of its place values, positive in the addends and negative in the result (SinSEND + MORE == MONEYweighs 1000,M1000 - 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_reachablechecks 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
leadingand never gets 0. placeslists each letter of a word with its place value, fromIter.reverseandIter.with_index, andIter.group_bygathers a letter’s uses into oneLetter.- The ten canonical cases are one
subteststable named by the description column.