[QUIZ] Morse Code (#121)

[James_Edward_Gray_II]

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

···

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

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

[Harry4 (Harry)]

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

···

On 4/20/07, Ruby Quiz <james@grayproductions.net> 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.

#####

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

--

Kakueki.com is for sale | HugeDomains

A Look into Japanese Ruby List in English

[Gareth_Adams]

Ruby Quiz <james <at> 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

[Christian_Theil_Have]

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

[Carl_Porth]

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 Porth

[Jesse_Merriman]

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

···

--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/

[Drew_Olson]

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 Olson

# the train method is based on this rubytalk post:
# http://www.ruby-forum.com/topic/104327#new

···

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

--
Posted via http://www.ruby-forum.com/.

[I_P]

Ruby Quiz|

Straightforward and memory-greedy solution.

= Tables

== table.rb

# An interface to subsequent tables

class Table
  
  def initialize
    @table = {}
    compose
  end
  
  def compose
  end
    
  def (value)
    @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)

···

--
I. P. 2007-04-22T17:09

[Joseph_Seaton]

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

[Abhijit_Gadgil]

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 Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

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

--

अभिजीत

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

[http://www.paahijen.com]

[Erik_Veenstra1 (Erik Veenstra)]

* 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

----------------------------------------------------------------

[Matt_Hulse]

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 : matt.hulse@gmail.com
#Web : http://www.matt-hulse.com

class Morse

  attr_reader :morse_code, :message, :result

  def initialize(message)
    @morse_code = { :A => '.-', :B => '-...', :C => '-.-.',
      :D => '-..', :E => '.', :F => '..-.', :G => '--.',
      :H => '....', :I => '..', :J => '.---', :K => '-.-',
      :L => '.-..', :M => '--', :N => '-.', => '---',
      :P => '.--.', :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
matt.hulse@gmail.com
http://www.matt-hulse.com

···

On Apr 20, 6:15 am, Ruby Quiz <j...@grayproductions.net> wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

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

[darren_kirby]

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
--
darren kirby :: Part of the problem since 1976 :: http://badcomputer.org
"...the number of UNIX installations has grown to 10, with more expected..."
- Dennis Ritchie and Ken Thompson, June 1972

[Ken_Bloom]

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 Bloom

···

Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

[Bob_Showalter1 (Bob Showalter)]

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 Showalter

# 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

···

On 4/20/07, Ruby Quiz <james@grayproductions.net> 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.

[Yossef_Mendelssohn]

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 Quiz.
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")

[Daniel_Martin]

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__

···

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]

[Bob_Lisbonne]

This is my first Ruby Quiz. I am relatively new to ruby, but have known morse code for a few years.
Mine is a simple recursive algorithm using a regexp to match possibilities.
I didn't bother adding the dictionary, or validating the user input, primarily because I liked the brevity of the solution below.
I'd welcome any suggestion for making it more ruby-like.
thanks,
/Bob Lisbonne

#!/usr/bin/env ruby -w
class Morse
@@cw = {'.-' => '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(dotsanddashes)
  parse(dotsanddashes,"")
end
def parse(dotsanddashes,letters)
  if dotsanddashes.size == 0 then
      puts letters
      return
  end
  @@cw.keys.each {|try|
    if /^#{try.gsub(/\./,'\.')}/.match(dotsanddashes) then
      parse(dotsanddashes[$&.size,dotsanddashes.size],letters + @@cw[$&])
    end
  }
end #parse
end #Morse
Morse.new(STDIN.read.chomp)

···

On Apr 20, 2007, at 5:15 AM, Ruby Quiz wrote:

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

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

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

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

[CHubas]

$ ruby quiz121.rb -m 4
Opening dictionary...
Dictionary loaded!

Type a morse sequence to find all possible words. Type 'done' to exit
.-...--...-.----.-..-..--...-...-.-......

ruby quiz rules
ruby quiz rite ties
....
Combinations found: 635

This quiz certainly kept me entertained, I should be doing school
things @.@ Worth it.
Here is my solution. When it loads the dictionary words, stores them
in a hash whose key is the morse representation, and the value is an
array with all possible words.

I used a dictionary at Download 12dicts-4.0.zip (SCOWL (and friends))

Here is my entry

http://pastie.caboo.se/55821

···

On Apr 20, 7:15 am, Ruby Quiz <j...@grayproductions.net> wrote:

The three rules of Ruby Quiz:

[Bob_Lisbonne]

Here is a second, cleaned up version of my posting which benefits from James Edward Gray's fine suggestions.
thanks,
/Bob

#!/usr/bin/env ruby -w
CW = {'.-'=>'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 morse(dotsanddashes,letters)
  if dotsanddashes.empty? then
    puts letters
  else
    CW.keys.each do |try|
      if /^#{Regexp.escape(try)}/.match(dotsanddashes) then
        morse(dotsanddashes[$&.size,dotsanddashes.size],letters+ CW[$&])
      end
    end
  end
end #morse
morse(STDIN.read.chomp,'')