# Secret Agent 00111 (#94)

**URL:** <https://www.ruby-forum.com/t/secret-agent-00111-94/68145>\
**Category:** Ruby\
**Created:** [September 9, 2006, 7:36pm UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145 "2006-09-09T19:36:44Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 9, 2006, 7:36pm UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/1 "2006-09-09T19:36:44Z")

</div>

The three rules of Ruby Q.:

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 Q. by submitting ideas as often as you can:

[http://www.rubyquiz.com/](http://www.rubyquiz.com/)

1. Enjoy!

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

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

by Mauricio F.

"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/

```

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 13, 2006, 5:45pm UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/2 "2006-09-13T17:45:43Z")

</div>

It’s my fault this quiz was released late and I think it is a fun  
problem. I don’t want to cheat anyone out of a chance to solve it,  
so I’m extending the quiz one week. I will summarize a week from  
tomorrow.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 11, 2006, 7:44pm UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/3 "2006-09-11T19:44:47Z")

</div>

Q:

Got your memo about needing help with the encoding. The code is  
below; I’ve taken a fairly straightforward approach here, since the  
handheld device you described has more than enough computational power  
to encode what it needs to quickly enough to get the message through.

By the way, one of your unit tests - with the two StringIO objects -  
gave me an inordinate amount of trouble. I suggest that in the future  
you take advantage of IO.pipe when faced with a similar situation.

Let me know what’s up with those retirement plans, and look me up if  
you ever find yourself on this side of the pond.

Your Friend,  
Marshall Flinkman

#! /usr/bin/env ruby  
require ‘io/nonblock’

# The SecretAgent00111CommunicationGizmo class implements a way to

# send a series of true/false values through a binary channel using

# only a relatively small number of bytes. It does this by assuming

# that true values are much more likely than false values, and

# that therefore one can do a simple run length encoding on the

# original series of true/false values and end up with a sequence

# of numbers amenable to being compressed by a Rice code. (i.e. by

# a Golomb code with the parameter a power of 2)

# 

# The format of a compressed message of integers is:

# 

# \* One byte of _exponent_. Our code will use a parameter value of

# b = 2 \*\* _exponent_

# \* For each number _n_ that’s encoded:

# \* _d_ ‘1’ bits

# \* a ‘0’ bit

# \* _exponent_ bits that as a binary number form the value _r_

# The number _n_ then has the value n == d \* (2 \*\* exponent) + r
# \* Whatever number of '1' bits are necessary to pad the whole # transmission to an even byte boundary # # Bits within a byte are ordered as by \_pack("B\*")\_ -- that is, MSB first. class SecretAgent00111CommunicationGizmo class UndefinedRLE \< Exception; end end
# We’re going to define a bunch of class methods now,

# and SecretAgent00111CommunicationGizmo is just too

# long to write out over and over again, and I don’t

# like the look of putting “self.” in front of each

# method name as I define it, so…

class \<\< SecretAgent00111CommunicationGizmo

# Run length encode an input array of true/false values.

# Note that this array _must_ end in a “false” value, or an

# exception (SecretAgent00111CommunicationGizmo::UndefinedRLE)

# will be thrown.

def rle(tfarr)  
raise self::UndefinedRLE unless false == tfarr.last  
ans = []  
tfarr.inject(0) {|a,tf|  
if tf  
a + 1  
else  
ans\<\<a; 0  
end  
}  
ans  
end

# Undo the operation of +rle+. Expands a given array of numbers

# into an array of true/false values.

def unrle(inarr)  
inarr.map{|x| [[true]\*x,false]}.flatten  
end

# This method does the internal work of encoding a

# given number by our Rice code into a string of ‘0’ and ‘1’.

# Not really for client use.

def bits\_for\_encoding(x, exponent)  
a, b = x.divmod(1\<\<exponent)  
[‘1’ \* a, sprintf(‘0%0\*b’, exponent, b)].join  
end

# Encode a true/false array by first adding a “false” to the end

# and then encoding the resulting string of numbers via our Rice

# code.

def encode(array,exponent)  
msg = rle(array+[false]).map{|x|  
bits\_for\_encoding(x,exponent)  
}.join  
msg += ‘1’ \* ((- msg.length) % 8)  
exponent.chr + [msg].pack(“B\*”)  
end

# This method does the internal work to decode a

# message in ‘1’ and ‘0’ bits into an array of

# integers. Note that the string in msg is changed

# by this method, and shortened to whatever sequence

# at the end couldn’t be decoded.

def decode\_bits(msg,exponent)  
ans = []  
trim\_from = 0  
msg.scan(/(1\*)0([01]{#{exponent}})/) {|a,b|  
ans \<\< a.length\*(1\<\<exponent) + b.to\_i(2)  
trim\_from = $~.end(0)  
}  
msg.slice!(0,trim\_from)  
ans  
end

# Undo the result of +encode+

def decode(bitstring)  
# It’s not polite to mangle someone else’s bitstring  
# so don’t use slice! here  
# Seriously, the sample program stops working if you  
# mangle bitstring because then it doesn’t give the right  
# input to Decoder.new(StringIO.new(s))  
exponent = bitstring.slice(0,1)[0]  
msg = bitstring[1…-1].unpack(“B\*”)[0]  
unrle(decode\_bits(msg,exponent))[0…-2]  
end  
end

class SecretAgent00111CommunicationGizmo

# Lets subclasses call class methods as their own

def method\_missing(meth, \*args)  
self.class.send(meth,\*args)  
end

# This class is meant for on-the-fly compression to a given

# IO channel.

class Encoder \< SecretAgent00111CommunicationGizmo  
def initialize(exponent, output)  
output \<\< exponent.chr  
@exponent = exponent  
@output = output  
@current\_byte = ‘’  
@current\_run = 0  
end  
def \<\<(tf)  
if tf  
@current\_run += 1  
else  
send\_number(@current\_run)  
@current\_run=0  
end  
self  
end  
def finish  
self \<\< false  
@current\_byte += ‘1’ \* ((-@current\_byte.length)%8)  
output\_maybe  
end

```
private
def output_maybe
  if @current_byte.length >= 8
    out_bits = @current_byte.slice!(0,(@current_byte.length/8)*8)
    @output << [out_bits].pack("B*")
  end
end
def send_number(x)
  @current_byte += bits_for_encoding(x,@exponent)
  output_maybe
end

```

end

# This class is meant for on-the-fly decompression to a given

# IO channel.

class Decoder \< SecretAgent00111CommunicationGizmo  
attr\_reader :exponent  
def initialize(io)  
# StringIO isn’t really an IO object, so doesn’t know about  
# nonblock.  
io.nonblock = true if io.respond\_to?(:nonblock=)  
@io = io  
@initialized = false  
@remaining = ‘’  
end  
def exponent  
if not @initialized  
@exponent = @io.readchar  
@initialized = true  
end  
@exponent  
end  
def read  
exp = exponent  
ans = []  
# Use read with no arguments since read with an integer  
# argument messes up the bizarre way StringIO is used in  
# the unit test. Does Q not know about IO.pipe ?  
buff = @io.read rescue buff = nil  
while buff and buff.length \> 0  
@remaining += buff.unpack(“B\*”)[0]  
ans.concat unrle(decode\_bits(@remaining, exp))  
buff = @io.read rescue buff = nil  
end  
ans  
end  
end  
end

**END**

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 18, 2006, 5:08am UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/4 "2006-09-18T05:08:53Z")

</div>

On Sep 17, 2006, at 7:31 PM, Kero wrote:

> Now I’ll have to figure out something very simple: when is the new  
> deadline  
> of this quiz 😛

I will release the summary Thursday morning, which means  
you need to have it in before I start writing sometime Wednesday if  
you want me to look it over.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 18, 2006, 2:30am UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/5 "2006-09-18T02:30:43Z")

</div>

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

> - 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? © yes

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

Regards,  
Kero.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 18, 2006, 11:31pm UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/6 "2006-09-18T23:31:12Z")

</div>

> > Now I’ll have to figure out something very simple: when is the new  
> > deadline  
> > of this quiz 😛
> 
> I will release the summary Thursday morning, which means  
> you need to have it in before I start writing sometime Wednesday if  
> you want me to look it over.

OK, here we go 🙂

Somehow, I dug into the tests and missed test\_rle and test\_unrle above  
the  
TEST\_VECTORS. A pity, because they _do_ get your mind set onto those  
trailing false’s. Plus, especially test\_unrle is trivial to implement.  
Run like `ruby test_00111_gizmo.rb -n test_unrle` 🙂

Then on with test\_basic\_en/decoding. Encoder#\<\< shows directly why the  
extra  
false is required for a finite bitstream: the code doesn’t do a bloody  
thing  
when appending 'true’s. In order to get finite bitstrings (36 out of 37  
which end with ‘true’) across the wire, you have to append a ‘false’.  
For  
consistency _always_ append a ‘false’ when you close the string. and  
that is  
precisely what Encoder#finish does.

This way, Encoder#\<\< works for infinite bitstreams, too.

And then you need some padding (with ones! so the decoder won’t be able  
to  
decode them!) for those “practical” bytes.

The decoder has a statemachine to see whether its reading bits for the  
multiplier (:div) or the remainder (:rem, which is a binary encoded  
number  
as we all know for these powers-of-two codes; this is not the case for  
the  
general Golomb codes, you’d need an extra offset and sometimes one bit  
less). I had to add a state for the exponent (:exp) in the beginning and  
move some code around, instead of just reading the exponent in  
initialize,  
because at that time the (string)io can still be empty.

Note how Decoder#read returns as much as can be processed from the  
bitstream, up until what is received (dealing with byte boundaries;  
additional (fewer than eight) bits could be in the bitstream, but not  
yet  
available for the decoder; see how “practical” bytes are?)

The Gizmo::encode and Gizmo::decode look amazingly like the test\_encoder  
and  
test\_decoder tests. Sorry 🙂

By this time I was still messing with the trailing false, which I had to  
append to some tests. Apart from that, test\_decode\_partial and  
test\_round\_trip\_probabilistic came almost for free. When I finally saw  
the  
light, I could remove the trailing ‘false’ in Gizmo::decode, put the  
tests  
back to what they were supposed to be, and immediately after that, Q’s  
00111.rb ran as it was supposed to.

Thanks for the Quiz, taught me Golomb codes and Ruby’s StringIO.  
Oh, and I realize now that test\_decoder tests the infinite streams.

## And then, the code!

# Author: Kero van Gelder

# Copyright: Kero van Gelder, can be distributed under LGPL

require ‘stringio’

module SecretAgent00111CommunicationGizmo

class UndefinedRLE \< RuntimeError  
end

def self.unrle(ary)  
ary.inject([]) {|un, val|  
un.concat([true] \* val)  
un \<\< false  
}  
end

def self.rle(ary)  
result = []  
while not ary.empty?  
nr = 0  
while not ary.empty? and ary[0]  
nr += 1  
ary.shift  
end  
raise UndefinedRLE if ary.empty?  
ary.shift  
result \<\< nr  
end  
raise UndefinedRLE if result.empty?  
result  
end

Log2 = Math.log(2)

def self.encode(ary, exponent)  
io = StringIO.new  
encoder = Encoder.new(exponent, io)  
ary.each{|result| encoder \<\< result}  
encoder.finish  
io.string  
end

def self.decode(bitstring)  
ary = Decoder.new(StringIO.new(bitstring)).read  
ary.pop  
ary  
end

class Encoder  
attr\_reader :exponent, :io

```
def initialize(exponent, io)
  @exponent, @io = exponent, io
  io.print [exponent].pack("c")
  @ones = 0
  @buf = ""
  # @finished = false
end

def << bool
  finished? and raise "Channel closed"
  if bool
    @ones += 1
  else
    m = 2**exponent
    div, rem = @ones.divmod m
    @buf << ("1" * div)
    @buf << (("%0#{exponent+1}s" % (rem).to_s(2)).gsub(/ /, "0"))
    if (blen = @buf.length) >= 8
      #p [exponent, div, rem, @buf, blen]
      bytes = blen / 8
      io.print([@buf.slice!(0, bytes * 8)].pack("B*"))
    end
    #p io.string
    @ones = 0
  end
end

def finish
  self << false
  @finished = true
  @buf << ("1" * (8 - @buf.length % 8)) if @buf.length % 8 > 0
  io.print([@buf].pack("B*"))
end

def finished?
  @finished
end

```

end

class Decoder  
attr\_reader :io  
def initialize(io)  
@io = io  
@state = :exp  
@buf = “”  
@div = 0  
@rem = “”  
end

```
def exponent
  if @state == :exp # and io.ready?
    @exponent = io.read(1).unpack("c")[0]
    @state = :div
  end
  @exponent
end

def read
  if @state == :exp # and io.ready?
    @exponent = io.read(1).unpack("c")[0]
    @state = :div
  end
  result = []
  @buf << io.read.unpack("B*")[0]
  while not @buf.empty?
    #p [@buf, @state, @exponent, @div, @rem]

    if @state == :div
      while not @buf.empty? and @buf[0] == ?1
        @buf.slice!(0, 1)
        @div += 1
      end
      @state = :rem unless @buf.empty?
    end
    #p [@buf, @state, @div, @rem]

    if @state == :rem
      req = exponent + 1 - @rem.length
      if @buf.length < req
        @rem << @buf.slice!(0..-1)
      else
        @rem << @buf.slice!(0, req)
        result.concat([true] * (@div * 2**exponent + @rem.to_i(2)))
        result << false
        @div = 0
        @rem = ""
        @state = :div
      end
    end
  end
  result
end

```

end  
end

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 20, 2006, 8:11am UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/7 "2006-09-20T08:11:57Z")

</div>

Hi,

here’s my solution. It’s based on strings of “1"s and “0"s, so the  
encoding  
can be done mainly with a format string (”%0#{@exponent+1}B”) and  
the decoding with regular expressions.

Regards,  
Boris

### 00111\_gizmo.rb

require ‘stringio’

module SecretAgent00111CommunicationGizmo  
class ExponentUndefined \< Exception  
end

class UndefinedRLE \< Exception  
end

def self.decode data  
events = Decoder.new(StringIO.new(data)).read  
events.pop # remove last false  
events  
end

def self.encode events, exponent  
io = StringIO.new  
e = Encoder.new(exponent, io)  
events.each do |result|  
e \<\< result  
end  
e.finish  
io.string  
end

def self.rle events  
raise UndefinedRLE.new if events.size == 0  
rl = []  
truevals = 0  
events.each do |result|  
if result  
truevals += 1  
else  
rl \<\< truevals  
truevals = 0  
end  
end  
raise UndefinedRLE.new if truevals != 0  
rl  
end

def self.unrle rl  
events = []  
rl.each {|n| events += [true]\*n + [false]}  
events  
end

class Encoder  
def initialize exponent, io  
@exponent = exponent  
@io = io  
@events = []  
@bits = ‘’  
@io \<\< exponent.chr  
end

```
 def << result
   @events << result
   if result == false
     encode_events
   end
 end

 def encode_events
   n = @events.size - 1
   @events = []
   @bits << "1" * (n / 2**@exponent)
   @bits << "%0#{@exponent+1}B" % (n % 2**@exponent)
   flush_bytes
 end

 def flush_bytes
   # write every 8 bits to the stream:
   @bits.gsub!(/[01]{8}/) do |byte|
     @io << byte.to_i(2).chr
     ''
   end
 end

 def finish
   @events << false
   encode_events
   # fill up remaining byte with "1"s:
   rest = @bits.size % 8
   if rest != 0
     @bits << "1" * (8 - rest)
   end
   flush_bytes
 end

```

end

class Decoder  
def bits(string)  
string.unpack(“B\*”)[0]  
end

```
 def initialize io
   @io = io
   @exponent = nil
   @bits = ''
   @t = @n = nil
 end

 def exponent
   return @exponent if @exponent
   e = @io.getc
   if e
     @exponent = e
   else
     raise ExponentUndefined.new
   end
   @exponent
 end

 def add_events
   n = @n
   n += @t * 2**exponent if @t
   @t = @n = nil
   @events += SecretAgent00111CommunicationGizmo.unrle([n])
 end

 def decode_bits
   loop do
     found = false
     if @bits =~ /^(1+)0/
       @t = $1.size
       @bits.sub!(/^(1+)/, '')
       found = true
     end
     re = Regexp.new("^0([01]{#{exponent}})")
     if @bits =~ re
       @n = $1.to_i(2)
       @bits.sub!(re, '')
       add_events
       found = true
     end
     return unless found
   end
 end

 def read
   @events = []
   begin
     exponent
     data = @io.read
     @bits += bits(data)
     decode_bits
   rescue ExponentUndefined
     # exponent not available yet in stream, try again later
   end
   @events
 end

```

end  
end

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 20, 2006, 6:03am UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/8 "2006-09-20T06:03:47Z")

</div>

James Edward G. II a écrit :

> It’s my fault this quiz was released late and I think it is a fun  
> problem. I don’t want to cheat anyone out of a chance to solve it, so  
> I’m extending the quiz one week. I will summarize a week from tomorrow.
> 
> James Edward G. II

So here is my solution … maybe not very optimal, but working … I  
just found not so easy to understand what he wanted exactly as an  
interface … and found disturbing to give a paper to implement  
something different (yet similar and obviously inspired by the paper).

Pierre

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [September 21, 2006, 11:37pm UTC](https://www.ruby-forum.com/t/secret-agent-00111-94/68145/9 "2006-09-21T23:37:31Z")

</div>

Hi,

Here’s my “solution” to the quiz. It passes the mandatory tests but not  
the  
StringIO tests (encode and decode\_partial).

I found it interesting to know about the Golomb coding, but I still can  
get  
ideas right about using IO with bits and bytes. This certainly points me  
to  
another area of study,…

The units tests were very helpful because they covered a lot of  
different  
cases (showing a new bug almost each time!) but the probabilistic test  
case  
was even more interesting because it detected a bug outside of the test  
suite. I have heard about QuickCheck which is an automatic testing tool  
for  
Haskell ([http://www.math.chalmers.se/~rjmh/QuickCheck/](http://www.math.chalmers.se/~rjmh/QuickCheck/)). This tool also  
makes use of random generated test cases and I am wondering if theses  
ideas  
could be imported into the Ruby world.

Eric.

====================================  
class SecretAgent00111CommunicationGizmo  
class UndefinedRLE \< Exception  
end

def self.rle(tries)  
# raise an error if there are no tries or if the array doesn’t end  
with  
a false try  
if (tries.empty? || tries[-1])  
raise UndefinedRLE.new(“tries empty: #{tries.empty?} - tries ends  
with: #{tries[-1]}”)  
end

```
# array[0..-2] returns an array with the last element removed
tries.map{|x| x ? "1" : "0"}.join("").split("0", 

```

-1)[0…-2].inject([])  
do |result, tries\_row|  
result \<\< tries\_row.size  
end  
end

def self.unrle(tries)  
tries.inject([]) do |result, tries\_row|  
tries\_row.times {result \<\< true}  
result \<\< false  
end  
end

def self.encode(array, exponent)  
tries, result = rle(array \<\< false), “”  
tries.inject(result) do |result, tries\_number|  
# divide the tries number with a power of two  
a, b = tries\_number.divmod(2 \*\* exponent)  
# the quotient is unary-encoded (‘1’ repeated a times)  
# the remainder is binary encoded  
result \<\< ‘1’ \* a + sprintf(“0%0\*b”, exponent, b)  
end

```
# pad the result with '1's in order to have an appropriate number of

```

bytes  
result \<\< ‘1’ \* (-result.length % 8)  
# add the exponent used for calculation and pack  
[exponent].pack(“c”) + [result].pack(“B\*”)  
end

def self.decode(bitstring)  
exponent, result = decode\_exponent\_and\_values(bitstring)  
result  
end

def self.decode\_exponent\_and\_values(bitstring)  
bitstring = bitstring.unpack(“B\*”)[0]  
# the exponent is binary encoded on 8 bits  
exponent = bitstring.slice!(0…7).to\_i(2)

```
result = []
# stop analyzing the bit if empty or if anything that's left is 

```

padding  
while(not bitstring.empty? and not bitstring =~ /\A1+$/)

```
  # the quotient is unary encoded at the beginning of the bitstring 

```

if  
!= 0  
coded\_quotient = “”  
bitstring.scan(/(\A1+)0+\w\*/){|x| coded\_quotient = x[0]}  
bitstring.slice!(0, coded\_quotient.size)  
quotient = coded\_quotient.size

```
  # the remainder is binary encoded on exponent + 1 bits
  remainder = bitstring.slice!(0..exponent).to_i(2)
  result << quotient * (2 ** exponent) + remainder
end
return exponent, unrle(result)

```

end

class Encoder  
def initialize(exponent, io)  
@values = []  
@io = io  
@exponent = exponent  
end

```
def << value
  @values << value
end

def finish
  @io << SecretAgent00111CommunicationGizmo.encode(@values, 

```

@exponent)  
end  
end

class Decoder  
attr :exponent  
def initialize(io)  
@exponent, @array =  
SecretAgent00111CommunicationGizmo.decode\_exponent\_and\_values(io.string)  
end

```
def read
  @array + [false]
end

```

end  
end