Re: [9fans] OT: puzzle

[Russ Cox <russcox@gmail.com>]

You can do it.  

When I say number-chunk, I mean the 16 bytes you
get for sprint(buf, "X%15d", n).  When I say zero-chunk
I mean 16 NUL bytes.

In the first half of each block, write the fixed pattern and
the block number.

Use the first half to classify the block as management, plain, or xor.

Treat the second half as a sequence of m 16-byte chunks.
Assuming m > 2*log2(n), you can treat each chunk as representing
a single bit in the block number.  When the chunk should represent
a 1 bit, set it to the number-chunk for n.  When the chunk should
represent a 0 bit, set it to the zero-chunk.  Then do the same trick
to encode the complement of the block number.  So if you are encoding
block 10 and you've decided to use 6-bit block numbers, the
second half looks like

  zero-chunk zero-chunk <10>-chunk zero-chunk <10>-chunk zero-chunk
  <10>-chunk <10>-chunk zero-chunk <10>-chunk zero-chunk <10>-chunk

When two number-chunks get xor'ed together, they lose the leading X,
so you know to ignore them.  

When you get an xor'ed block, scan the second half for intact
number-chunks (those that still have the leading X).  You'll find
at least one intact number-chunk from each of the two blocks
that got xor'ed, so just atoi() them to get your answer.

(This works because any two different numbers have to differ in their
binary representation somewhere - you'll get one block's 
pristine number-chunk at that bit position in the normal binary
encoding and the other block's pristine number-chunk at that position
in the complement.)

Russ