From: "Stan K." <lists@...>
Date: 2013-07-30T00:44:27+09:00
Subject: Re: Morse Code (#121)

Christian Theil Have wrote in post #237067:
> Hi
>
> I've implemented it using a simple backtracking search algorithm.
>
> My code could probably be a lot more compact, and the first_letters
> function could definitely be
> much faster..
>
>
> 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
>     # Reverse index the array
>     @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 { |k|  letters << k unless
> morse[pos..-1].scan(/^#{k.gsub(".","\\.")}.*/).empty? }
>
>     letters
>   end
>
>   # Returns an array of words that matches 'morse' string
>   # It's basically a recursive function with bactracking
>   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)
>   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

Thanks, this was useful. You were missing an "n", I fixed it for you:

@@alpha = {
      "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" => "--.."
    }

-- 
Posted via http://www.ruby-forum.com/.