From: James Edward Gray II <james@...>
Date: 2007-05-14T12:25:35+09:00
Subject: Fwd: Please Forward: Ruby Quiz Submission

--Apple-Mail-3--1057530766
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

Begin forwarded message:

> From: Hirotsugu Asari <asari@mac.com>
> Date: May 13, 2007 6:58:20 PM CDT
> To: submission@rubyquiz.com
> Subject: Please Forward: Ruby Quiz Submission
>

--Apple-Mail-3--1057530766
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
	x-unix-mode=0644;
	x-mac-creator=54784D74;
	name=huffman.rb
Content-Disposition: attachment;
	filename=huffman.rb

#! /usr/bin/env ruby

# Ruby Quiz #123
# Copyright 2007 Hirotsugu Asari

class String
  def huffman_encode
    a = self.split(//)
    h = {} # hash of character occurences
    a.each { |c|
      h[c] = h[c].nil? ? 1 : h[c] + 1
    }
    # puts h.inspect
    a = h.sort { |a,b|
      # sort the hash in descending order of the values
      b[1] <=> a[1]
    }
    a = a.transpose[0]
    
    encoding={}
    # for encoding, we will always start with
    # 0, 10, 110, 1110, 11110, ...
    a.each_with_index { |o,i|
      encoding[o] = ("1"*i).to_i(2) << 1
    }
    # .... and the last one is 111...111, which is obtained by
    # shifting 1111...1110 to the right by 1 bit.
    encoding[a[-1]] = encoding[a[-1]] << -1
    
    @key = encoding
    # puts @key.inspect
    
    # finally, map the binary representation of these numbers
    self.split(//).map { |c| encoding[c].to_s(2) }.
      # ...and concatenate
      inject("") { |s, i| s + i }
  end
  
  def huffman_key
    self.huffman_encode
    @key
  end

  def to_blocks_of_8( delim=" " )
    self.scan(%r{.{1,8}}).join(delim)
  end
  
end

--Apple-Mail-3--1057530766
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	delsp=yes;
	format=flowed

>
> Here's my answer to #123.
>
> I didn't think through the decoding part.  The "extra credit"  
> suggests padding "1" to the next byte boundary, but thus padded  
> string of 1's can be a legal word in the encoding.  (AAAAABBB and  
> AAAAABB will have the same encoding.)
>
> (As with the last week, I would like to have this email address  
> hidden.  Thanks.)
>
> Hiro.


--Apple-Mail-3--1057530766--