[QUIZ] Morse Code (#121)

[Christian_Neukirche1 (Christian Neukirchen)]

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

···

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

[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[i]}.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

[Erik_Veenstra1 (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

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

[CHubas]

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

···

On Apr 23, 12:32 am, CHubas <CHub...@gmail.com> wrote:

Here is my entry

http://pastie.caboo.se/55821

[James_Edward_Gray_II]

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

James Edward Gray II

···

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

This is my first rubyquiz as well.

[James_Edward_Gray_II]

Two simple things I noticed:

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

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

Just some thoughts.

Welcome to Ruby Quiz.

James Edward Gray II

···

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

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

[Jesse_Merriman]

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.

···

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

[John_W_Kennedy]

Ken Bloom wrote:

···

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!

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

I don't even know Prolog, and I can see that your code is horribly broken.
--
John W. Kennedy
"Only an idiot fights a war on two fronts. Only the heir to the throne of the kingdom of idiots would fight a war on twelve fronts"
  -- J. Michael Straczynski. "Babylon 5", "Ceremonies of Light and Dark"
* TagZilla 0.066 * http://tagzilla.mozdev.org

[7stud2 (7stud --)]

Christian Theil Have 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" => "--.."
    }

···

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

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

···

On 4/22/07, Kyle Schmitt <kyleaschmitt@gmail.com> wrote:

[Colin_A_Bartlett]

# 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

[Paul_Novak]

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],"")