[QUIZ] Secret Agent 00111 (#94)

[James Gray-7]

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/

[Daniel Martin-7]

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 <tt> n == d * (2 ** exponent) + r </tt>
# * 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__

--
s=%q(  Daniel Martin -- [hidden email]
       puts "s=%q(#{s})",s.map{|i|i}[1]       )
       puts "s=%q(#{s})",s.map{|i|i}[1]

[James Gray-7]

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 Gray II

[Kero-2]

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

[James Gray-7]

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 :P

<laughs>  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 Gray II

[Kero-2]

>> Now I'll have to figure out something very simple: when is the new  
>> deadline
>> of this quiz :P
>
><laughs>  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

[Pierre Barbier de Reuille-4]

James Edward Gray 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 Gray 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

[Boris Prinz]

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

[Eric Torreborre]

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