Binary Permutations

Eight bits with some bits set to one and some set to zero.

This is one of those little math puzzles that probably have some application somewhere out in the real world, but for our purposes, it's enough that it's a bit of a puzzle.

Supposed you have string of ten digits, like 0 thru 9, arranged in numerical order. Now you can mix them up and rearrange them in any order you want, and you could use the resulting string of digits as a combination or password and no one would ever guess what the correct sequence was.

Now suppose you have a string of ten binary digits. You could mix them up and rearrange them just like you did with the decimal digits, but since all one's look alike and all zero's look alike, there wouldn't be nearly as many possibilites. You could still use it for a password, but if someone was determined and diligent they could eventually figure out what the correct sequence was. Of course, it helps if you use a mix of one's and zero's. A password of all one's isn't much of a password at all.

Now imagine that someone has made up a rule for where the digits go. If they like you well enough, they tell you what the rule is. Then when you want access to their secret hideout, they give you a mixed up string of binary digits (one's and zero's) and you have to rearrange them according to the rule.

But they don't like you, or maybe they like you, but they don't trust you, so they don't tell you what the rule is. So the question is, given a handful of examples of pairs of binary numbers, can you decipher the rule?

I spent some time working on this puzzle a few months ago, but I wasn't able to come up with a program that could correctly decipher all of the test cases. It got most of them, but not all. Yesterday I picked it up again and fiddled with it for a bit, but I wasn't really clear on what the program was doing (it's been months since I last looked at it), but I remember I made a fairly serious effort to get it working, so maybe I was barking up the wrong tree.

Then I got a new idea. Each test case gives you several pairs of numbers: the original and the rearranged one. All of the numbers include a mix of one's and zero's. (If they didn't there wouldn't be any puzzle.) Start with the low order bit and a mask that has the same number of bits as our test cases and has all the bits set to one. Now go through the list of original numbers. If any of those numbers have the low order bit set, then AND the mask with the corresponding, rearranged number. If we are lucky, by the time we get to the end, there will only be one one bit left in the mask and we will know where our low order bit got moved to.

Now we can remove that bit from our mask, move our test bit to the next position, and repeat the process. If we have any unresolved bits at the end of this first iteration, we can continue, and by repeating this process we will eventually decipher the rules for rearrangement.