[QUIZ] Morse Code (#121)

ruby-talk
1

From: "Jesús Gabriel y Galán" <jgabrielygalan@gmail.com>
Date: April 21, 2007 5:01:15 PM CDT
To: james@grayproductions.net
Subject: Re: [QUIZ] Morse Code (#121)

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

Hi James, I'm not sure when the 48 hours expire, but as tomorrow I will not
be able to access email and I wanted to send as early as possible I would
appreciate if you could forward my "solution" as soon as you see fit.

I say "solution" since it's late here (I'm in Spain) and I'm tired, so I haven't
made formal tests, just some manual tests and I think it's correct.

Sorry if this is not appropriate, as this is my first try at Ruby Quiz
and my first post to ruby-talk :-).

Also, I'm fairly new to Ruby, only programming little things to learn,
but nothing serious. So I'd appreciate any feedback you have on my
Ruby. For example I had a little of hard time to get the dups right,
because I was always storing the same string so other iterations were
modifying the same object: hope I have it right !!

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.

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

OK. So here's my solution. I just start slicing characters from the
begining of the input to check all the combinations that match with a
letter, then try everything that can match the starting of the rest,
etc, until there's no rest to match. I have stored the mapping between
Morse characters and the letters in a hash to look them up easily:

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"}

input = ARGV[0]
# Start a queue with the empty translation and the input as rest to translate
queue = [["", input]]

# Calculate the min and max length of the keys to
# slice from the rest to translate only from min to max
sorted_keys = letters.keys.sort_by {|x| x.length}
min_length = sorted_keys[0].length
max_length = sorted_keys[-1].length

answers =

while (!queue.empty?) do
  process = queue.shift
  translation = process[0]
  rest = process[1]
  # Try to slice from the min key length to the max key length
  # but not more than the resting length
  up_to = (max_length < rest.length ? max_length : rest.length)
  min_length.upto(up_to) do |length|
    current_rest = rest.dup
    current_translation = translation.dup
    # Get the first characters from the rest that may form a letter
    next_morse = current_rest.slice!(0..length-1)
    letter = letters[next_morse]
    if (letter)
      # If there is a letter corresponding to those characters add it
      # to the translation
      current_translation << letter
      # If there's nothing left to translate we have an answer
      if (current_rest.empty?)
        answers << current_translation
      # Else add what's left to translate to the queue
      else
        queue << [current_translation, current_rest]
      end
    end
  end
end

puts answers
-------------------------------

Thanks.

Jesus Gabriel y Galan.

···

Begin forwarded message:

On 4/20/07, Ruby Quiz <james@grayproductions.net> wrote:

2

Below is my first solution to this quiz.

http://pastie.caboo.se/55736

- donald

# Ruby Quiz 121
# Donald A. Ball Jr.
# Version 1.0
class Morse

  CODES = {
    :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 => '--..'
  }

  LETTERS = CODES.invert

  def self.translate(cipher)
    results = []
    LETTERS.each_pair do |code, letter|
      next unless cipher.slice(0, code.length) == code
      if cipher.length == code.length
        results << letter.to_s
      else
        translate(cipher.slice(code.length, cipher.length)).each do |result|
          results << (letter.to_s << result)
        end
      end
    end
    results
  end

end

Morse.translate(ARGV[0]).each{|word| puts word}

3

Some minor suggestions:

* Drop the parentheses on if/while statement conditions
* while !queue.empty? could be until queue.empty?
* This bit of code:

sorted_keys = letters.keys.sort_by {|x| x.length}
min_length = sorted_keys[0].length
max_length = sorted_keys[-1].length

could be:

min_length = letters.keys.min {|a,b| a.length <=> b.length }
max_length = letters.keys.max {|a,b| a.length <=> b.length }

or:

min_length, max_length = letters.keys.sort_by {|x| x.length}.values_at(0, -1)

Just some thoughts.

Welcome to Ruby.

James Edward Gray II

···

On Apr 22, 2007, at 1:03 PM, James Edward Gray II wrote:

Begin forwarded message:

