From: Erik Veenstra <erikveen@...>
Date: 2007-04-23T01:05:11+09:00
Subject: Re: Morse Code (#121)

* O(c^n)?... :{ (It's like a non-deterministic finite state
  machine with only one state...)

* Includes the dictionary words.

* No state.

How it works? find_words() takes a (partial) word and a
sequence, starting with an empty string and the input sequence.
If "._" could be "shifted" from the sequence, the character "a"
is added to the (partial) word and find_words() is called with
the new (partial) word and the remaining sequence as sequence.
This is done for all characters of the alphabet (iteration) and
all "characters" in the sequence (recursion), until
find_words() receives an empty sequence, in which case the word
is a final word.

 ["", ".--....-..."]
   ["a", "-....-..."]
   ["ab", ".-..."]
     ["aba", "..."]
       ["abae", ".."]
         ["abaee", "."]
           ["abaeee", ""]       <-- Final word.
         ["abaei", ""]          <-- Final word.
       ["abai", "."]
         ["abaie", ""]          <-- Final word.

gegroet,
Erik V. - http://www.erikveen.dds.nl/

----------------------------------------------------------------

 $ cat morse.rb
 class Morse
   MORSE_CODES          = %w{.- -... -.-. -.. . ..-. --. .... .. .---
-.- .-.. -- -. --- .--. --.- .-. ... - ..- ...- .-- -..- -.--
--..}.zip(("a".."z").to_a)

   DICTIONARY_WORDS     = File.open("/usr/share/dict/words"){|f|
f.read}.downcase.split(/[^a-z]/)       rescue nil

   def parse(sequence)
     real_words(find_words(sequence.gsub(/\s+/, "")))
   end

   private

   def find_words(sequence, word="", results=[])
     if sequence.empty?
       results << word
     else
       MORSE_CODES.each do |seq, chr|
         if sequence.index(seq) == 0
           find_words(sequence[seq.length..-1], word+chr, results)
         end
       end
     end

     results
   end

   def real_words(words)
     words & DICTIONARY_WORDS rescue words
   end
 end

 puts Morse.new.parse($stdin.read)

----------------------------------------------------------------

 $ echo ".--....-..." | ruby morse.rb
 abets
 able
 adele
 pile
 wests

----------------------------------------------------------------