Brute force solver for alphametics

alphametics.jl

# See also https://github.com/exercism/julia/blob/3e57ea81abbff1882b263eb414fb0e453b07a17e/exercises/practice/alphametics/.meta/example.jl

using Combinatorics: permutations

using Test

function sum_expr(exprs)
    if length(exprs) == 1
        return only(exprs)
    else
        return Expr(:call, :+, exprs...)
    end
end

function parse_word(word)
    multiplier = 10 ^ (length(word) - 1)
    exprs = []
    for l in word
        if multiplier == 1
            push!(exprs, Symbol(l))
        else
            push!(exprs, Expr(:call, :*, multiplier, Symbol(l)))
            multiplier ÷= 10
        end
    end
    sum_expr(exprs)
end

@test parse_word("A") == :(A)
@test parse_word("AA") == :(10A + A)

function parse_puzzle(puzzle::String)
    lhs = []
    rhs = []
    acc = lhs
    for token in split(puzzle)
        if token == "=="
            acc = rhs
        elseif token != "+"
            push!(acc, parse_word(token))
        end
    end
    Expr(:call, :(==), sum_expr(lhs), sum_expr(rhs))
end

@test parse_puzzle("A == B") == :(A == B)
@test parse_puzzle("AB == BA") == :(10A + B == 10B + A)
@test parse_puzzle("SEND + MORE == MONEY") == :((1000S + 100 * E + 10N + D) + (1000M + 100O + 10R + E) == 10000M + 1000O + 100N + 10E + Y)

function leading_letters(puzzle)
    unique(first.(split(puzzle, r"[^A-Z]+")))
end

@test leading_letters("SEND + MORE == MONEY") == ['S', 'M']

letters(puzzle) = unique(c for c in puzzle if c in 'A':'Z')

@test letters("ABC + CDE = FG") == ['A', 'B', 'C', 'D', 'E', 'F', 'G']

function validator_expr(puzzle)
    vars = Symbol.(letters(puzzle))
    leading_vars = Symbol.(leading_letters(puzzle))
    quote
        function(vs)
            $(Expr(:tuple, vars...)) = vs
            $((:($L == 0 && return false) for L in leading_vars)...)
            # We'll only be calling the validator with permutations, so
            # we don't need to check this.
            # allunique(vs) || return false
            return $(parse_puzzle(puzzle))
        end
    end
end

get_validator(puzzle) = eval(validator_expr(puzzle))

@test get_validator("A + B == C")([1, 2, 3])
@test get_validator("A + A + B == AA")([1, 9])

"""
    solve(puzzle::String)

Return a Dict mapping each letter in the puzzle to an integer in 0:9.

Words cannot start with 0.
No two letters can share the same value.
"""
function solve(puzzle::String)
    is_valid = get_validator(puzzle)
    vars = letters(puzzle)
    # Need to use invokelatest here because the function `is_valid` doesn't
    # exist at the time `solve` or `do_solve` are compiled.
    # There might be a better/faster way to do this, but I don't know it.
    Base.invokelatest(do_solve, vars, is_valid)
end

function do_solve(vars, is_valid)
    for p in permutations(0:9, length(vars))
        if is_valid(p)
            return Dict(vars .=> p)
        end
    end
    error("No solution!")
end

@time solve("A + B == C") # 0.06s
@time solve("A + A + B == AA") # 0.07s
@time solve("SEND + MORE == MONEY") # 0.3s

# 10 character alphametic, but quite an easy one (many valid solutions)
@time solve("A + B + C + D + E + F + G + H + I + AJ == EE") # 0.1s

# Harder 9 character alphametic
# British Informatics Olympiad exam 1998, Q3
# https://www.olympiad.org.uk/papers/1998/bio/bio98r1s3.html
@time solve("THREE + THREE + TWO + TWO + ONE == ELEVEN") # 0.6s, 10M allocations 1 GiB

# Much of the time and most of the allocations are from permutations()
# An in-place variant would probably speed this up
@time foreach(identity, permutations(0:9, 9)) # 0.6s, 11M allocations, 1.1 GiB