26
Developer's Corner / Interesting String Manipulation Problem
« Last post by Ruffnekk 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.
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.

Recent Posts
I was waiting for this every day 
Is it what you expected from it? I already have an Xbox 360 and a PS3 for serious gaming
(Yeah yeah I'm a console freak!)
Too bad no-one is here now to try it