Morse Code (#121)

Ruby
21

This is my first Ruby Q… I am relatively new to ruby, but have
known morse code for a few years. :slight_smile:
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)

22

On Apr 20, 7:15 am, Ruby Q. [email protected] wrote:

The three rules of Ruby Q.:

$ 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
http://prdownloads.sourceforge.net/wordlist/12dicts-4.0.zip

Here is my entry :smiley:

http://pastie.caboo.se/55821

23

On Apr 23, 12:32 am, CHubas [email protected] wrote:

Here is my entry :smiley:

Parked at Loopia

Uh, sorry for the double posting, I found a little error at line 54.
There is an uninvited statement (Ctrl-V error) xP
Wanted to point that, and also trying to not to use another pastie.

Thanks

Ruben

24

My first Ruby quiz. Been toying with Ruby for 6 months

or so now. I’m looking forward to seeing how others

who are more experieced handle this problem. No extra

credit for me this week as I didn’t do any dictionary

lookups. -Colin

Just for formatting the output later

LINE = “----------------------------------------------------”

The codes, as pasted from the RubyQuiz site

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

I found it easier to put them in opposite of how I was

really going to use them so here I flip-flop the hash

@index = codes.invert

Grab the morse code from the command line

code_string = ARGV[0]

Sets up an array to plunk our answers into

@answers = []

A method that takes a two-item array of values:

First - the letters of the answer so far

Last - the remaining dots and dashes to translate

def translate(answer)

Cycle through the various possible lengths of the

letters. Since they can only be 4 chrs long, we

stop at 4.

(1…4).each do |n|
# for each letter / morse code pair
@index.each_pair do |k,v|
# If first (1, 2, 3, or 4) letters in the part
# remaining to be translated are the same as a
# morse code letter…
if answer[1][0,n] == k
new_answer = [
# Build an array that has the original part
# already translated…
answer[0] + v,
# And the remaining part to translate with
# the part we just translated lobbed off.
answer[1].sub(k, ‘’)
]
if new_answer[1] == “”
# If we’ve translated the whole word, then
# add it into our final aray of possibilities.
@answers << new_answer[0]
else
# Otherwise, pass what we’ve got back to this
# same method and keep translating.
translate new_answer
end
end
end
end
end

translate(["",code_string])

puts LINE
puts "The morse code you entered was: " + code_string
puts LINE
puts “The possible translations are:”
puts LINE

I dunno how but I ended up with some non-unique answers.

No matter, the uniq method makes quick work of that.

puts unique = @answers.uniq.sort
puts LINE
puts "Total possible answers: " + unique.length.to_s

25

On Apr 23, 2007, at 12:20 AM, Bob Lisbonne wrote:

I’d welcome any suggestion for making it more ruby-like.

Two simple things I noticed:

dotsanddashes.size == 0 # => dotsanddashes.empty?

try.gsub(/./,’.’) # => Regexp.escape(try)

Just some thoughts.

Welcome to Ruby Q…

James Edward G. II

26

Thanks for another fun rubyquiz!

I don’t think my solution has any unusual features, but I love it that
I could directly paste the mappings in from the problem description!

Regards,

Paul

#!/usr/bin/ruby

a lazy way to convert pasted-on text from problem into a Hash

$morse = 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 --… }]

convert dashes and dots to regexen to match each code at beginning

of line

gotta love it when Ruby let’s you convert documentation to code!

$morse.each_pair { |k,v| $morse[k] = Regexp.new("^(%s)(.*)" %
Regexp.escape(v))}

def parse(code, parsed_so_far)
if code==""
p parsed_so_far
else
$morse.each_pair do |k,v|
m = v.match( code).to_a
if m.length>0
parse(m[2], parsed_so_far + k)
end
end
end
end

parse(ARGV[0],"")

27

On Apr 22, 2007, at 8:35 AM, Drew O. wrote:

This is my first rubyquiz as well.

Just wanted to say a quick welcome to all the new faces. Glad you
decided to join us.

James Edward G. II

28

Here is a second, cleaned up version of my posting which benefits
from James Edward G.'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,’’)

29

Ruby Q. [email protected] writes:

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.

This is my solution with the Morse code passed as argument; you can
enable a directory by passing -d.

It uses simple recursion.

#!ruby -s

$morse = Hash[*%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 --…
}].invert

if $d
words = {}
File.readlines(“/usr/share/dict/words”).each { |word|
words[word.downcase.chomp] = true
}
end

def allmorse(s, t=“”, &b)
if s.empty?
yield t
else
1.upto(s.size) { |n|
$morse[s[0,n]] && allmorse(s[n…-1], t+$morse[s[0,n]], &b)
}
end
end

allmorse (ARGV[0] || “.-…–…-.–”).delete(“^.-”) do |word|
puts word if !$d || words.include?(word.downcase)
end

END

Example:

$ ruby quiz121.rb
ETEEETTEEETETT
ETEEETTEEETEM
ETEEETTEEETAT
ETEEETTEEETW
ETEEETTEEENTT
: : : :
LPUW
LPFTT
LPFM

$ ruby quiz121.rb -d
RUBY

$ ruby quiz121.rb -d …/./.-…/.-…/—
HELLO

30

Here’s a slight optimization to the each_translation method in my
original
submission:

class String

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

def each_translation
split(//).each_grouping(MinCodeLength, MaxCodeLength) do |group|
valid = true
group.map! do |char_arr|
# Convert arrays of individual dots & dashes to strings, then
translate.
letter = Decode[char_arr.join]
letter.nil? ? (valid = false; break) : letter
end
# Join all the translated letters into one string.
yield group.join if valid
end
end
end

Originally, I would translate every letter in a word, and then throw it
out if
any failed to translate. This version breaks out of the map! as soon as
any
letter fails, at the expense of two more variables and a few more LOC. I
expected this to speed it up quite a bit, but this test data shows only
a
minor improvement for short code strings:

(All times in seconds)

Length, Original Time, New Time

0 0.112 0.113
1 0.110 0.109
2 0.106 0.108
3 0.106 0.106
4 0.106 0.106
5 0.108 0.107
6 0.121 0.119
7 0.123 0.121
8 0.125 0.124
9 0.132 0.130
10 0.146 0.145
11 0.188 0.187
12 0.259 0.253
13 0.403 0.390
14 0.713 0.668
15 1.313 1.221
16 2.513 2.342
17 4.959 4.597
18 9.885 9.146
19 19.671 18.208
20 38.729 35.972
21 78.767 71.431
22 159.931 145.794
23 319.763 294.711
24 636.660 590.360
25 1273.474 1169.021

These were all run with prefixes of ‘…—…-…–.–.-…-.’
The percentage improvement increases as the length of the code to
translate
increases, as can be seen in this (noisy) plot:

http://www.jessemerriman.com/images/ruby_quiz/121_morse_code/new_vs_old.png

How far it goes down after that, I don’t know, but my guess would be
that
eventually it’d approach zero.

31

Ken B. wrote:

  1. Enjoy!
    m(’…’, s). m(’-’, t). m(’…-’, u).
    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).

I don’t even know Prolog, and I can see that your code is horribly
broken.

32

Christian Theil H. wrote in post #237067:

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

Thanks, this was useful. You were missing an “n”, I fixed it for you:

@@alpha = {
“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” => “–…”
}