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*")
# 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}
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