From: "Jesús Gabriel y Galán" <jgabrielygalan@gmail.com>
Date: April 21, 2007 5:01:15 PM CDT
To: james@grayproductions.net
Subject: Re: [QUIZ] Morse Code (#121)

Also, I'm fairly new to Ruby, only programming little things to learn,
but nothing serious. So I'd appreciate any feedback you have on my
Ruby.

4

Below is my second solution.

http://pastie.caboo.se/55742

- donald

# Ruby Quiz 121
# Donald A. Ball Jr.
# Version 1.1
class String
  def split_at(index)
    [slice(0, index), slice(index, length)]
  end
end

class Morse

  CODES = {
    :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 self.decipher(cipher)
    CODES.each_pair do |letter, code|
      prefix, suffix = cipher.split_at(code.length)
      next unless prefix == code
      if suffix == ''
        yield letter.to_s
      else
        decipher(suffix) {|result| yield letter.to_s << result }
      end
    end
  end

end

Morse.decipher(ARGV[0]) {|word| puts word}

5

>> From: "Jesús Gabriel y Galán" <jgabrielygalan@gmail.com>

* This bit of code:
sorted_keys = letters.keys.sort_by {|x| x.length}
min_length = sorted_keys[0].length
max_length = sorted_keys[-1].length

could be:

min_length = letters.keys.min {|a,b| a.length <=> b.length }
max_length = letters.keys.max {|a,b| a.length <=> b.length }

or:

min_length, max_length = letters.keys.sort_by {|x| x.length}.values_at
(0, -1)

Just some thoughts.

In fact, I have done a modification to my version, to generalize that
thing: instead of assuming we have keys from min to max I actually get
an array with all the possible key lengths with:

key_lengths = letters.keys.map {|x| x.length}.uniq

and then modify the min_length.upto(up_to) with key_lengths.each

which optimizes the loop for arbitrary key lengths... but haven't been
able to test my code yet.

Welcome to Ruby.

Thanks, I'm in complete love with the language, and the community is
great. Ruby Quiz is a great tool to learn.

Jesus.

···

On 4/23/07, James Edward Gray II <james@grayproductions.net> wrote:

6

Here's my solution to Ruby Quiz #121.

Jim Barnett

#!/usr/bin/env ruby

class MorseCode
  attr_accessor :results
  attr_reader :words

  Alphabet = {
    '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
    @results = []
    @words = []
    @words << load_dictionary
  end

  def to_text(input, output = "", words = @words)
    unless input.empty?
      m = matches(input)
      m.each do |char|
        to_text(input[Alphabet[char].length, input.length], output +
char)
      end
    else
      @results << output
    end
  end

  def matches(input)
    Alphabet.select { |key, value| input[0, value.length] ==
value }.map { |v| v.first }.sort
  end

  def load_dictionary
    # dictionary.txt from http://java.sun.com/docs/books/tutorial/collections/interfaces/examples/dictionary.txt
    File.open("dictionary.txt", "r") do |file|
      file.each_line do |line|
        @words << line.chomp.upcase if line
      end
    end
    @words << 'SOFIA'
    @words << 'EUGENIA'
  end

  def in_dictionary?(str)
    @words.include?(str)
  end
end

$mc = MorseCode.new
$mc.to_text(ARGV[0])
$mc.results.each { |r| puts "#{r} #{ $mc.in_dictionary?(r) ? "(in
dictionary)" : "" }" }

7

That's pretty much what I did (as well as some others) but yours is
much more elegant. I didn't really think about using a block with the
recursion. Cool.

···

On 4/22/07, Ball, Donald A Jr (Library) <donald.ball@nashville.gov> wrote:

...
  def self.decipher(cipher)
    CODES.each_pair do |letter, code|
      prefix, suffix = cipher.split_at(code.length)
      next unless prefix == code
      if suffix == ''
        yield letter.to_s
      else
        decipher(suffix) {|result| yield letter.to_s << result }
      end
    end
  end

end

Morse.decipher(ARGV[0]) {|word| puts word}

8

That's pretty much what I did (as well as some others) but yours is
much more elegant. I didn't really think about using a block with the
recursion. Cool.

Thanks. That's actually the first time I've written code that yields. It's actually bit unclear to me as to when it's better to return results and when it's better to yield them. I guess the best thing to do would be to check, what is it, block_given? and either yield or collect the results as appropriate. Do more advanced rubyists have any guidance to offer in this regard?

- donald

9

I prefer to yield whenever you don't need a full set of results to do something useful. This means I don't have to aggregate results, which saves memory. It also means the calling code gets answers as soon as they are available. Plus, if that calling code really wanted to fill an Array with the results they can certainly do that. Basically, it gives the caller more choices.

James Edward Gray II

···

On Apr 22, 2007, at 9:35 PM, Ball, Donald A Jr (Library) wrote:

That's pretty much what I did (as well as some others) but yours is
much more elegant. I didn't really think about using a block with the
recursion. Cool.

Thanks. That's actually the first time I've written code that yields. It's actually bit unclear to me as to when it's better to return results and when it's better to yield them. I guess the best thing to do would be to check, what is it, block_given? and either yield or collect the results as appropriate. Do more advanced rubyists have any guidance to offer in this regard?