Re: [QUIZ] Morse Code (#121)

Here is my solution. This appears a lot complex to me. What I amtrying to find is every possible word (or collection of letters) thatcan be obtained using the given morse code.
Approach
Given a Morse Code, we insert imaginary vertical bars to separate . and - seg. for a given word
...---...
The imaginary vertical bars can be put in any of the following ways.|..|---.|.....|---|....|.|.|-|-|-|.|.|.
So the problem is essentially to find out all such valid placements of verticalbars and output words corresponding to them.
This is done in three steps
1. Building a hash of all Symbols of length 1,2,3 and 4 in the Input Morse Code2. Building a list of all tuples of 1,2,3,4, that sum upto the input length3. Building the words using Symbols in 1. and each tuple in 2. above.
Detailed Explaination=====================
We define a Hash of Morse Code to English Letters.MORSE_CODE_TABLE = { '.-' => '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' }

Step 1.-------A look at Morse code tells that the Morse code for an English Letter can be 1 symbol 2 symbol 3 symbol 4 symbol
Given the input Morse Code, we find all possible combinations of 1,2,3and 4 symbols.Note that for the length 'N' of the input, there are  N   1 symbol combinations  N-1 2 symbol combinations  N-3 3 symbol combinations  N-4 4 symbol combinations
For each such combination we lookup the Hash above and enter the lettercorresponding to the combination in another hash (MORSE_ARRAY), whose keysare 1, 2, 3, and 4
Thus the Hash for Morse code "...." will look like[1, ["E", "E", "E", "E"]][2, ["I", "I", "I"]][3, ["S", "S"]][4, ["H"]]
If the symbol for a given combination is missing, we place "nil" there. Thisbecomes useful later
Note that the combinations above are at offsets -  0 - N-1 for 1 symbol combination  0 - N-2 for 2 symbol combination  0 - N-3 for 3 symbol combination  0 - N-4 for 4 symbol combination
Step 2.-------After we have done this, the problem essentially remains finding all tuplescontaining [1,2,3,4] that sum upto the input length of the Morse Code. Alsonote that sum of the tuples may be invalid (Thos containing "nil" in theabove Hash above.)
The set of these tuples (also as a Hash) can be calculated starting with0 = [] and 1 = [[1]]
This yields 2 = [ [1,1], [2]]
Three yields 3 = [ [1,1,1], [2,1], [1,2], [3]]

The way this is calculated is as follows
For a given number N, there will be tuples ending with 1, tuples ending with2, tuples ending with 3 and tuples ending with 4. Tuples ending with 1 arenothing but all the tuples of N-1 with a one in the end (Check tuples for2 and 3 above). Similarly tuples ending with 2 are all the tuples of (n-2)ending with 2 and so on.
Thus a list of all such tuples is calculated.

Step 3.-------Now all we have to do is using these tuples and the Hash we obtained above,just populate the words  ignoring those that contain a nil.
Consider example...
This can be split into following groups and corrosponding solutions[1,1,1] => EEE[1,2]   => EI[2,1]   => IE[3]     => S
Spell Check using 'raspell'---------------------------For words in dictionary, I have used 'raspell' gem. For each output word,if the word is checked using Aspell.check if that returns true, the wordis marked with begining and trailing '__'.
Bells and Whistles------------------A trivial pager is implemented (which just accepts enter), to scroll downthe list, This is not a fully functional pager at all. One can simplyscroll down but not scroll up and so on.
Finally all the words are stored in a file words.txt, which can beexamined later.
quiz121.rb begins------------------------------------------------------------------------------------------------------#!/usr/bin/ruby

require 'rubygems'require 'raspell'
MORSE_CODE_TABLE = { '.-' => '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' }
MORSE_ARRAY = {}SOLS = {}
def get_sols (n)    if n == 0      SOLS[n] = []    else      SOLS[n] = []      for i in 1..n-1        SOLS[n-i].each do |j|          if i <=4            SOLS[n].push([j, i].flatten)          end        end      end      SOLS[n].push([n]) if n <= 4    endend
if __FILE__ == $0
  print "Morse >"  val = gets
  val.strip!  val.gsub!(/[^.-]*/, '')
  ###  # First construct the hash for the input Morse Code  ###  for i in 1..4    MORSE_ARRAY[i] = []    for j in 0..(val.length-i)      MORSE_ARRAY[i].push(MORSE_CODE_TABLE[val[j,i]])    end  end
  ###  # Build a list of all solutions for a number N  # whose sum can be calculated using numbers 1,2,3 and 4  #  # This is calculated recursively, starting from 0 to the  # length. This can be optimized.  ###  len = val.length  for k in 0..len    get_sols k  end
  ###  # Generate Words  ###  words = []  SOLS[len].each do |i|    sum = 0 ## This will be used to find the offset in MORSE_ARRAY    w = ''    i.each do |l| ## l is one of 1,2,3,4      if MORSE_ARRAY[l][sum]        w << MORSE_ARRAY[l][sum]        sum += l # The length of the MORSE_ARRAY increments by symbol val      else        break   ## We encountered a nil in the MORSE_ARRAY      end    end    if sum == len  ## Discards all words with "nil" in MORSE_ARRAY                   ## (sum will be < len)
      words.push(w) ## Append to the final list
    end  end
  count = 1      ## For Pager  sp = Aspell.new  ## Spell Checking  File.open('words.txt', 'w') do |f|    words.each do |w|      if sp.check w        w = w.center(w.length+4, "_")        p w      else        p w      end        f.write(w + "\n")      if count%25 == 0        print "--more--"        STDIN.getc      end      count += 1    end  endend-------------------------------------------------------------------------------------------quiz121.rb ends


On 4/20/07, Ruby Quiz <[e-mail]> 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!>> 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 --..>>

-- 
अभिजीत
[written in http://www.paahijen.com/scratchpad]
[http://www.paahijen.com]