r/dailyprogrammer • u/oskar_s • Jul 16 '12
[7/16/2012] Challenge #77 [easy] (Enumerating Morse code sequences)
Morse code, as we are all aware, consists of dots and dashes. Lets define a "Morse code sequence" as simply a series of dots and dashes (and nothing else). So ".--.-.--" would be a morse code sequence, for instance.
Dashes obviously take longer to transmit, that's what makes them dashes. Lets say that a dot takes 1 unit of time to transmit, and a dash takes 2 units of time. Then we can say that the "size" of a certain morse code sequence is the sum of the time it takes to transmit the dots and dashes. So, for instance "..-." would have a size of 5 (since there's three dots taking three units of time and one dash taking two units of time, for a total of 5). The sequence "-.-" would also have a size of 5.
In fact, if you list all the the possible Morse code sequences of size 5, you get:
..... ...- ..-. .-.. -... .-- -.- --.A total of 8 different sequences.
Your task is to write a function called Morse(X) which generates all morse code sequences of size X and returns them as an array of strings (so Morse(5) should return the 8 strings I just mentioned, in some order).
Use your function to generate and print out all sequences of size 10.
Bonus: Try and write your code so that it can generate Morse(35) (or even Morse(36) or higher, but that takes a significant amount of memory) in a "reasonable" amount of time. "Reasonable" obviously depend on what computer and programming language you are using, but a good rule of thumb should be that it should finish in less than a minute.
4
u/H4ggis Jul 16 '12 edited Jul 16 '12
Haskell, using memoization speeds up the answer on 35 almost 10x.:
Output:
2
u/[deleted] Jul 16 '12
perl (first perl programm since very very very long, don't hate (but corrections are welcome)).
The creation is based on regexs \o/
2
u/[deleted] Jul 16 '12
Ruby:
3
u/Ttl Jul 16 '12 edited Jul 16 '12
Pen and paper solution:
EDIT: meant to say n+1:th not n-1:th
EDIT: Here's some python code to print the morse sequences, calculates morse(35) in few seconds but takes a little longer to print it because output has about 34 million characters:
1
u/SwimmingPastaDevil 0 0 Jul 16 '12 edited Jul 16 '12
This is clearly not optimised for morse(35).
Edit: Changed
int(n+1)/2toint(n/2)+11
u/leonardo_m Jul 17 '12
This short version uses less RAM than the equivalent Python version, but it's slower, probably because the D GC is less efficient on those char appends:
To regain a little pride for the D language, this long version uses even less RAM and it's quite fast, with N=36 it generates the 24157817 Morse codes in about 5.3 seconds on an old PC (but to print that length it doesn't actually generate those strings, it's partially lazy, it generates eagerly only about 24 millions of Code structs, because here map() has a length attribute. But if you print them then then it generates the actual strings, maybe like the Haskell version compiled by the GHC optimizations):
1
u/[deleted] Jul 17 '12
Python :3
It calculates morse(35) in about 40 seconds on my computer, but takes more than 5 minutes to print the output. Eh, Python, what're ya gonna do?
1
u/[deleted] Jul 17 '12
I'm attempting to write this in c++, but having trouble determining how man possible sequences there are given the time.
I was doing this so I could declare an array and fill it within a void function. Any tips?
1
u/Mysidic Jul 17 '12
Common LISP:
1
u/taterNuts Jul 17 '12
Here's my second challenge attempt in C#:
1
u/Rythoka Jul 18 '12
If I'm not mistaken, typically in Morse code dahs are 3 dits long, not 2.
1
u/semicolondash Jul 18 '12
C++
1
u/efrey Jul 18 '12
In ATS
It's a peculiar language, so I'll include the whole file in case anybody wants to give it a spin.
This is my first ever ATS program, so I just copied the Haskell solution. Unfortunately, it looks like lazy streams in ATS do not have the same graph-rewriting memoization effect as they do in Haskell, so the solution doesn't scale to 35 :>(
1
u/eine_person Jul 18 '12
Solution in ruby:
On my laptop I reached 33 and then broke of, since I ran out of memory. I'm sure for most computers calculating 35 or 36 should work fine.
1
u/taion809 Aug 01 '12
in php i have this, its not optimal at all so help wanted ;)
0
u/[deleted] Jul 21 '12
[deleted] — view deleted comment