Interesting String Manipulation Problem - DonationCoder.com
HOME | Blog | Software | Reviews and Features | Forum | Help | Donate
Welcome Guest. April 18, 2015, 08:07:13 PM

Or did you miss your validation email?

Why not become a lifetime supporting member of the site with a one-time donation of any amount? Your donation entitles you to a ton of additional benefits, including access to exclusive discounts and downloads, the ability to enter monthly free software drawings, and a single non-expiring license key for all of our programs.

 You must sign up here before you can post and access some areas of the site. Registration is totally free and confidential.
 Check out and download the GOE 2007 Freeware Challenge productivity tools. Entire Forum This board This topic Members Help Desk Entire Site
Pages: [1]   Go Down
 Reply  |  New Topic  |  Print
 Author Topic: Interesting String Manipulation Problem  (Read 2329 times)
Ruffnekk
Honorary Member

Posts: 332

Uhm yeah...

 « on: April 13, 2007, 01:37:44 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.
 « Last Edit: April 13, 2007, 01:50:23 AM by Ruffnekk » Logged

Regards,
RuffNekk

Programming is an art form that fights back.
mouser
First Author

Posts: 34,401

 « Reply #1 on: April 13, 2007, 02:15:31 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:

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.
 Logged
Perry Mowbray
N.A.N.Y. Organizer
Charter Member

Posts: 1,808

Thoughtful Scribbles

 « Reply #2 on: April 13, 2007, 08:36:26 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:

[copy or print]
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")
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")
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

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:50 AM by Perry Mowbray » Logged

Pages: [1]   Go Up
 Reply  |  New Topic  |  Print