Welcome Guest.   Make a donation to an author on the site May 19, 2013, 10:52:13 PM  *

Please login or register.
Or did you miss your validation email?


Login with username and password (forgot your password?)
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.
 
View the new Member Awards and Badges page.
   
   Forum Home   Thread Marks Chat! Downloads Search Login Register  
+  DonationCoder.com Forum
|-+  Other Software
| |-+  Developer's Corner
| | |-+  Interesting String Manipulation Problem
Pages: [1]   Go Down
« previous next »
  Reply  |  New Topic  |  Print  
Author Topic: Interesting String Manipulation Problem  (Read 2010 times)
Ruffnekk
Honorary Member
**
Posts: 331



Uhm yeah...

View Profile WWW Give some DonationCredits to this forum member
« 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
Administrator
*****
Posts: 30,972



plarker mouser see users location on a map View Profile WWW Read user's biography. Give some DonationCredits to this forum member
« 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:

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.
Logged
Perry Mowbray
N.A.N.Y. Organizer
Charter Member
***
Posts: 1,693



Thoughtful Scribbles

plarker scribbly see users location on a map View Profile WWW Read user's biography. Give some DonationCredits to this forum member
« 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")
  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:50 AM by Perry Mowbray » Logged
Pages: [1]   Go Up
  Reply  |  New Topic  |  Print  
« previous next »



[ may-june 2013 ad experiment; click here to learn more about donationcoder.com ]


 
Jump to:  
   Forum Home   Thread Marks Chat! Downloads Search Login Register  

DonationCoder.com | About Us
DonationCoder.com Forum | Powered by SMF
[ Page time: 0.04s | Server load: 0.08 ]