Christian Theil Have
4/22/2007 12:42:00 PM
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