Here is my solution. This appears a lot complex to me. What I am

trying to find is every possible word (or collection of letters) that

can be obtained using the given morse code.

Approach

Given a Morse Code, we insert imaginary vertical bars to separate . and

…—…

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

vertical

bars and output words corresponding to them.

This is done in three steps

- Building a hash of all Symbols of length 1,2,3 and 4 in the Input

Morse Code
- Building a list of all tuples of 1,2,3,4, that sum upto the input

length
- 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,3

and 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 letter

corresponding to the combination in another hash (MORSE_ARRAY), whose

keys

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

This

becomes 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

tuples

containing [1,2,3,4] that sum upto the input length of the Morse Code.

Also

note that sum of the tuples may be invalid (Thos containing “nil” in the

above Hash above.)

The set of these tuples (also as a Hash) can be calculated starting with

0 = [] 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

with

2, tuples ending with 3 and tuples ending with 4. Tuples ending with 1

are

nothing but all the tuples of N-1 with a one in the end (Check tuples

for

2 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 word

is marked with begining and trailing ‘__’.

## Bells and Whistles

A trivial pager is implemented (which just accepts enter), to scroll

down

the list, This is not a fully functional pager at all. One can simply

scroll down but not scroll up and so on.

Finally all the words are stored in a file words.txt, which can be

examined 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

end

end

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

end

end

quiz121.rb ends

On 4/20/07, Ruby Q. [email protected] wrote:

and words, but in written form the code can be ambiguous.

```
B -... O ---
M -- Z --..
```

–

à¤…à¤à¤¿à¤œà¥€à¤¤

[written in http://www.paahijen.com/scratchpad]

[http://www.paahijen.com]