From: Mark Day <mday@...>
Date: 2007-04-23T01:32:21+09:00
Subject: [QUIZ][SOLUTION] Morse Code (#121)

Thanks!  That was a fun problem for a newbie.  It was simple enough  
to come up with a basic solution pretty rapidly, with several  
opportunities to refine and experiment.

-Mark

#
# Ruby Quiz #121: Morse Code
#
# The example Morse code from the quiz is: ...---..-....-
#

#
# MORSE_SYMS: A dictionary mapping letters to their morse code.
#
MORSE_SYMS = { "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", "--.." }

#
# morse_words: Given a string of Morse code (s), return an array
# of strings of letters which have the same morse code.
#
# The technique is recursive: attempt to match the start of the
# Morse code string to the Morse code for each letter.  If it
# matches, then return an array of words starting with that letter,
# and followed by all possible strings made up from the remaining
# Morse code.
#
def morse_words(s)
	words = []
	MORSE_SYMS.each_pair do |letter, morse|
		#
		# If the remaining string exactly matches a letter, then
		# add that letter (by itself) as a result.  This is how the
		# recursion "bottoms out."
		#
		if s == morse
			words << letter
			next
		end
		
		#
		# Does the Morse code for the current letter match the start
		# of the Morse code string?
		#
		l = morse.length
		if s[0,l] == morse
			#
			# Generate the possibilities starting with the current letter.
			#
			morse_words(s[l..-1]).each do |w|
				words << letter+w
			end
		end
	end
	return words
end

#
# to_morse: Convert a word into its Morse code equivalent by splitting
# the word into individual letters, mapping each letter, and rejoining
# them with the given separator.
#
def to_morse(word, sep="|")
	word.scan(/./).map { |c| MORSE_SYMS[c] }.join(sep)
end

if __FILE__ == $0
	#
	# The command line arguments are paths to files containing
	# dictionary words separated by whitespace.  For example,
	# pass /usr/share/dict/words.
	#
	dictionary = []
	ARGV.each do |path|
		# puts "Reading #{path}..."
		dictionary.concat(open(path).read.split)
	end
	
	#
	# The following words were translations from the example Morse
	# code string, but not in my dictionaries, so add them so we
	# can test the "word in dictionary" case.
	#
	dictionary << "sofia"
	dictionary << "eugenia"
	
	#
	# Read Morse code strings from standard input, and print possible
	# words to standard output.
	#
	$stdin.each do |morse|
		words = morse_words(morse.chomp)
		words.sort!		# Sorted output is easier to scan
		
		#
		# Find the length of the longest Morse code string
		# so that we can line up columns nicely.
		#
		morse_max = words.map { |w| to_morse(w).length }.max
		
		#
		# Separate the words into two lists: those words which are
		# in the dictionary, and those that aren't.
		#
		dict_words = words & dictionary
		non_dict_words = words - dict_words
		
		#
		# Print the words.  I chose to print the dictionary words
		# last, so they'd be easier to spot.
		#
		puts "Non-dictionary words:"
		non_dict_words.each do |word|
			print to_morse(word).ljust(morse_max), " => ", word, "\n"
		end

		puts "Dictionary words:"
		dict_words.each do |word|
			print to_morse(word).ljust(morse_max), " => ", word, "\n"
		end
	end
end