Interesting String Manipulation Problem

[Ruffnekk]

A friend of mine asked me to code a little tool that can take any string of morse code and output all possible translations of it. At first glance this seemed easy enough, but it turns out to be rather tricky and I'm kind of stuck.

To clarify the problem, I will give an example. I use dots (.) and dashes (-) for morse code.

D   O   N  A  T I  O   N
-.. --- -. .- - .. --- -.

Now, to parse this and get the word 'DONATION' is easy, but what if the spaces were left out?

-..----..--..----.

Taking into account that a morse code 'character' can consist of 1 to 7 dots or dashes (letters, digits and punctuation) the problem arises.

What I need is an (recursive) algorithm that can split the string without spaces into all possible groups of substrings, with a maximum length of 7 chars per substring. It will start at some point, for example 1 1 1 1 1 1 1 1... and iterate through all possible combinations. In the example given, the first morse code character can be - (T) or -. (N) or -.. (D) or -..- (X).

I realize the number of possibilities will grow very large, but that's not the issue.

EDIT: Please realize that the relative positions of the morse code characters do not change.

So does anybody have an idea? Any ideas are welcome, and sample code is appreciated in any language.

[mouser]

Interesting problem.

ok assuming you are not trying to do anything clever like reject possibilities that dont map to english text, and assuming you dont have to worry about stack overflows on too many recursive calls (which you will have to worry about if you really want to implement this on long strings), it should be pretty straightforward.

some pseudocode:

you could start with a function like
DecodeRemainder(string textsofar, string remainingmorsecode)
{
if (remainingmorsecode=="")
  {
  print textsofar;
  return;
  }


for (int i=1;i<=7;++i)
  {
  letter = DecodeMorseCodeUsingNChars(remainingmorsecode,i);
  if (letter!=NULL)
    {
    DecodeRemainder(textsofar + letter, remainingmorsecode.substr(i,len(remainingmorsecode-i) );
    }
  }
}


now keep in mind i dont quite recommend this approach - it's just a theoretical recursive solution off the top of my head which i think will work.

a better solution that wouldnt kill the stack with recursive calls could simply do something like this:
for each position in the morse code string, keep track of 7 pairs of [Lettter, morsecoderemainder position].
then you could much more easily iterate through every possible output by basically walking through the index of branch decisions from
1,1,1,1,1,1,1,1,1 (vector length is the length of the morsecodestring) to
1,1,1,1,1,1,1,1,7 to
...
7,7,7,7,7,7,7,7,7

something like that, if you follow my meaning, stopping when you run out of characters.

[Perry Mowbray]

Hi Ruffnekk:

I wouldn't say I'm a brilliant coder, but I can often get things done (though it's often pretty ugly). Anyway, I was intrigued by your problem so had a bash.

The following VBScript code works for me:
[attach=#1][/attach]

[Select]

Dim Morse(36, 3)
Dim FoundLetters()
Dim iLastFoundLetter
iLastFoundLetter = -1

ReDim FoundLetters(1)

Dim MorseCodeString

MorseCodeString = "-..----..--..----."

' Fill Morse Alphabet
Call FillMorse()

' Check the Morse String
CheckMorseCodeString(1)

' Join Found Characters
Dim strFoundCharacters
strFoundCharacters = Join(FoundLetters , ", ")

' Count Found Characters
for x = 0 to 35

    if Morse(x , 2) > 0 then
   
       if Len(strCountCharacters) > 0 then
          strCountCharacters = strCountCharacters & ", " & Morse(x , 1) & "=" & Morse(x , 2)
       else
           strCountCharacters =  Morse(x , 1) & "=" & Morse(x , 2)
       end if
   
    end if

next

if msgbox ( "Morse String: " & MorseCodeString & vbnewline & "Found: " & strFoundCharacters & vbnewline & vbnewline & "Copy to clipboard?", 4 , "Found Characters") = 6 Then
  Set objIE = CreateObject("InternetExplorer.Application")
  objIE.Navigate("about:blank")
  strURL = objIE.document.parentwindow.clipboardData.setData("Text" ,  Replace(strFoundCharacters , ", " , vbnewline ) )
end if
if msgbox ("Morse String: " & MorseCodeString & vbnewline & "Found: " & strCountCharacters & vbnewline & vbnewline & "Copy to clipboard?", 4 , "Count Characters") = 6 Then
  Set objIE = CreateObject("InternetExplorer.Application")
  objIE.Navigate("about:blank")
  strURL = objIE.document.parentwindow.clipboardData.setData("Text" , Replace(strCountCharacters , ", " , vbnewline ) )
end if

Sub CheckMorseCodeString( iStartHere )

  Dim iWhatsLeft
  For iStart = iStartHere To Len(MorseCodeString)
 
      iWhatsLeft = Len(MorseCodeString) - iStart + 1
      If iWhatsLeft > 7 then iWhatsLeft = 7
 
      For iLength = 1 To iWhatsLeft
     
         CheckString( Mid(MorseCodeString , iStart , iLength))
     
      Next
 
  Next
   
End Sub

Function CheckString(sString)

  For iCount = 0 to Ubound(Morse)-1
    if sString = Morse(iCount , 0) then
       CheckString = True
       
       ' Add another found letter
       ReDim Preserve FoundLetters(Ubound(FoundLetters)+1)
       
       ' Add Found letter to Found Letters       
       FoundLetters(ubound(FoundLetters)) = Morse(iCount, 1)
       ' Increase the Found Count by 1
       Morse( iCount, 2) = Morse( iCount , 2) + 1

       exit for
    else
       if len(Morse(iCount , 0 )) > len(sString) then exit for
    end if
  Next

End Function

Sub FillMorse()

  Dim x
  x = 0
 
  Morse(x,0)="."
  Morse(x,1)="e"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-"
  Morse(x,1)="t"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".-"
  Morse(x,1)="a"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".."
  Morse(x,1)="i"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="--"
  Morse(x,1)="m"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-."
  Morse(x,1)="n"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-.."
  Morse(x,1)="d"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="--."
  Morse(x,1)="g"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-.-"
  Morse(x,1)="k"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="---"
  Morse(x,1)="o"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".-."
  Morse(x,1)="r"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="..."
  Morse(x,1)="s"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="..-"
  Morse(x,1)="u"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".--"
  Morse(x,1)="w"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-..."
  Morse(x,1)="b"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-.-."
  Morse(x,1)="c"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="...."
  Morse(x,1)="h"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".---"
  Morse(x,1)="j"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="..-."
  Morse(x,1)="f"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".-.."
  Morse(x,1)="l"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".--."
  Morse(x,1)="p"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="--.-"
  Morse(x,1)="q"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="...-"
  Morse(x,1)="v"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-..-"
  Morse(x,1)="x"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-.--"
  Morse(x,1)="y"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="--.."
  Morse(x,1)="z"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)=".----"
  Morse(x,1)="1"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="..---"
  Morse(x,1)="2"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="...--"
  Morse(x,1)="3"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="....-"
  Morse(x,1)="4"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="....."
  Morse(x,1)="5"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-...."
  Morse(x,1)="6"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="--..."
  Morse(x,1)="7"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="---.."
  Morse(x,1)="8"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="----."
  Morse(x,1)="9"
  Morse(x,2)=0
  x=x+1
  Morse(x,0)="-----"
  Morse(x,1)="0"
  Morse(x,2)=0
 

End Sub

Is that the sort of thing you meant??