My answer to ruby quiz 121

My solution to Ruby quiz 121.

Given some morse code without breaks between letters (which can have ambiguous interpretations), it will generate the words that the morse code can generate.

It's implemented as a recursive depth-first search in Ruby. Branches are expanded dynamically in the first_letters function.

require 'pp'

class Morse
 @@alpha = {
  "a" => ".-",
  "b" => "-...",
  "c" => "-.-.",
  "d" => "-..",
  "e" => ".",
  "f" => "..-.",
  "g" => "--.",
  "h" => "....",
  "i" => "..",
  "j" => ".---",
  "k" => "-.-",
  "l" => ".-..",
  "m" => "--",
  "o" => "---",
  "p" => ".--.",
  "q" => "--.-",
  "r" => ".-.",
  "s" => "...",
  "t" => "-",
  "u" => "..-",
  "v" => "...-",
  "w" => ".--",
  "x" => "-..-",
  "y" => "-.--",
  "z" => "--.."
 }

 def initialize
  # turn around hash index to use morse chars index
  @rev = {}
  @@alpha.each { |k,v| @rev[v] = k.to_s }
 end

 # Returns all letters matching the morse str at this pos
 def first_letters(morse, pos)
  letters = []
  @rev.keys.each do |k|  
   letters << k unless morse[pos..-1].scan(/^#{k.gsub(".","\\.")}.*/).empty?
  end
  letters
 end

 # Returns an array of words that matches 'morse' string 
 # It's basically a recursive function implementing depth-first search 
 def morse2words(morse, pos = 0 , seen = "")
  solutions = []
  first_letters(morse, pos).each do |l|
   if morse.length == pos + l.length
    solutions << "#{seen}#{@rev[l]}"
   else
    result = morse2words(morse,(pos+l.length),"#{seen}#{@rev[l]}")
    solutions += result
   end
  end

  solutions
 end

 # Converts a word to a morse string, used for testing
 def word2morse(word)
  morse = ""
  word.each_byte { |b| morse << @@alpha[b.chr] }
  morse
 end
end


######################
# Test:

def test_word2morse
 m = Morse.new
 raise unless  m.word2morse("sofia") == "...---..-....-"  
end

def test_first_letters
 m = Morse.new
 raise unless m.first_letters(".", 0) == [ "." ];
 raise unless m.first_letters("--.--..--.-.", 0) == ["--", "-", "--.", "--.-"] 
end

def test_morse2words
 m = Morse.new
 sofia = "...---..-....-" 
 solutions = m.morse2words(sofia)
 pp solutions
 solutions.each do |s|
  if m.word2morse(s) != sofia 
   puts "bad solution: #{s}"
   puts "yields #{m.word2morse(s)} in morse"
   raise
  end
 end
end

test_word2morse
test_first_letters
test_morse2words