Last active
November 15, 2021 10:57
-
-
Save cmcaine/2a056d6b8926e0ae033fe041c5d5aec7 to your computer and use it in GitHub Desktop.
Brute force solver for alphametics
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment