Don’t keep reading unless you want a fun puzzle spoiled.

I found the latest SMBC bonus panel to be a fascinating puzzle. From the comic it’s obvious that this is going to be a cryptogram with hamming distances. So my first step was clustering everything together to try and find common clusters.

This did not go so well: you don’t end up with enough connected components to start trying to assign letters. Then I went back and reread the comic: turns out they gift us some letters: “a” through “e”, “n”, “y”, and “h”, “u”, “k”.

With this we’re in business: we maintain two mappings of codes to letters:

  • known: These must be correct: everything within hamming distance 1 gets assigned this letter
  • assumed: These are only presumed correct: exact matches are assigned this letter and everything within hamming distance 1 could possibly be assigned this letter

We start only with the known letters from the comic and start solving our cryptogram

function solve(input, known, assumed)
    elements = split(input, " ")
    n = length(elements)

    results = fill("?", n)
    guesses = fill("", n)

    for ii in 1:n
        for (code, letter) in known
            if hamming(elements[ii], code) <= 1
                results[ii] = letter
            end
        end
        for (code, letter) in assumed
            if hamming(elements[ii], code) == 0
                results[ii] = letter
            end
            if hamming(elements[ii], code) == 1
                guesses[ii] = "$(guesses[ii])$letter"
            end
    end

    end

    for (char, guess, base) in zip(results, guesses, elements)
        println("$char ($guess): $base")
    end

    return join(results)
end

For instance when we start out we get “?he?beau?y?????a?he?a??c???n?y??h?w?????e?????????e?pa??en???????we??”.

It’s pretty clear that we have the word “beauty” in there so we add the code “001100001” => t to our assumed list.

This then gets us “?he?beauty?????athe?a??c???n?y??h???????e?????????e??a??en????????e??” and now we start seeing the starts of “mathematics” in there so we assign more and more.

We can get fairly far just with the assignments but it’s also nice to transfer some of our assumptions into known codes. Fortunately we can use the Hamming distance constraints to achieve this:

function reduce_hamming1(common_elements, disjoint_elements=[],
    known=[]) base = collect(common_elements[1])

    candidates = []
    for ii in 1:9
        new = copy(base)
        new[ii] = new[ii] == '0' ? '1' : '0'
        push!(candidates, join(new))
    end

    for el in common_elements[2:end]
        filter!(x -> hamming(x, el) <= 1, candidates)
    end

    for el in disjoint_elements
        filter!(x -> hamming(x, el) > 1, candidates)
    end

    for el in known
        filter!(x -> hamming(x, el) >= 2, candidates)
    end

    return candidates
end

We can patiently continue on this path making more assumptions and filling in letters until finally the entire solution shows itself!

Final Solution Code

input = "011100101 011111111 110100110 101111010 100010011 010101110 000000000 010011010 001100001 100110001 101111011 011100001 010110111 001111011 111101011 100000000 001100001 011111111 110100110 110101011 000000010 001100100 100001101 001001010 001110111 101111010 111100001 110111000 101010100 100110101 001111011 001110110 011111111 111100001 011010010 001110110 101110011 100001101 001100101 001110110 010101110 111010100 010110101 101110011 001100101 111100000 101111011 110101011 111100001 000101111 010100110 101111011 111110000 000000000 001100100 100001111 011100110 010111000 001101101 101111011 010110101 111100001 111010100 101010100 111100001 111010000 010100110 000101110 001110110"

known = Dict("000000000" => "a",
             "000010011" => "b",
             "001001010" => "c",
             "001011001" => "d",
             "010100110" => "e",
             "110111000" => "n",
             "100110001" => "y",
             "011111111" => "h",
             "010011010" => "u",
             "101000111" => "k",
             "001100101" => "t", # reduce_hamming1(["011100101", "001100001", "001100100"])
             "101111011" => "_", # reduce_hamming1(["101111010", "101111011"])
             "110101011" => "m", # reduce_hamming1(["111101011", "110101011"])
             "100001111" => "i", # reduce_hamming1(["100001101", "100001111"])
             "001110110" => "s", # reduce_hamming1(["001110111", "001110110"])
             "111100001" => "o", # reduce_hamming1(["011100001", "111100000", "111100001"])
             "010110111" => "f", # reduce_hamming1(["010110101", "010110111"])
             "111010100" => "l", # reduce_hamming1(["101010100", "111010100"])
             "000101111" => "r", # reduce_hamming1(["000101110", "000101111"])
)

assumed = Dict(
    "111110000" => "p",
    "011010010" => "w",
    "111010000" => "w",
)

hamming(xx, yy) = count(map(!=, xx, yy))

function reduce_hamming1(common_elements, disjoint_elements=[], known=[])
    base = collect(common_elements[1])

    candidates = []
    for ii in 1:9
        new = copy(base)
        new[ii] = new[ii] == '0' ? '1' : '0'
        push!(candidates, join(new))
    end

    for el in common_elements[2:end]
        filter!(x -> hamming(x, el) <= 1, candidates)
    end

    for el in disjoint_elements
        filter!(x -> hamming(x, el) > 1, candidates)
    end

    for el in known
        filter!(x -> hamming(x, el) >= 2, candidates)
    end

    return candidates
end

function solve(input, known, assumed)
    elements = split(input, " ")
    n = length(elements)

    results = fill("?", n)
    guesses = fill("", n)

    for ii in 1:n
        for (code, letter) in known
            if hamming(elements[ii], code) <= 1
                results[ii] = letter
            end
        end
        for (code, letter) in assumed
            if hamming(elements[ii], code) == 0
                results[ii] = letter
            end
            if hamming(elements[ii], code) == 1
                guesses[ii] = "$(guesses[ii])$letter"
            end
    end

    end

    for (char, guess, base) in zip(results, guesses, elements)
        println("$char ($guess): $base")
    end

    return join(results)
end

print(solve(input, known, assumed))