> Q keeps a very detailed log of his activities, so you know he has been reading
> up on Information Theory, and has found a paper that addresses the very problem
> he needs to solve:
>
> 	Run-length encodings--S. W. Golomb (1966); IEEE Trans Info Theory 12(3):399[1] 

Gave me the chance to actually read Golomb's paper, which I never had :)

[snip]

> Unfortunately, it seems Q is not doing any better, but management is sure you
> will be able to complete Q's code (that is, write 00111_gizmo.rb such that the
> above unit tests pass and the sample program works) in time, given all the
> material he left. 
>
> 00111's mission will require _at least_ the following tests to pass:
>
> 	* test_rle
> 	* test_unrle
> 	* test_basic_encoding
> 	* test_basic_decoding
> 	* test_round_trip_probabilistic
>
> The other tests are optional (you can choose to comment them, but the sample
> program won't execute correctly if they fail, though), but you should probably
> do your best to make them pass: this is an excellent opportunity to prove your
> skills, and it seems Q's retirement is not too far away...

I'm all for TDD, but a little bit of explanation would have been welcome
1) Golomb's paper mentions m, you use an exponent, such that 2**exponent is m
   (so we're missing all the fun with M; aren't these the Rice codes?)
2) placing the exponent in a BYTE before the bits is... practical...
3) why does there seem to be an extra 'false' trailing, in (some!) of the
   bitstreams of the testcases?

After I figured out all of that (I happily started with arbitrary m... and
with hindsight, (3) kept me confused longer than it should have; tests
working on infinite bitstreams before turning to the finite bit-strings (and
then byte-strings) would have helped (unfortunately test_decoder_partial is
derived from those finite TEST_VECTORS and therefore carries its problems
back into the infinite bitstream domain :( ) ) I managed:

Probability : 0.972972972972973
Approx. with: 0.957603280698574
Exponent: 4  (p**4 = 1/2; m = 2 ** e = 16)
Decoded correctly?   yes
Original size: 1000
Compressed to: 27 bytes (2.7%)
Compare to     72 bytes  using deflate...
================================================================================
Testing buffered encoder/decoder
Decoded correctly? (b)  yes
Decoded correctly? (c)  yes

Now I'll have to figure out something very simple: when is the new deadline
of this quiz :P

Regards,
Kero.