Decode the Morse code, for real
Description:
In this kata you have to deal with "real-life" scenarios, when Morse code transmission speed slightly varies throughout the message as it is sent by a non-perfect human operator. Also the sampling frequency may not be a multiple of the length of a typical "dot".
For example, the message HEY JUDE
, that is ···· · −·−− ·−−− ··− −·· ·
may actually be received as follows:
0000000011011010011100000110000001111110100111110011111100000000000111011111111011111011111000000101100011111100000111110011101100000100000
As you may see, this transmission is generally accurate according to the standard, but some dots and dashes and pauses are a bit shorter or a bit longer than the others.
Note also, that, in contrast to the previous kata, the estimated average rate (bits per dot) may not be a whole number – as the hypotetical transmitter is a human and doesn't know anything about the receiving side sampling rate.
For example, you may sample line 10 times per second (100ms per sample), while the operator transmits so that his dots and short pauses are 110-170ms long. Clearly 10 samples per second is enough resolution for this speed (meaning, each dot and pause is reflected in the output, nothing is missed), and dots would be reflected as 1 or 11, but if you try to estimate rate (bits per dot), it would not be 1 or 2, it would be about (110 + 170) / 2 / 100 = 1.4. Your algorithm should deal with situations like this well.
Also, remember that each separate message is supposed to be possibly sent by a different operator, so its rate and other characteristics would be different. So you have to analyze each message (i. e. test) independently, without relying on previous messages. On the other hand, we assume the transmission charactestics remain consistent throghout the message, so you have to analyze the message as a whole to make decoding right. Consistency means that if in the beginning of a message '11111' is a dot and '111111' is a dash, then the same is true everywhere in that message. Moreover, it also means '00000' is definitely a short (in-character) pause, and '000000' is a long (between-characters) pause.
That said, your task is to implement two functions:
1. Function decodeBitsAdvanced(bits)
, that should find an estimate for the transmission rate of the message, take care about slight speed variations that may occur in the message, correctly decode the message to dots .
, dashes -
and spaces (one between characters, three between words) and return those as a string. Note that some extra 0
's may naturally occur at the beginning and the end of a message, make sure to ignore them. If message is empty or only contains 0
's, return empty string. Also if you have trouble discerning if the particular sequence of 1
's is a dot or a dash, assume it's a dot. If stuck, check this for ideas.
2. Function decodeMorse(morseCode)
, that would take the output of the previous function and return a human-readable string. If the input is empty string or only contains spaces, return empty string.
NOTE: For coding purposes you have to use ASCII characters .
and -
, not Unicode characters.
The Morse code table is preloaded for you as MORSE_CODE
dictionary, feel free to use it. For C, the function morse_code
acts like the dictionary. For C++, Scala and Go, a map is used. For C#, it's called Preloaded.MORSE_CODE
. For Racket, a hash called MORSE-CODE is used.
(hash-ref MORSE-CODE "".-.") ; returns "C"
Of course, not all messages may be fully automatically decoded. But you may be sure that all the test strings would be valid to the point that they could be reliably decoded as described above, so you may skip checking for errors and exceptions, just do your best in figuring out what the message is!
Good luck!
Similar Kata:
Stats:
Created | Jan 7, 2015 |
Published | Jan 16, 2015 |
Warriors Trained | 17933 |
Total Skips | 3420 |
Total Code Submissions | 135404 |
Total Times Completed | 1944 |
Python Completions | 1107 |
JavaScript Completions | 430 |
Java Completions | 178 |
C Completions | 39 |
C++ Completions | 73 |
C# Completions | 97 |
Haskell Completions | 23 |
Racket Completions | 2 |
Ruby Completions | 20 |
Scala Completions | 9 |
Go Completions | 22 |
Total Stars | 1683 |
% of votes with a positive feedback rating | 75% of 355 |
Total "Very Satisfied" Votes | 226 |
Total "Somewhat Satisfied" Votes | 82 |
Total "Not Satisfied" Votes | 47 |
Total Rank Assessments | 8 |
Average Assessed Rank | 3 kyu |
Highest Assessed Rank | 1 kyu |
Lowest Assessed Rank | 4 kyu |