True Story Follows
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:
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:
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:
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.