Morse Code (#121)

Ruby
1

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

The idea for this quiz was given to me by Yossef M…

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 --…

2

On 4/20/07, Ruby Q. [email protected] wrote:

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.

This is my first Ruby Q…
I am interested in seeing how it can be made to run faster and also
how other people approached it.

letters = Hash.new(“*”)
abc = %w[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]
marks = [“.-”,“-…”,“-.-.”,“-…”,“.”,“…-.”,“–.”,“…”,
“…”,“.—”,“-.-”,“.-…”,“–”,“-.”,“—”,“.–.”,“–.-”,“.-.”,
“…”,“-”,“…-”,“…-”,“.–”,“-…-”,“-.–”,“–…”]

marks.each do |x|
letters.store(x,abc[marks.index(x)])
end

puts “Enter Morse code”
str = gets.chomp
str_arr = str.split(//)

nums = []
(0…5 ** str.length/4).each do |b|
if b.to_s(5) !~ /0/
sum = 0
b.to_s(5).split(//).each {|hj| sum += hj.to_i }
if sum == str.length
nums << b.to_s(5)
end
end
end

unpackers = []
nums.each do |x|
unpackers << x.to_s.split(//).collect {|u| “A” + u}.join
end

morse = []
unpackers.each do |g|
morse << str.unpack(g)
end

words = []
morse.each do |t|
word = “”
t.each do |e|
word << letters[e]
end
words << word unless word =~ /*/
end
puts words

Harry

3

Ruby Q. <james grayproductions.net> writes:

This week’s quiz is to write program that displays all possible translations
for ambiguous words provided in code.

Wow, a ruby quiz with no discussion or clarifications? Sounds easy
enough for me
to have a go at my second ruby quiz entry:

#############################
class String

Calls the given block for every substring with length given in

+range+

Yields the string’s head [0…i] and tail [i…-1] for each i in

+range+
def each_substr(range = [1,self.length])
raise ArgumentError, “Block required” unless block_given?
range.first.upto([self.length, range.last].min) do |i|
yield [ self[0…i], self[i…-1] ]
end
end
end

class Morse

Windows users like me don’t have a dictionary, so use your own if

you like
Dictionary = [‘i’, ‘a’, ‘an’, ‘emu’, ‘pet’, ‘sofia’, ‘eugenia’]

Letters = {
‘.-’ => :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,
}

def initialize code
raise ArgumentError, “Invalid morse code string” unless
code.match(/^[.-]+$/)
self.string = code
end

def string=(newstring)
@string = newstring
@words = nil
end

Run the calculation and save each result with a boolean indicating

whether

it’s in the dictionary or not

def words
@words ||= self.class.permutate(@string).sort.map do |word|
[Dictionary.include?(word), word]
end
end

class << self

# Generate all valid 'words' from a morse code string
def permutate morse
  results = []
  # Grab the next 1-4 letters from the string
  morse.each_substr(1..4) do |substr, rest|
    letter = Letters[substr]
    if letter
      # If this substring is a letter, calculate sub-permutations
      # (using the remaining part of the string)
      permutations = permutate(rest)
      if permutations.empty?
        results << "#{letter}"
      else
        # Add each sub-permutation to the current letter, and add

that to
# the list of results
permutations.each do |permutation|
results << “#{letter}#{permutation}”
end
end
end
end
results
end

# Turns a string back into its morse code form
def morsify string, separator = '|'
  string.split(//).map do |letter|
    Letters.invert[letter.intern]
  end.join separator
end

end

end

if FILE == $0
while (line = gets.chomp) && !line.empty?
begin
out = Morse.new(line).words.map do |in_dict, word|
“%-#{line.length+2}s %s” %
[(in_dict ? “[#{word}]” : " #{word}"), “#{Morse.morsify
word}”]
end
rescue ArgumentError => e
out = “Invalid morse code string (‘#{line}’)”
end
puts out
end
end

4

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

5

Here is mine using simple recursion.

#!/usr/bin/env ruby -wKU

require “set”

WORD_FILE = “/usr/share/dict/words”
MORSE_LETTERS = %w[.- -… -.-. -… . …-. --. … … .— -.- .-…

-. — .–. --.- .-. … - …- …- .-- -…- -.-- --…]

map encodings to letters

ENCODINGS = Hash[*MORSE_LETTERS.zip((‘A’…‘Z’).to_a).flatten]

def morse_decodings(word)

iterate through matching prefixes

ENCODINGS.select { |p,l| p == word[0,p.size] }.map do |
prefix,letter|

# gather decoded suffixes for the current prefix
suffixes = morse_decodings( word[prefix.size,word.size] )

# append decoded suffixes to decoded letter
suffixes.empty? ? letter : suffixes.map { |s| letter + s }

end.flatten
end

decodings = morse_decodings(readline.chomp).sort

puts “All Possible Decodings:”
decodings.each { |e| puts e }

read word file into set (for fast indexing)

words = Set.new
open(WORD_FILE).each { |line| words << line.chomp.upcase }

puts “All Decodings in Dictionary:”
decodings.each { |e| puts e if words.include? e }

END

Carl P.

6

My solution is short enough that I don’t need to explain the code
outside of my
comments. For input, the first line is the morse code to translate, and
every
line after (until EOF) is one dictionary word (case insensitive). It can
be
called with or without a --matching command-line option. Without it, all
translations are printed, and those in the dictionary are marked. With
it, only
translations matching a dictionary word are printed.

On my Linux machine, I was able to dump aspell’s dictionary to do things
like
this:

jesse@ricercar $ echo …—…-…- > input
jesse@ricercar $ aspell dump master en_US >> input
jesse@ricercar $ ./morse_code.rb --matching < input
Enter morse code to translate:
Enter dictionary words (case does not matter, EOF when done):
Translations:
EUGENIA
SOUSA
SOFIA

The code:

#!/usr/bin/env ruby

morse_code.rb

Ruby Q. 121: Morse Code

require ‘set’

Decode = {
‘.-’ => ‘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’
}

Could hard-code these, but what fun would that be?

MinCodeLength = Decode.keys.min { |k,j| k.length <=> j.length }.length
MaxCodeLength = Decode.keys.max { |k,j| k.length <=> j.length }.length

class Array

Yield once for each way of grouping the elements into groups of size

between min_length and max_length (inclusive). It works recursively:

empty arrays return self, and longer arrays take all initial (head)

slices of valid lengths, and append to that each grouping of the

remaining tail.

def each_grouping(min_length, max_length)
if empty?
yield self
else
max_length = size if size < max_length
(min_length…max_length).each do |code_length|
head = [slice(0, code_length)]
slice(code_length…-1).each_grouping(min_length, max_length) do
|tail|
yield head + tail
end
end
end
end
end

class String

Yield once for each translation of this (Morse code) string.

def each_translation
split(//).each_grouping(MinCodeLength, MaxCodeLength) do |group|
# Convert arrays of individual dots & dashes to strings, then
translate.
group.map! { |char_arr| Decode[char_arr.join] }
# Skip if something was not translated.
next if group.any? { |letter| letter.nil? }
# Join all the translated letters into one string.
yield group.join
end
end
end

if $0 == FILE
src = $stdin
dict = Set[]

if ARGV.include?(’–matching’)
trans_handler = lambda do |trans|
puts trans if dict.include? trans
end
else
trans_handler = lambda do |trans|
print trans
dict.include?(trans) ? puts(’ <-- In dictionary!’) : puts
end
end

puts ‘Enter morse code to translate:’
code = src.gets.chomp
puts ‘Enter dictionary words (case does not matter, EOF when done):’
while dict_word = src.gets
dict << dict_word.chomp.upcase
end

puts ‘Translations:’
code.each_translation { |trans| trans_handler[trans] }
end

7

This is my first rubyquiz as well. My solution uses simple recursion and
also checks matches against a dictionary. For fun, I also checked the
frequency of words within a holmes novel to determine probabilistically
which match was the most likely (we could train on any number of text
documents, just chose this one for fun).

Here’s my solution:

file: morse_trained.rb

author: Drew O.

the train method is based on this rubytalk post:

How to Write a Spelling Corrector - Ruby - Ruby-Forum

we build a model based on the frequency of words

within the text provided here: http://www.norvig.com/holmes.txt

combined

with the frequency in the local dictionary. this means any word in the

dictionary

will have a frequency of 1 and words appearing in the holmes text will

have

increased frequencies, thus being favored in the sort later in the

program.

the goal is the present the user with the most relevant matches first.

both files were saved locally.

def train texts
model = Hash.new(0)
texts.each do |text|
File.new(text).read.downcase.scan(/[a-z]+/).each do |word|
model[word] += 1
end
end
return model
end

global hash of word → frequency pairs

NWORDS = train [‘holmes.txt’,‘dictionaries/2of4brif.txt’]

MorseLetter holds a pattern and the letter associated

with the pattern

MorseLetter = Struct.new(:pattern,:letter)

global array to hold all the MorseLetter objects

LETTERS = [MorseLetter.new(/^.-/,“A”),
MorseLetter.new(/^-.../,“B”),
MorseLetter.new(/^-.-./,“C”),
MorseLetter.new(/^-../,“D”),
MorseLetter.new(/^./,“E”),
MorseLetter.new(/^..-./,“F”),
MorseLetter.new(/^–./,“G”),
MorseLetter.new(/^..../,“H”),
MorseLetter.new(/^../,“I”),
MorseLetter.new(/^.—/,“J”),
MorseLetter.new(/^-.-/,“K”),
MorseLetter.new(/^.-../,“L”),
MorseLetter.new(/^–/,“M”),
MorseLetter.new(/^-./,“N”),
MorseLetter.new(/^—/,“O”),
MorseLetter.new(/^.–./,“P”),
MorseLetter.new(/^–.-/,“Q”),
MorseLetter.new(/^.-./,“R”),
MorseLetter.new(/^.../,“S”),
MorseLetter.new(/^-/,“T”),
MorseLetter.new(/^..-/,“U”),
MorseLetter.new(/^...-/,“V”),
MorseLetter.new(/^.–/,“W”),
MorseLetter.new(/^-..-/,“X”),
MorseLetter.new(/^-.–/,“Y”),
MorseLetter.new(/^–../,“Z”)]

a recursive method which checks the code for letter matches,

builds the translation string, removes the matched

portion of the code and then recurses

the method returns an array of all possible morse code translations

def translate code, translation = “”

recursion base case:

return an array containing the translation if the code has

a size of 0

return [translation.downcase] if code.size.zero?

words = []

check all possible matches to the code

LETTERS.each do |letter|
if code[letter.pattern]

  # recurse on untranslated portion of the code
  # and new translation
  # add results to our array at this level of recursion
  words += translate

code.sub(letter.pattern,‘’),translation+letter.letter
end
end

return words

end

read the initial code from standard input

code = gets.chomp

initial call to translate with the complete code

and no translation string

words = translate code

sort the resulting words first based on the frequency in NWORDS

and the dictionary in a decreasing order and then by the word itself.

this

preserves alphabetical order when words have the same frequency or

do not appear in the dictionary. we then print each word along with an

asterisk if that word is in the dictionary (or in the training

material

but not in the dictionary).

words.sort_by{|word| [-NWORDS[word],word] }.each do |word|
puts “#{word.capitalize} #{”*" if NWORDS[word] > 0}"
end

8

|Ruby Q.|

Straightforward and memory-greedy solution.

= Tables

== table.rb

An interface to subsequent tables

class Table

def initialize
@table = {}
compose
end

def compose
end

def
@table[value]
end

end

== morse.rb

require ‘table’

class Morse < Table

def compose
@table[‘.’] = ‘E’
@table[‘…’] = ‘I’
@table[‘.-’] = ‘A’
@table[‘…’] = ‘S’
@table[‘…-’] = ‘U’
@table[‘…’] = ‘H’
@table[‘…-’] = ‘V’
@table[‘…-.’] = ‘F’
@table[‘.-.’] = ‘R’
@table[‘.–’] = ‘W’
@table[‘.-…’] = ‘R’
@table[‘.–.’] = ‘P’
@table[‘.—’] = ‘G’
@table[‘-’] = ‘T’
@table[‘-.’] = ‘N’
@table[‘–’] = ‘M’
@table[‘-…’] = ‘D’
@table[‘-.-’] = ‘K’
@table[‘-…’] = ‘B’
@table[‘-…-’] = ‘X’
@table[‘-.-.’] = ‘C’
@table[‘-.–’] = ‘Y’
@table[‘–.’] = ‘G’
@table[‘—’] = ‘O’
@table[‘–…’] = ‘Z’
@table[‘–.-’] = ‘Q’
end

end

== probability.rb

I’ve decided to use letters probabilities approach. Output strings

will be sorted by difference (Euclidean metric) between input

distribution and control

distribution for English language (taken from [1]).

However possible benefits are visual only in large texts. But large

texts are processed very lo-o-ong…

In few signals’ string it’s just sends less meaningful values like

‘EEEETTTEEE’ to end.

In SOFIA/EUGENIA example: SOFIA was found at 1824’s position and

EUGENIA at 935’s from 5104 strings.

[1] http://www.fortunecity.com/skyscraper/coding/379/lesson1.htm

require ‘table’

class Probability < Table

def compose
@table[‘E’] = 0.127
@table[‘T’] = 0.091
@table[‘A’] = 0.082
@table[‘O’] = 0.075
@table[‘I’] = 0.070
@table[‘S’] = 0.063
@table[‘N’] = 0.067
@table[‘H’] = 0.061
@table[‘R’] = 0.060
@table[‘L’] = 0.040
@table[‘C’] = 0.028
@table[‘U’] = 0.028
@table[‘M’] = 0.024
@table[‘W’] = 0.023
@table[‘F’] = 0.022
@table[‘G’] = 0.020
@table[‘P’] = 0.019
@table[‘B’] = 0.015
@table[‘V’] = 0.010
@table[‘K’] = 0.008
@table[‘J’] = 0.002
@table[‘Y’] = 0.002
@table[‘Q’] = 0.001
@table[‘X’] = 0.001
@table[‘Z’] = 0.001
end

def metric(vec1, vec2)
vec = []
vec1.each_index do |index|
vec << [vec1[index], vec2[index]]
end
metr = vec.inject(0) do |sum, item|
sum + (item[0]-item[1]) ** 2
end
Math.sqrt(metr)
end

def to_vector
table = @table.sort.to_a
table.inject([]) do |acc, item|
acc << item[1]
end
end

def distance(other)
metric(self.to_vector, other)
end

end

= Implementation

Approach:

(0 step) Input Morse string is sent to accumulator

(n step) Take first element from accumulator. Separate it in two
parts: head with decoded letters and tail with Morse code.

If tail is not empty:

Find letter representation for first four codes in tail:

  • decode letter if it’s represented by one signal
  • decode letter if it’s represented by two signals (if possible)
  • decode letter if it’s represented by three signals (if possible)
  • decode letter if it’s represented by four signals (if possible)

Construct new strings (no more than 4):

  • previously decoded head plus decoded on this step letter plus
    intact Morse code
    and append them to accumulator

If tail is empty:

Append to output.

== telegraphist.rb

require ‘probability’
require ‘morse’
require ‘enumerator’

class Telegraphist

ALPHABET = ‘ABCDEFGHIJKLMNOPQRTSUVWXYZ’

SILENT mode writes output to file

SILENT = true

def initialize
@probability = Probability.new
@morse = Morse.new
end

def listen
@code = $stdin.gets.chomp
end

def say(words)
if SILENT
File.open(“check.txt”, “w”) do |file|
file.puts words
end
else
$stdout.puts words
end
end

def decode
sort(translate(@code))
end

def translate(text)
txt = text.split(//)
accumulator = [] << txt
result = []
while !accumulator.empty?
element = accumulator.shift
if element.include?(‘.’) or element.include?(‘-’)
head = element.select do |item|
item =~ /\w/
end
tail = element.select do |item|
item =~ /[.-]/
end
if tail.length < 4
iterate = tail.length
else
iterate = 4
end
(1…iterate).each do |index|
letter = @morse[tail[0, index].join]
accumulator << head + [letter] + tail[index, element.length]
if letter
end
else
result << element.join
end
end
result
end

def sort(lines)
lines.sort_by do |line|
@probability.distance(probabilities(line))
end
end

def probabilities(str)
abc = ALPHABET.split(//)
acc = []
abc.each_index do |index|
acc[index] = str.count(abc[index])
end
acc.map do |item|
item / str.length.to_f
end
end

end

= Application

== app.rb

require ‘telegraphist’

operator = Telegraphist.new
operator.listen
operator.say(operator.decode)

9

This is my first solution that I’ve posted (and my first post to
ruby-talk) so please be nice to me, I’m only a newbie.

require ‘rubygems’
gem ‘raspell’
require ‘raspell’

class MCheck
def initialize(message, mmap)
@aspell = Aspell.new
@mmap = mmap
matches(message)
end
def matches(str,s="") #recursively check string for
@mmap.each do |n,o| #every possible letter
if str =~ /^#{n}(.)$/
num = “#{s}#{@mmap[n]}”
if $1 == “”
x = @aspell.check(num) ? "" : " "
puts " #{x} #{num}"
else
matches($1, num)
end
end
end
end
end
MCheck.new(gets.gsub(/[^.-]+/, ‘’), Hash[*“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 --…”.gsub(/(.|-)/, ‘\\\1’).split(/\n| /)].invert) #Escape .
and - for regexx, and create hash

My solution uses aspell, with the raspell ruby bindings, so it might be
a pain to get working, but it’s fairly simple to remove the
spell-checking code. I haven’t checked how efficient this code is, I
think the efficiency of the terminal used at printing out all the
solutions probably has more effect on speed.

Joe

10

#morse code
#a little inefficient, but easy to follow
letters2morse = {“k”=>"-.-", “v”=>"…-", “l”=>".-…", “w”=>".–",
“a”=>".-", “m”=>"–", “x”=>"-…-",
“b”=>"-…", “y”=>"-.–", “c”=>"-.-.",
“n”=>"-.", “z”=>"–…", “d”=>"-…", “o”=>"—",
“e”=>".", “p”=>".–.", “f”=>"…-.",
“q”=>"–.-", “g”=>"–.", “r”=>".-.", “h”=>"…",
“s”=>"…", “i”=>"…", “t”=>"-",
“j”=>".—", “u”=>"…-"}
morse2letters = {}
letters2morse.each_pair do
|letter,morse|
morse2letters.store(morse,letter)
end

#for testing
#stringtoconvert = “Sofia”.downcase
#encodedstring =stringtoconvert.split(’’).collect{|i|
letters2morse[i]}.join

puts “Enter a word in morse code”
encodedstring = gets().gsub(/[^.-]/,’’)#and ignore anything that’s not
morse

#seed the hash. the value of each key is the number of times the word
was found
#just through it may be interesting later on
huge={encodedstring,0}
huge.default=0

#while anything in the hash has non-morse chars
while(huge.keys.join[/[.-]/]!=nil)
huge.keys.each do
|key|
if key[/[.-]/]!=nil
morse2letters.each_pair do
|code,letter|
huge.store(key.sub(code,letter),huge[key.sub(code,letter)]+1)
#for each letter of the alphabet, create a new value by replacing
#the first instance of the letter with it’s morse value, and
insert it
#into the hash.
end
#encoded all possibilities, now delete it.
huge.delete(key)
else
#continuous output when answers are found
#puts key
end
end
end
puts huge.keys.sort

11

OOps, that comment is poorly worded.

On 4/22/07, Kyle S. [email protected] wrote:

#morse code
…
#for each letter of the alphabet, create a new value by replacing
#the first instance of the letter with it’s morse value, and insert it
#into the hash.

For each letter of the morse alphabet, insert a new key by replacing
the first match of that letter-code with the letter.

12

Here is my solution. This appears a lot complex to me. What I am
trying to find is every possible word (or collection of letters) that
can be obtained using the given morse code.

Approach

Given a Morse Code, we insert imaginary vertical bars to separate . and

  • s
    eg. for a given word

…—…

The imaginary vertical bars can be put in any of the following ways
.|…|—.|…
…|—|…
.|.|.|-|-|-|.|.|.

So the problem is essentially to find out all such valid placements of
vertical
bars and output words corresponding to them.

This is done in three steps

  1. Building a hash of all Symbols of length 1,2,3 and 4 in the Input
    Morse Code
  2. Building a list of all tuples of 1,2,3,4, that sum upto the input
    length
  3. Building the words using Symbols in 1. and each tuple in 2. above.

Detailed Explaination

We define a Hash of Morse Code to English Letters.
MORSE_CODE_TABLE = { ‘.-’ => ‘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’ }

Step 1.

A look at Morse code tells that the Morse code for an English Letter can
be
1 symbol
2 symbol
3 symbol
4 symbol

Given the input Morse Code, we find all possible combinations of 1,2,3
and 4 symbols.
Note that for the length ‘N’ of the input, there are
N 1 symbol combinations
N-1 2 symbol combinations
N-3 3 symbol combinations
N-4 4 symbol combinations

For each such combination we lookup the Hash above and enter the letter
corresponding to the combination in another hash (MORSE_ARRAY), whose
keys
are 1, 2, 3, and 4

Thus the Hash for Morse code “…” will look like
[1, [“E”, “E”, “E”, “E”]]
[2, [“I”, “I”, “I”]]
[3, [“S”, “S”]]
[4, [“H”]]

If the symbol for a given combination is missing, we place “nil” there.
This
becomes useful later

Note that the combinations above are at offsets -
0 - N-1 for 1 symbol combination
0 - N-2 for 2 symbol combination
0 - N-3 for 3 symbol combination
0 - N-4 for 4 symbol combination

Step 2.

After we have done this, the problem essentially remains finding all
tuples
containing [1,2,3,4] that sum upto the input length of the Morse Code.
Also
note that sum of the tuples may be invalid (Thos containing “nil” in the
above Hash above.)

The set of these tuples (also as a Hash) can be calculated starting with
0 = [] and 1 = [[1]]

This yields 2 = [ [1,1], [2]]

Three yields 3 = [ [1,1,1], [2,1], [1,2], [3]]

The way this is calculated is as follows

For a given number N, there will be tuples ending with 1, tuples ending
with
2, tuples ending with 3 and tuples ending with 4. Tuples ending with 1
are
nothing but all the tuples of N-1 with a one in the end (Check tuples
for
2 and 3 above). Similarly tuples ending with 2 are all the tuples of
(n-2)
ending with 2 and so on.

Thus a list of all such tuples is calculated.

Step 3.

Now all we have to do is using these tuples and the Hash we obtained
above,
just populate the words ignoring those that contain a nil.

Consider example
…

This can be split into following groups and corrosponding solutions
[1,1,1] => EEE
[1,2] => EI
[2,1] => IE
[3] => S

Spell Check using ‘raspell’

For words in dictionary, I have used ‘raspell’ gem. For each output
word,
if the word is checked using Aspell.check if that returns true, the word
is marked with begining and trailing ‘__’.

Bells and Whistles

A trivial pager is implemented (which just accepts enter), to scroll
down
the list, This is not a fully functional pager at all. One can simply
scroll down but not scroll up and so on.

Finally all the words are stored in a file words.txt, which can be
examined later.

quiz121.rb begins

#!/usr/bin/ruby

require ‘rubygems’
require ‘raspell’

MORSE_CODE_TABLE = { ‘.-’ => ‘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_ARRAY = {}
SOLS = {}

def get_sols (n)
if n == 0
SOLS[n] = []
else
SOLS[n] = []
for i in 1…n-1
SOLS[n-i].each do |j|
if i <=4
SOLS[n].push([j, i].flatten)
end
end
end
SOLS[n].push([n]) if n <= 4
end
end

if FILE == $0

print “Morse >”
val = gets

val.strip!
val.gsub!(/[^.-]*/, ‘’)

First construct the hash for the input Morse Code

for i in 1…4
MORSE_ARRAY[i] = []
for j in 0…(val.length-i)
MORSE_ARRAY[i].push(MORSE_CODE_TABLE[val[j,i]])
end
end

Build a list of all solutions for a number N

whose sum can be calculated using numbers 1,2,3 and 4

This is calculated recursively, starting from 0 to the

length. This can be optimized.

len = val.length
for k in 0…len
get_sols k
end

Generate Words

words = []
SOLS[len].each do |i|
sum = 0 ## This will be used to find the offset in MORSE_ARRAY
w = ‘’
i.each do |l| ## l is one of 1,2,3,4
if MORSE_ARRAY[l][sum]
w << MORSE_ARRAY[l][sum]
sum += l # The length of the MORSE_ARRAY increments by symbol
val
else
break ## We encountered a nil in the MORSE_ARRAY
end
end
if sum == len ## Discards all words with “nil” in MORSE_ARRAY
## (sum will be < len)

  words.push(w) ## Append to the final list

end

end

count = 1 ## For Pager
sp = Aspell.new ## Spell Checking
File.open(‘words.txt’, ‘w’) do |f|
words.each do |w|
if sp.check w
w = w.center(w.length+4, “_”)
p w
else
p w
end
f.write(w + “\n”)
if count%25 == 0
print “–more–”
STDIN.getc
end
count += 1
end
end
end

quiz121.rb ends

On 4/20/07, Ruby Q. [email protected] wrote:

and words, but in written form the code can be ambiguous.

    B -...          O ---
    M --            Z --..

–

अभिजीत

[written in http://www.paahijen.com/scratchpad]

[http://www.paahijen.com]

13

  • O(c^n)?.. :{ (It’s like a non-deterministic finite state
    machine with only one state…)

  • Includes the dictionary words.

  • No state.

How it works? find_words() takes a (partial) word and a
sequence, starting with an empty string and the input sequence.
If “._” could be “shifted” from the sequence, the character “a”
is added to the (partial) word and find_words() is called with
the new (partial) word and the remaining sequence as sequence.
This is done for all characters of the alphabet (iteration) and
all “characters” in the sequence (recursion), until
find_words() receives an empty sequence, in which case the word
is a final word.

[“”, “.–…-…”]
[“a”, “-…-…”]
[“ab”, “.-…”]
[“aba”, “…”]
[“abae”, “…”]
[“abaee”, “.”]
[“abaeee”, “”] ← Final word.
[“abaei”, “”] ← Final word.
[“abai”, “.”]
[“abaie”, “”] ← Final word.

gegroet,
Erik V. - http://www.erikveen.dds.nl/

$ cat morse.rb
class Morse
MORSE_CODES = %w{.- -… -.-. -… . …-. --. … … .—
-.- .-… – -. — .–. --.- .-. … - …- …- .-- -…- -.–
–…}.zip((“a”…“z”).to_a)

DICTIONARY_WORDS = File.open(“/usr/share/dict/words”){|f|
f.read}.downcase.split(/[^a-z]/) rescue nil

def parse(sequence)
real_words(find_words(sequence.gsub(/\s+/, “”)))
end

private

def find_words(sequence, word=“”, results=[])
if sequence.empty?
results << word
else
MORSE_CODES.each do |seq, chr|
if sequence.index(seq) == 0
find_words(sequence[seq.length…-1], word+chr, results)
end
end
end

 results

end

def real_words(words)
words & DICTIONARY_WORDS rescue words
end
end

puts Morse.new.parse($stdin.read)

$ echo “.–…-…” | ruby morse.rb
abets
able
adele
pile
wests

14

Here’s a more practical Morse parser. (Although it’s not part
of the quiz…)

gegroet,
Erik V. - http://www.erikveen.dds.nl/

$ cat morse2.rb
class Morse
MORSE_CODES = %w{.- -… -.-. -… . …-. --. … … .—
-.- .-… – -. — .–. --.- .-. … - …- …- .-- -…- -.–
–…}.zip((“a”…“z”).to_a)

DICTIONARY_WORDS = File.open(“/usr/share/dict/words”){|f|
f.read}.downcase.split(/[^a-z]/) rescue nil

def parse(sequence)
real_words(find_words(sequence.gsub(/\s+/, “”)))
end

private

def find_words(sequence, word=“”, results=[])
if sequence.empty?
results << word
else
MORSE_CODES.each do |seq, chr|
if sequence.index(seq) == 0
find_words(sequence[seq.length…-1], word+chr, results)
end
end
end

 results

end

def real_words(words)
words & DICTIONARY_WORDS rescue words
end
end

puts(
$stdin.read.split(/\r*\n+/).collect do |sequence|
list = Morse.new.parse(sequence)

 case list.length
 when 0      then    "?"
 when 1      then    list[0]
 else                "(#{list.join("|")})"
 end

end.join(" ")
)

$ cat morse.txt
…
… — .–. .
-.-- — …-
.- .-. .
.- -… .-… .

.-. . .- -…

  • … … …
    … . -. - . -. -.-. .

$ ruby morse2.rb < morse.txt
i hope you (al|are|end|rd) (abets|able|adele|pile|wests) to (lad|lane|
read|rune) (nisei|thees|these|this) sentence

15

Well, here’s mine. Not pretty, but seems to do the job, though quite
slowly.
If you pass the script ‘–dict’ after the code string it will
check /usr/share/dict/words for matches (so I guess it will only work on
Unix), and display them at the top of the results. This starts to take a
while with all non-trivial code strings. I was considering an online
dictionary for this, but gave it up after I realised the example given
in the
quiz itself produces over 5000 combinations.

Not much error checking here either…

The code:
############################################
code_key = { “.-” => “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” }

WORDS = []

def recurse(ck, a)
naa = []
a.each do |arr|
4.times do |n|
if parse_chars(arr[2], ck, n+1)
na = [arr[0] + ck.fetch(arr[2][0,n+1]), arr[1]
+ arr[2][0,n+1] + “|”, arr[2][n+1…-1]]
if na[2] == “” or na[2] == nil
WORDS << “#{na[0]} => #{na[1][0…-2]}” if not
WORDS.include?("#{na[0]} => #{na[1][0…-2]}")
else
if not naa.include?(na)
naa << na
end
end
end
end
end
naa
end

def main(w, ck)
wlen = w.length - 1
wa = []
wa << [ck.fetch(w[0,1]), w[0,1] + “|”, w[1…-1]] if parse_chars(w, ck,
1)
wa << [ck.fetch(w[0,2]), w[0,2] + “|”, w[2…-1]] if parse_chars(w, ck,
2)
wa << [ck.fetch(w[0,3]), w[0,3] + “|”, w[3…-1]] if parse_chars(w, ck,
3)
wa << [ck.fetch(w[0,4]), w[0,4] + “|”, w[4…-1]] if parse_chars(w, ck,
4)
wlen.times do |i|
wa = recurse(ck, wa)
end
end

def parse_chars(w, ck, n)
if ck.has_key?(w[0,n])
true
else
false
end
end

word_array = main(ARGV[0], code_key)

if ARGV[1] == “–dict”
a = IO.readlines("/usr/share/dict/words")
WORDS.each do |w|
if a.include?(w[0, w.index(’ ')] + “\n”)
puts w
WORDS.delete(w)
end
end
puts
end

puts WORDS.sort
###################################

-d

16

Ruby Q. [email protected] wrote:

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Technically, I’m not breaking any rules in suggesting that the most
natural language for this problem is Prolog:

m(‘.-’, a). m(‘-…’, b). m(‘-.-.’, c).
m(‘-…’, d). m(‘.’, e). m(‘…-.’, f).
m(‘–.’, g). m(‘…’, h). m(‘…’, i).
m(‘.—’, j). m(‘-.-’, k). m(‘.-…’, l).
m(‘–’, m). m(‘-.’, n). m(‘—’, o).
m(‘.–.’, p). m(‘–.-’, q). m(‘.-.’, r).
m(‘…’, s). m(‘-’, t). m(‘…-’, u).
m(‘…-’, v). m(‘.–’, w). m(‘-…-’, x).
m(‘-.–’, y). m(‘–…’, z).

morse_decode(Text,Translation):-atom_chars(Text,List),
morse_i(List,TranslationList),
atom_chars(Translation,TranslationList).
morse_encode(Text,Translation):-
atom_chars(Translation,TranslationList),
morse_i(List,TranslationList),
atom_chars(Text,List).
morse_i([],[]).
morse_i(List,Translation):-m(First,Letter),atom_chars(First,FirstList),
append(FirstList,RestList,List),Translation=[Letter|RestTrans],
morse_i(RestList,RestTrans).

Examples of use:
morse_decode(‘…—…’,X).
morse_decode(‘…—…’,sos).
morse_encode(X,‘sos’).
morse_encode(‘…—…’,sos).

–Ken B.

17

Here’s my solution. Not much to it. I didn’t do any dictionary
stuff.
Pass -v to see all interpretations printed out. Otherwise, just
number of interpretations printed.

#Author: Matt Hulse
#File : morse.rb
#Email : [email protected]
#Web : http://www.matt-hulse.com

class Morse

attr_reader :morse_code, :message, :result

def initialize(message)
@morse_code = { :A => ‘.-’, :B => ‘-…’, :C => ‘-.-.’,
:smiley: => ‘-…’, :E => ‘.’, :F => ‘…-.’, :G => ‘–.’,
:H => ‘…’, :I => ‘…’, :J => ‘.—’, :K => ‘-.-’,
:L => ‘.-…’, :M => ‘–’, :N => ‘-.’, :open_mouth: => ‘—’,
:stuck_out_tongue: => ‘.–.’, :Q => ‘–.-’, :R => ‘.-.’, :S => ‘…’,
:T => ‘-’, :U => ‘…-’, :V => ‘…-’, :W => ‘.–’,
:X => ‘-…-’, :Y => ‘-.–’, :Z => ‘–…’
}
@message = message
end

def translate
@result = do_translation(@message).flatten
puts “Translation Complete”
puts “#{@result.length} interpretations found.”
end

def do_translation(str)
result = Array.new

(1..4).each{|n|
  morse = str[0,n]
  this_char = decode(morse)
  if(this_char.nil?) then
    puts "Invalid char, skipping to next" if $DEBUG
    next
  else
    #is a valid character
    if(n == str.size)
      result << this_char
    elsif(n < str.size)
      result << do_translation(str[n,str.size]).flatten.collect{|c|
        this_char + c
      }
    end
  end
}

return result

end

def encode(char)
encoded = “”
if(char.size > 1) then
char.split(“”).each{|letter|
encoded += encode(letter) + “|”
}
encoded.chop!
else
result = @morse_code.find{|key,value| key == char.to_sym}
if(result.nil?)
return nil
else
encoded = result[1].to_s
end
end

encoded

end

def decode(morse)
result = @morse_code.find{|key,value| value == morse}
if (not result.nil?) then
result[0].to_s
else
return nil
end
end

def show_result
@result.each{|res|
printf(“#{encode(res)}%25s\n”,res)
}
end
end

if FILE == $0 then

code = ARGV[0] ||= “…—…-…-”

morse = Morse.new(code)
morse.translate
morse.show_result if $VERBOSE
end

Matt Hulse
[email protected]
http://www.matt-hulse.com

18

Hey! I’m internet famous! For some reason, I was sure there was a
backlog of suggestions and mine wouldn’t come up for a while, if at
all. Imagine my surprise when it was the very next quiz.

The reason I suggested this is because I wrote it myself about a year
ago (albeit in Perl, my main quick language at the time) in order to
help with a puzzle in Games magazine. I then promptly forgot about
its existence until recently, when I was reading up on the Ruby Q…
It wasn’t hard to figure out what to do next.

My own solution follows, ported from my original Perl. The algorithm
hasn’t been changed, mostly just converted. It’s not very quick or
efficient (or elegant), but it works. Basically I create a trie
(using nested hashes) of the possibilities and then flatten it down to
a single level.

class String

class << self
def morse_code_hash=(new_val)
@@morse_code_hash = new_val
end

def morse_code_hash
  @@morse_code_hash
end

end

def morsecode_possibilities
raise “#{self} is not valid morse code” if self.match(/[^-.]/)

@tree = get_tree

@possibilities = @tree.flatten.keys.sort

end

def get_tree
starts = @@morse_code_hash.keys.select { |k| self.match(/
^#{Regexp.escape(k)}/) }

tree = {}

starts.each do |start|
  tree[ @@morse_code_hash[start] ] = self[start.length ..

-1].get_tree
end

tree

end

end

class Hash
def flatten
tmp = {}
each do |key, val|
tmp[key] = val
if val.is_a?(Hash)
val.keys.each do |subkey|
tmp["#{key}#{subkey}"] = val[subkey]
end
tmp.delete(key) unless val.empty?
end
end
tmp = tmp.flatten while tmp.values.any? { |v| !v.empty? }
tmp
end
end

codehash = {
‘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’ => ‘–…’
}

String.morse_code_hash = codehash.invert

code = (ARGV.first || ‘’).chomp

exit if code.empty?

puts “Getting possibilities for ‘#{code}’:”

puts code.morsecode_possibilities.join("\n")

19

On 4/20/07, Ruby Q. [email protected] wrote:

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.

Here’s my solution. It takes one or more code words from ARGV, and
takes an optional -d argument to use a dictionary file to filter
results.

RubyQuiz 121 submission

Bob S.

set to dictionary file to load

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 --…
/]

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

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

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)
end

20

Here’s my solution: it implements two optional extensions.

morse.rb [-d dictionary] [-m] [morse-sequence]

The -d option names a file that is a dictionary, one word per line.
If given, results will be limited to words in that file. The -m
option (“multi”) causes it to read lines from standard input until
EOF, and perform the Morse->English expansion on each line. If the
morse sequence isn’t given as the first argument, it reads a single
line from standard input. (That is, with no arguments or options, it
behaves as the quiz spec said it should)

Also, I allow spaces in the morse code sequence to force a letter
break at that point. For example “.- .” produces only “AE” and “ETE”,
whereas “.-.” produces those two results plus “EN” and “R”.

Without further ado:

#!ruby -x

Copied from quiz description, with a regexp search/replace that

my editor (SciTE) made easy to do:

MORSE = [
%w{A .-}, %w{N -.},
%w{B -…}, %w{O —},
%w{C -.-.}, %w{P .–.},
%w{D -…}, %w{Q --.-},
%w{E .}, %w{R .-.},
%w{F …-.}, %w{S …},
%w{G --.}, %w{T -},
%w{H …}, %w{U …-},
%w{I …}, %w{V …-},
%w{J .—}, %w{W .–},
%w{K -.-}, %w{X -…-},
%w{L .-…}, %w{Y -.–},
%w{M --}, %w{Z --…},
].map {|c, morse| [c, /^#{Regexp.escape(morse)} ?(.*)/]}.sort;

Given a morse-code input string, yield the initial letter we

could be starting with and the rest of the morse code string.

def get_letters(instr)
MORSE.each { |c, re|
if (instr =~ re) then
yield c,$1
end
}
end

Generate all possible decodings of the given morse code string.

The algorithm’s pretty simple - the only twist is storing the

intermediate results in a hash so that they don’t get calculated

more than once.

def gencode(instr)
memoizer = Hash.new { |h,morse|
retval = []
get_letters(morse) { |c,rest|
h[rest].each {|s| retval << (c+s)}
}
h[morse] = retval
}
memoizer[’’] = [’’]
memoizer[instr]
end

And that’s it as far as the fundamental algorithm is concerned.

The rest is all option handling and dictionary filtering

$dictfunc = lambda {|x| 1}
$opt_m = nil
$usage = “morse.rb [-d dictionary] [-m] [codestring]”

while ARGV[0] and ARGV[0] =~ /^-/ do
case ARGV[0]
when /^-d/
dictionary = {}
File.open(ARGV[1]) { |f| f.each { |w|
w.chomp!.upcase!.strip!
dictionary[w] = 1
} }
$dictfunc = lambda {|x| dictionary[x]}
ARGV.shift
when /^-m/
$opt_m = 1
else
STDERR.puts “Unknown option #{ARGV[0]}”
STDERR.puts $usage
exit 1
end
ARGV.shift
end

if ARGV[0] then
if ARGV[1] then
STDERR.puts $usage
exit 1
end
gencode(ARGV[0]).select{|w|$dictfunc.call(w)}.each{|w| puts w}
exit 0 unless $opt_m
end

STDIN.each do |l|
gencode(l).select{|w|$dictfunc.call(w)}.each{|w| puts w}
exit 0 unless $opt_m
end
END