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