From mboxrd@z Thu Jan 1 00:00:00 1970 Message-ID: Date: Mon, 4 Oct 2004 14:45:45 -0400 From: Russ Cox To: Nigel Roles , 9fans <9fans@cse.psu.edu> Subject: Re: [9fans] OT: puzzle In-Reply-To: Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit References: Cc: Topicbox-Message-UUID: ecaae160-eacd-11e9-9e20-41e7f4b1d025 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