Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
• December 11, 2018, 12:30 PM
• Proudly celebrating 13 years online.
• Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.

### Author Topic: Interesting String Manipulation Problem  (Read 3092 times)

#### Ruffnekk

• Honorary Member
• Joined in 2006
• Posts: 332
• Uhm yeah...
##### Interesting String Manipulation Problem
« on: April 13, 2007, 01:37 AM »
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.
Regards,
RuffNekk

Programming is an art form that fights back.
« Last Edit: April 13, 2007, 01:50 AM by Ruffnekk »

#### mouser

• First Author
• Administrator
• Joined in 2005
• Posts: 39,015
##### Re: Interesting String Manipulation Problem
« Reply #1 on: April 13, 2007, 02:15 AM »
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

• N.A.N.Y. Organizer
• Charter Member
• Joined in 2005
• Posts: 1,817
##### Re: Interesting String Manipulation Problem
« Reply #2 on: April 13, 2007, 08:36 AM »
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]

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

« Last Edit: April 13, 2007, 08:38 AM by Perry Mowbray »