The three rules of Ruby Quiz:

1.  Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2.  Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion.  Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Mauricio Fernandez

"Secret Agent 00111 is back at the Casino again, playing a game of chance, while
the fate of mankind hangs in the balance. Each game consists of a series of
favorable events (probability p), terminated by the first occurrence of an
unfavorable event (probability q = 1 - p). More specifically, the game is
roulette, and the unfavorable event is the occurrence of 0, which has a
probability of q = 1 / 37. No one seriously doubts that 00111 will come through
again, but the Secret Service is quite concerned about communicating the
blow-by-blow description to Whitehall.

The bartender, who is a free-lance agent, has a binary channel available, but he
charges a stiff fee for each bit sent. The problem perplexing the Service is how
to encode the vicissitudes of the wheel[1] so as to place the least strain on
the Royal Exchequer."

00111 will be needing the communication device in 48H. Q has decided to give him
a programmable gizmo, with a built-in Ruby interpreter, in the hope that 00111
will code/play with it on his own and do his best to return it in the original
condition, very unlike all the other gadgets he's been given before. 

Therefore, Q can enjoy the luxury of coding in Ruby, and he's confident he will
be able to complete the task in time. Q's first thought of using Zlib::Deflate
to compress the data as shown in the following example:

	# EVENTS will be a large sequence of boolean events:
	#   true     favorable event   (00111 wins)
	#   false    unfavorable event (00111 loses)
	# we generate a sample one as follows:
	EVENTS = (0..1000).map{ rand() > 1.0 / 37 }
	
	# compress
	require 'zlib'
	string = EVENTS.map{|x| x ? "0" : "1"}.join("")
	string.size                                       # => 1001
	compressed = Zlib::Deflate.deflate(string)
	compressed.size                                   # => 69
	
	# now 'compressed' is transmitted by the bartender

However, Q has been wary of Zlib since he ran into some sort of BufferError when
he was installing Mongrel using RubyGems, and he still mourns the sad demise of
00110, which was the direct result of a binary incompatibility between a Ruby
build and a third-party extension.

Moreover, the MI6 has been spying on the management of the Casino, which faced a
similar problem and solved it long ago, and intercepted the following message at
the time the Casino's system was being developed:

	TEST RUN 43
	-----------
	Original size: 10000
	Compressed to: 242 bytes
	Result using deflate: 462 bytes

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] 

He also found some information in the Wikipedia[2], and wrote the following unit
tests before feeling indisposed while reading RailsBlob[3]:

	http://rubyquiz.com/test_00111_gizmo.rb

Q has also wrote some code to exert the SecretAgent00111CommunicationGizmo:

	http://rubyquiz.com/00111.rb

Finally, Q left a note with the expected (approximate) output one should get
when running 00111.rb:

	Dear myself,
	
	please make sure that
	 ruby 00111.rb
	writes something like this to stdout before you hand your beautiful creation
	to the brutish 00111:
	
	  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: 23 bytes (2.3%)
	  Compare to     57 bytes  using deflate...
	  =========================================
	  Testing buffered encoder/decoder
	  Decoded correctly? (b)  yes
	  Decoded correctly? (c)  yes
	  
	Sincerely,
	
	Q

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...

Good luck.

PS: you owe me one, man. Such opportunities are rare.

	----
	[1] http://urchin.earth.li/~twic/Golombs_Original_Paper/
	[2] http://en.wikipedia.org/wiki/Golomb_coding
	[3] http://railsblob.blogspot.com/