The idea for this quiz was given to me by Yossef Mendelssohn.
Morse code is a way to encode telegraphic messages in a series of long and short sounds or visual signals. During transmission, pauses are used to group letters and words, but in written form the code can be ambiguous.
For example, using the typical dot (.) and dash (-) for a written representation of the code, the word ...---..-....- in Morse code could be an encoding of the names Sofia or Eugenia depending on where you break up the letters:
...|---|..-.|..|.- Sofia
.|..-|--.|.|-.|..|.- Eugenia
This week's quiz is to write program that displays all possible translations for ambiguous words provided in code.
Your program will be passed a word of Morse code on STDIN. Your program should print all possible translations of the code to STDOUT, one translation per line. Your code should print gibberish translations in case they have some meaning for the reader, but indicating which translations are in the dictionary could be a nice added feature.
We will only focus on the alphabet for this quiz to keep things simple. Here are the encodings for each letter:
A .- N -.
B -... O ---
C -.-. P .--.
D -.. Q --.-
E . R .-.
F ..-. S ...
G --. T -
H .... U ..-
I .. V ...-
J .--- W .--
K -.- X -..-
L .-.. Y -.--
M -- Z --..
Quiz Summary
I always forget how much I love the simple problems. Everyone plays when we have them and the solutions tend to be quite creative. This time was no different. Everyone did see MenTaLguY's state machine parser, right?
Solving the problem, even with the suggested extra credit, is easy stuff though. Let's have a look at Bob Showalter's solution to see just how easy. Here's the start of the code:
DICT = '/usr/share/dict/words'
class Morse
@@words = nil
LETTER = Hash[*%w/
A .- N -.
B -... O ---
C -.-. P .--.
D -.. Q --.-
E . R .-.
F ..-. S ...
G --. T -
H .... U ..-
I .. V ...-
J .--- W .--
K -.- X -..-
L .-.. Y -.--
M -- Z --..
/]
# ...
Here we see some setup work. Bob defines a constant to point at the dictionary on his system. The comment encourages you to tweak this for your system.
Next we have a the start of a class definition. This class is really just used as a namespace. No objects are ever constructed from it. Given that, a module definition might have better represented it's purpose.
The class variable will hold the actual dictionary words, assuming the user requests that we load it. More on that in a bit.
Finally, we have a wonderful little trick that many solvers picked up on. It's possible to write some Ruby that will allow you to paste the translation chart from the quiz directly into your code and actually have that be a meaningful data structure. Here we see the whole thing converted into a whitespace delimited Array, which is then splatted into Hash form. Every other element becomes a key or value, so we end up with Morse code values keyed by the English letter it translates to. Very clever stuff.
Here's the dictionary loading code:
# loads dictionary file to limit the words output
def self.load_dictionary(path)
@@words = {}
File.open(path, 'r') do |f|
while word = f.gets
@@words[word.chomp.upcase] = true
end
end
end
# ...
This method creates a Hash to hold the words, reads the indicated file line by line, peels off line endings, and normalizes word case, filling the Hash as it reads. Most solutions that included dictionary handling had a chunk of code very similar to this. This particular version could be simplified a touch by using File.foreach().
The last method of Bob's class does the heavy lifting:
# returns list of words starting with prefix that can be made from code
def self.words(code = @code, prefix = '')
results = []
if code == ''
results << prefix if @@words.nil? || @@words.include?(prefix)
else
LETTER.sort.each do |l, p|
if code[0, p.length] == p
results += words(code[p.length,code.length], prefix + l)
end
end
end
results
end
end
# ...
This is a very straightforward recursive decoder. We get two parameters here: the remaining code (ignore that unused default) and any prefix we should apply to words generated from that code. You can see that the method defines, fills, and returns an Array of results. How those results are generated is the interesting bit.
The if statement branch comes into play when we run out of code to translate. In that case, the word is added to the results, as long as no dictionary was loaded or the word is in the loaded dictionary. This means that you can run this code without using a dictionary to see all options or with a dictionary to see only likely matches.
The else branch handles all cases where we have some code left. When that happens, each letter is tried at the start of the code. If it matches, the method recurses using the code after the matched letter and the existing prefix plus the new letter. All words generated from the recursive calls are added to the current result set. This generates all possible combinations.
I should note here that there was some discussion over similar code from Donald A. Ball Jr. that yielded the words to a block instead of collecting them in an Array. This is probably a good move for this particular decoder, since there are a surprising 5,104 possible translations of the simple code provided in the quiz. Collecting larger translations in an Array might get a bit resource intensive. Bob's method is easily converted:
def self.words(code, prefix = '', &block)
if code == ''
block[prefix] if @@words.nil? || @@words.include?(prefix)
else
LETTER.sort.each do |l, p|
if code[0, p.length] == p
results += words(code[p.length,code.length], prefix + l, &block)
end
end
end
end
Note the three simple changes: I added the block as a parameter, I pass finished words to the block instead of placing them in an Array, and I hand the block down the stack when we recurse. This removes the need for the results Array, so I have also trimmed that code.
Getting back to Bob's solution, here is the application code that makes it run:
Morse.load_dictionary(DICT) if ARGV.delete('-d')
abort "Usage: #{$0} [-d] code [...]" if ARGV.empty?
ARGV.each do |code|
puts "#{code}:"
puts Morse.words(code) # Morse.words(code) { |w| puts w } with the block
end
First we see the optional dictionary flag interpretation. We've already talked about how the code changes depending on whether or not a word list is loaded.
The next line is a usage statement printed by abort(). We don't see that method too often in quiz solutions, but it prints a message to STDERR, when provided, and then terminates the program. Note that the usage statement tells us this code differs slightly from the quiz interface, taking the code as a command-line argument instead of reading it from STDIN.
That last iterator just walks the provided codes printing the translations returned from a call to Morse.words().
---.-- -.....--.-.-... ---- .-.-...-.. .--....--- -.-..--. .-...--.. -----.-..... -.-.----... (.-.-.-.----...-.. -...-.-- --.-.-.-.- -...--.--... ...---.-....--..----.)
Tomorrow we have another easy, though more practical, challenge...
