Morse Key Decoder
MediumOnline Assessment
Decode a telegraph operator's key log into text.
The key was timed in milliseconds. signal alternates between how long the key was down and how long it was up, always starting and ending with a down: [down, up, down, up, ..., down] (empty if the key was never pressed). unit is the length of one dot. Standard International Morse is used:
A .- B -... C -.-. D -.. E . F ..-. G --. H .... I .. J .--- K -.- L .-.. M -- N -. O --- P .--. Q --.- R .-. S ... T - U ..- V ...- W .-- X -..- Y -.-- Z --.. 0 ----- 1 .---- 2 ..--- 3 ...-- 4 ....- 5 ..... 6 -.... 7 --... 8 ---.. 9 ----.
Step 1, chatter. Any duration x with 2 * x < unit is a glitch (a bounce of the contacts), whether it is a down or an up. A glitch and the interval right after it are absorbed into the interval right before the glitch: that interval gets longer by x plus the following interval. This is done left to right, so the lengthened interval can be followed by another glitch. A merged interval keeps the type (down or up) of the interval before the glitch.
Step 2, reading. After step 1:
- a down shorter than
2 * unitis a dot, a down of2 * unitup to (not including)5 * unitis a dash, and a down of5 * unitor more is a stuck key; - an up shorter than
2 * unitseparates two symbols of the same letter, an up of2 * unitup to (not including)5 * unitends a letter, and an up of5 * unitor more ends a letter and a word.
A letter that contains a stuck key is decoded as ?, and so is a dot-dash pattern that is not in the table.
Input: unit and signal.
Output: the decoded text with exactly one space between words; "" for an empty signal.
Example 1
- Input:
- [100,[100,100,140,30,150,150,40,160,100,700,600,100,100]]
- Output:
- "AE ?"
- Explanation
- With unit 100, the first press is a dot. The 100 up is a symbol gap. The press 140 is followed by an up of 30, which is a glitch (2 * 30 < 100), so 140 + 30 + 150 = 320 becomes one dash: the letter is
.-=A. The up of 150 is followed by a down of 40, a glitch, so the gap becomes 150 + 40 + 160 = 350 (a letter gap, not two short gaps), andEfollows. The gap 700 is a word gap. Then a press of 600 is a stuck key, so that letter is?:AE ?.
Example 2
- Input:
- [100,[95,105,100,100,110,290,310,100,280,100,300,305,95,100,105,100,100]]
- Output:
- "SOS"
- Explanation
- Every press and gap is near its ideal length.
Sis three dots, 290 ends the letter,Ois three dashes (310, 280, 300), 305 ends the letter again, and the lastSis three dots. The result isSOS.
Example 3
- Input:
- [60,[60,120,120,300,30,29,30,60,60,300,60,60,180,60,60,60,180]]
- Output:
- "ET I ?"
- Explanation
- 60 is a dot (
E), 120 is a letter gap (2 * unitis a letter gap), 120 is a dash (T), and 300 is a word gap (5 * unit). Then a press of 30 is not a glitch (2 * 30is not below 60); the up of 29 is a glitch, so it merges with the next press: 30 + 29 + 30 = 89, a dot. With the following dot this gives..=I. After another word gap the pattern dot dash dot dash is not in the table, so it is?:ET I ?.
Constraints
- 1 ≤ unit ≤ 200
- 0 ≤ signal.length ≤ 301 and signal.length is odd when non-empty; every duration is between 1 and 2000
- The first and last durations are never glitches, and no two glitches are adjacent