[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Fwd: [QUIZ] Morse Code (#121

James Gray

4/22/2007 6:04:00 PM

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

Ball, Donald A Jr (Library)

4/22/2007 6:12:00 PM

0

Below is my first solution to this quiz.

http://pastie.cabo...

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

Ball, Donald A Jr (Library)

4/22/2007 7:02:00 PM

0

Below is my second solution.

http://pastie.cabo...

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

James Barnett

4/22/2007 10:07:00 PM

0

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/dict...
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)" : "" }" }

Bob Showalter

4/22/2007 10:14:00 PM

0

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}

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.

Ball, Donald A Jr (Library)

4/23/2007 2:35:00 AM

0

> 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

James Gray

4/23/2007 1:17:00 PM

0

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?

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

James Gray

4/23/2007 1:28:00 PM

0

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.

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

Jesús Gabriel y Galán

4/23/2007 1:41:00 PM

0

On 4/23/07, James Edward Gray II <james@grayproductions.net> wrote:
> >> 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.