Brute Force for the Win! Sort Of. Just give me like 55 years.

True Story Follows

I’m in my house, bro’ing out. My wife is watching the Christmas special of Downton Abbey, 2 hour special. So naturally I go on Twitter and get slapped in the face by a gauntlet with this:
Screen Shot 2014-12-27 at 9.49.04 PM

So I checked out the problem on the internets at RealMode.com. My eyes glazed over reading the problem and I almost gave up right there and then. The short story of the problem is this:

Generate 7 bit representations of the capital letters A-Z where each character can be represented by two different 7 bit bytes. In this way, you should be able to overwrite any character to get to a different state of any other character by overwriting just 1 bit.

Solving the Problem

Here’s the spoiler alert: I solved the problem. Sort of. I think. We’ll see. Essentially (or at least as far as I can tell) this boils down to a brute force problem, but the number of combinations to try is insanely large. Before explaining any more, you can see my solution:

import math

# for every letter in the alphabet, find 2 unique 7 bit representations for it
# where every other letter in the alphabet has a 2nd state that can be reached
# from the 1st combination

# http://realmode.com/


def generate_possible_bit_arrays():
    possibles = []
    base = (False, False, False, False, False, False, False)
    for value in xrange(64):
        bit_val = 64
        temp_byte = list(base)
        while bit_val >= 2:
            bit_val /= 2
            if value >= bit_val:
                value -= bit_val
                index = bit_val and int(math.log(bit_val, 2))
                temp_byte[index] = True
        possibles.append(tuple(temp_byte))
    return possibles


def can_transition(source_byte_array, dest_byte_array):
    for index, value in enumerate(dest_byte_array):
        if not value and source_byte_array[index]:
            return False
    return True


def binomial(n, k):
    c = [0] * (n + 1)
    c[0] = 1
    for i in range(1, n + 1):
        c[i] = 1
        j = i - 1
        while j > 0:
            c[j] += c[j - 1]
            j -= 1
    return c[k]


def generate_index_combinations(n, k, callback_for_indexes):

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            callback_for_indexes(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)


if __name__ == "__main__":
    byte_combos = generate_possible_bit_arrays()
    print binomial(64, 52)

    def attempt_7bit_encoding(indexes_to_try):
        non_overwrite_symbol_indexes = indexes_to_try[:26]
        overwrite_symbol_indexes = indexes_to_try[26:]

        combination_works = True
        for source_index in non_overwrite_symbol_indexes:
            for dest_index in overwrite_symbol_indexes:
                if not can_transition(byte_combos[source_index], byte_combos[dest_index]):
                    combination_works = False
        if combination_works:
            print "HEY THIS COMBO WORKS!"
            print indexes_to_try

    combos = generate_index_combinations(64, 26 + 26, attempt_7bit_encoding)

My idea is essentially this: what characters map to which byte combination is irrelevant. We just need to have 26 byte combinations that can each successfully map to 26 other unique byte combinations. From there the characters they represent can be arbitrary. So all I did was generate all possible byte combinations, then iterate over all possible index combinations in chunks of 52 (26 + 26 letters of the alphabet) of the 64 possible byte combinations and see if the rules passed. The problem is that there are 3,284,214,703,056 possible combinations unless I’m wrong, which I’m not. That numbers is from N choose K for N=64 and K=52 (64 is the number of permutations for 7 bits, 52 is the number of character representations we need).

As kind of an aside, getting all of the possible index combinations is a classic N choose K style problem, so I wrote a nifty recursive function that can be generically applied (let’s say, for instance, when you’re at the pizza shop and you can choose 3 of any 10 different toppings, and you want to know and list all of the 120 possible pizzas that can be created). Here’s the function:

def generate_index_combinations(n, k, callback_for_indexes):

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            callback_for_indexes(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)

Rather than deal with inevitable memory pressure as you append trillions of items onto a list, I instead just took a callback function as a parameter that gets called with an index combination. You can verify that the function is correct with a corresponding function that outputs the number of possible combinations for N choose K:

def binomial(n, k):
    c = [0] * (n + 1)
    c[0] = 1
    for i in range(1, n + 1):
        c[i] = 1
        j = i - 1
        while j > 0:
            c[j] += c[j - 1]
            j -= 1
    return c[k]

So anyway, I timed the brute force matching to see how long it takes to try one iteration of a combination. That ended up being 0.000536 seconds. And I need to try 3284214703056 combinations max. That comes out to 55 years. Dang. But hey, maybe I’ll get lucky and it’ll short circuit in a few minutes.

I’ll take another gander at the problem and see if there are other ways to constrain the problem and short circuit it. One probably crucial detail that I didn’t mention was that for a given character, you didn’t need to worry about mapping to its second representation (because for example, there’s no reason to overwrite ‘A’ with ‘A’).

Anyway, it’s an interesting problem. And when I solve it, I will get so many high fives.