Smudged secret messages

Original problem source: Riddler, June 8, 2018. Solutions by Laurent Lessard


First problem:

  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.

Solution 1: brute force

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.

In [104]:
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

Solution 2: integer programming

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!

In [129]:
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]

Second problem:

  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.

Solution: integer programming

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.

In [132]:
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:

  • change the 4 to a 6 (i.e. the K should have been a Y)
  • change the 3 to a 5 (i.e. the D should have been a B)
  • change the 9 to a 7 (i.e. the T should have been an H)