From: Yossef Mendelssohn <ymendel@...>
Date: 2007-04-23T09:10:09+09:00
Subject: Re: Morse Code (#121)

Hey!  I'm internet famous! For some reason, I was sure there was a
backlog of suggestions and mine wouldn't come up for a while, if at
all.  Imagine my surprise when it was the very next quiz.

The reason I suggested this is because I wrote it myself about a year
ago (albeit in Perl, my main quick language at the time) in order to
help with a puzzle in Games magazine.  I then promptly forgot about
its existence until recently, when I was reading up on the Ruby Quiz.
It wasn't hard to figure out what to do next.

My own solution follows, ported from my original Perl.  The algorithm
hasn't been changed, mostly just converted.  It's not very quick or
efficient (or elegant), but it works.  Basically I create a trie
(using nested hashes) of the possibilities and then flatten it down to
a single level.

-----

class String

  class << self
    def morse_code_hash=(new_val)
      @@morse_code_hash = new_val
    end

    def morse_code_hash
      @@morse_code_hash
    end
  end

  def morsecode_possibilities
    raise "#{self} is not valid morse code" if self.match(/[^\-\.]/)

    @tree = get_tree

    @possibilities = @tree.flatten.keys.sort
  end

  def get_tree
    starts = @@morse_code_hash.keys.select { |k|  self.match(/
^#{Regexp.escape(k)}/) }

    tree = {}

    starts.each do |start|
      tree[ @@morse_code_hash[start] ] = self[start.length ..
-1].get_tree
    end

    tree
  end

end

class Hash
  def flatten
    tmp = {}
    each do |key, val|
      tmp[key] = val
      if val.is_a?(Hash)
        val.keys.each do |subkey|
          tmp["#{key}#{subkey}"] = val[subkey]
        end
        tmp.delete(key) unless val.empty?
      end
    end
    tmp = tmp.flatten while tmp.values.any? { |v|  !v.empty? }
    tmp
  end
end

codehash = {
  'A' => '.-',
  'B' => '-...',
  'C' => '-.-.',
  'D' => '-..',
  'E' => '.',
  'F' => '..-.',
  'G' => '--.',
  'H' => '....',
  'I' => '..',
  'J' => '.---',
  'K' => '-.-',
  'L' => '.-..',
  'M' => '--',
  'N' => '-.',
  'O' => '---',
  'P' => '.--.',
  'Q' => '--.-',
  'R' => '.-.',
  'S' => '...',
  'T' => '-',
  'U' => '..-',
  'V' => '...-',
  'W' => '.--',
  'X' => '-..-',
  'Y' => '-.--',
  'Z' => '--..'
}


String.morse_code_hash = codehash.invert

code = (ARGV.first || '').chomp

exit if code.empty?

puts "Getting possibilities for '#{code}':"

puts code.morsecode_possibilities.join("\n")