Better Living through Software

This is the puzzle.  If you want to see the solution, visit this post.

A few weekends ago, a friend introduced me to this puzzle while we were walking around the park.  It took me a few hours to find the solution and write a program to test it.  It’s a fun puzzle which I have never seen before, so I’m posting it to my blog.  I’ll reveal the solution in a separate post, so you can try solving it without any spoilers.

Introduction

Imagine that you have a 64-bit buffer, where you can alter one bit only before passing the buffer on to a friend.

If the initial state of the buffer is known beforehand (all zeros, for example), you will be able to send 64 different unique values to your friend.  This means that you can send 6 bits of information (2^6 = 64) by flipping only a single bit of a 64-bit buffer.  This is enough to encode all upper and lower case letters of the alphabet, for example.

Random Initial State

Now, imagine that the 64-bit buffer you receive is initially filled with random information.  This time, your friend does not know the initial state of the buffer.  Ad before, you are allowed to flip only one bit in the buffer.

Now, how many bits of information would you be able to communicate to your friend?

Obviously, you would be able to communicate at least one bit of information (for example, a “yes/no”).  You could do this by agreeing with your friend beforehand that the “yes/no” would be encoded in the first bit, and then you would flip the first bit if necessary before sending the buffer on, otherwise, you would flip a different bit.

Challenge

It turns out that it’s possible to encode a full 6-bits of information by flipping only one bit on a random buffer, with the recipient not knowing the initial state of the buffer.

Note that the same holds true for any buffer size that is a power of 2.  For example, you can encode 8 bits of information in a 256 bit buffer, using this technique.

Your challenge is to figure out what technique needs to be used, and write a program to encode a message in a random buffer of arbitrary size, and a program that can decode the message without knowing the initial state.

The method signatures might look something like:

bit[64] encodeBuffer(bit[64] randBuffer, bit[6] value);
bit[6] decodeBuffer(bit[64] encodedBuffer);

// the below will always be true

decodeBuffer(encodeBuffer(r, val)) == val

Hint

At first, I started down the route of using some sort of run length encoding, but that quickly hit a brick wall.

Instead, think of this as information being encoded in the parity.  For example, you could encode a “yes/no” by saying, if the first 32 bits have an even number of zeros, the answer will be “yes”, otherwise “no”.  To encode the “yes/no” message, you just flip a bit on one half or the other to get the desired parity.

With this hint, you can set about generalizing the solution.

This entry was posted on Thursday, January 28th, 2010 at 10:42 am and is filed under mastery. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.