From: Christian Theil Have <christiantheilhave@...>
Date: 2007-04-22T21:42:00+09:00
Subject: Re: [QUIZ] Morse Code (#121)

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