E X M R E E K
+ E H K R E K K
---------------
A K B H C X D E
In the original problem, the letters A, B, C, D were horizontal dashes (--). I replaced them with letters instead. This is fine because we know all digits 0 through 9 must appear, and there are only 6 other letters. This forces all four "smudges" to be different numbers. I solve the problem in two different ways.
In this solution, I simply loop through all possible assignments of letters to numbers and see which one works. Trying all ~3,600,000 permutations takes about 16 seconds on my laptop. Of course, we can stop once we found the answer so there is no need to iterate through all possibilities. So on average, we can expect this to take ~8 seconds.
using Combinatorics
letters = "EXMRKHABCD"
chars = [c for c in letters]
optperm = []
@time for p in permutations(0:9)
E,X,M,R,K,H,A,B,C,D = p
num1 = E*1e6 + X*1e5 + M*1e4 + R*1e3 + E*1e2 + E*1e1 + K
num2 = E*1e6 + H*1e5 + K*1e4 + R*1e3 + E*1e2 + K*1e1 + K
num3 = A*1e7 + K*1e6 + B*1e5 + H*1e4 + C*1e3 + X*1e2 + D*1e1 + E
if num1 + num2 == num3
optperm = p
# we can obviously just stop once we find a solution. I kept looping
# to see how long it would take to iterate through all permutations.
end
end
for (i,c) in enumerate(chars)
println("$(c) = $(optperm[i])")
end
16.132296 seconds (170.55 M allocations: 4.001 GiB, 6.68% gc time) E = 6 X = 2 M = 4 R = 7 K = 3 H = 8 A = 1 B = 0 C = 5 D = 9
In this solution, I model and solve the problem using integer programming. This approach only takes about 0.05 seconds, or about 160x faster than the brute-force approach. Not too bad!
using JuMP, Gurobi
m = Model(solver=GurobiSolver(OutputFlag=0))
letters = "EXMRKHABCD"
chars = [c for c in letters]
# define e.g. "Yb" a binary vector of length 10 with exactly one "1"
for c in chars
eval(parse("@variable(m, $(c)b[1:10], Bin)"))
eval(parse("@constraint(m, sum($(c)b)==1)"))
end
# constraint that each letter corresponds to a different number
@constraint(m, sum( eval(parse("$(c)b")) for c in chars ) .== ones(10,1) )
# define e.g. "Y" to be the numerical value of the variable
digs = collect(0:9)
for c in chars
eval(parse("@expression(m, $(c), digs'*$(c)b)"))
end
# define carry-overs from the addition (no carry-over on last (ones) digit)
@variable(m, carry[1:8], Bin)
@constraint(m, carry[8] == 0)
# the numbers being added together and their sum
@expression(m, num1, [0, E, X, M, R, E, E, K])
@expression(m, num2, [0, E, H, K, R, E, K, K])
@expression(m, num3, [A, K, B, H, C, X, D, E])
;
# addition constraints
for i = 1:8
if i==1
@constraint(m, carry[1] + num1[1] + num2[1] == num3[1])
else
@constraint(m, carry[i] + num1[i] + num2[i] == 10*carry[i-1] + num3[i])
end
end
# solve and print solution
status = @time solve(m)
for c in chars
val = eval(parse("Int(getvalue($(c)))"))
println("$(c) = $(val)")
end
println("carryover, summands, and sum")
if status == :Optimal
println(Array{Int,1}(getvalue(carry)))
println(Array{Int,1}(getvalue(num1)))
println(Array{Int,1}(getvalue(num2)))
println(Array{Int,1}(getvalue(num3)))
end
Academic license - for non-commercial use only 0.005093 seconds (127 allocations: 66.141 KiB) E = 6 X = 2 M = 4 R = 7 K = 3 H = 8 A = 1 B = 0 C = 5 D = 9 carryover, summands, and sum [1, 1, 0, 1, 1, 0, 0, 0] [0, 6, 2, 4, 7, 6, 6, 3] [0, 6, 8, 3, 7, 6, 3, 3] [1, 3, 0, 8, 5, 2, 9, 6]
Y T B B E D M K D
+ Y H D B T Y Y D D
-------------------
E D Y T E R T P T Y
In this variant, there is an "error" somewhere in the above sum. In other words, one of the letters is wrong. I didn't solve this variant using brute force, because it would take at least ~8 seconds (just as the first problem did). Instead, I solved the problem using integer programming only.
The key to solving this problem is to treat each "column" as a separate integer constraint. We then introduce additional binary variables that track whether the sums work out or not. Then, we minimize the number of sums that don't work out. This allows us to deduce which column contains the error. This problem is a bit more complicated than the first one (the optimization has more variables and constraints). In this case, it took about 0.3 seconds to solve on my laptop.
using JuMP, Gurobi
m = Model(solver=GurobiSolver(OutputFlag=0))
letters = "YTBEDMKHRP"
chars = [c for c in letters]
# define e.g. "Yb" a binary vector of length 10 with exactly one "1"
for c in chars
eval(parse("@variable(m, $(c)b[1:10], Bin)"))
eval(parse("@constraint(m, sum($(c)b)==1)"))
end
# constraint that each letter corresponds to a different number
@constraint(m, sum( eval(parse("$(c)b")) for c in chars ) .== ones(10,1) )
# define e.g. "Y" to be the numerical value of the variable
C = collect(0:9)
for c in chars
eval(parse("@expression(m, $(c), C'*$(c)b)"))
end
# define carry-overs from the addition (no carry-over on last (ones) digit)
@variable(m, carry[1:10], Bin)
@constraint(m, carry[10] == 0)
# a binary variable for each equation. If z[j]=1, then jth equation it's not satisfied.
@variable(m, z[1:10], Bin)
# the numbers being added together and their sum
@expression(m, num1, [0, Y, T, B, B, E, D, M, K, D])
@expression(m, num2, [0, Y, H, D, B, T, Y, Y, D, D])
@expression(m, num3, [E, D, Y, T, E, R, T, P, T, Y])
# addition constraints. When z[j]==0, it's just an equality constraint. Otherwise it's unconstrained
for i in 1:10
if i == 1
@constraint(m, -9*z[1] <= carry[1] + num1[1] + num2[1] - num3[1] )
@constraint(m, carry[1] + num1[1] + num2[1] - num3[1] <= 19*z[1] )
else
@constraint(m, -19*z[i] <= carry[i] + num1[i] + num2[i] - 10*carry[i-1] - num3[i] )
@constraint(m, carry[i] + num1[i] + num2[i] - 10*carry[i-1] - num3[i] <= 19*z[i] )
end
end
# minimize the number of incorrect additions (these correspond to errors in the digits for that sum)
@objective(m, Min, sum(z))
# solve and print solution
status = @time solve(m)
for c in chars
val = eval(parse("Int(getvalue($(c)))"))
println("$(c) = $(val)")
end
println("carryover, summands, and sum")
if status == :Optimal
println(Array{Int,1}(getvalue(carry)))
println(Array{Int,1}(getvalue(num1)))
println(Array{Int,1}(getvalue(num2)))
println(Array{Int,1}(getvalue(num3)))
println("locations of incorrect sums:")
println(Array{Int,1}(getvalue(z)))
end
Academic license - for non-commercial use only 0.305246 seconds (127 allocations: 102.688 KiB) Y = 6 T = 9 B = 5 E = 1 D = 3 M = 2 K = 4 H = 7 R = 0 P = 8 carryover, summands, and sum [1, 1, 0, 1, 1, 0, 0, 0, 0, 0] [0, 6, 9, 5, 5, 1, 3, 2, 4, 3] [0, 6, 7, 3, 5, 9, 6, 6, 3, 3] [1, 3, 6, 9, 1, 0, 9, 8, 9, 6] locations of incorrect sums: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
The error is located in the second last column: it reads "4+3=9", which is obviously incorrect. There are three different ways to fix this: