[QUIZ] Morse Code (#121)

R

Ruby Quiz

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

Harry Mathews

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

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
 
J

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
 
D

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
 
I

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

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
 
K

Kyle Schmitt

#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}.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
 
K

Kyle Schmitt

OOps, that comment is poorly worded.


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

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

----------------------------------------------------------------
 
E

Erik Veenstra

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

----------------------------------------------------------------
 
M

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 : (e-mail address removed)
#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 => '-.', :O => '---',
: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
(e-mail address removed)
http://www.matt-hulse.com





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

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
 
K

Ken Bloom

Ruby Quiz said:
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!

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
 
B

Bob Showalter

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

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")
 
D

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__
 
B

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)




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

CHubas

The three rules of Ruby Quiz:

$ 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 :D

http://pastie.caboo.se/55821
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top