Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Decode the Morse code, advanced |
| Level: | 4 kyu |
| Sprache: | TypeScript |
Beschreibung:
This kata is part of a series on the Morse code. Make sure you solve the previous part before you try this one. After you solve this kata, you may move to the next one.
In this kata you have to write a Morse code decoder for wired electrical telegraph.
Electric telegraph is operated on a 2-wire line with a key that, when pressed, connects the wires together, which can be detected on a remote station. The Morse code encodes every character being transmitted as a sequence of "dots" (short presses on the key) and "dashes" (long presses on the key).
When transmitting the Morse code, the international standard specifies that:
- "Dot" – is 1 time unit long.
- "Dash" – is 3 time units long.
- Pause between dots and dashes in a character – is 1 time unit long.
- Pause between characters inside a word – is 3 time units long.
- Pause between words – is 7 time units long.
However, the standard does not specify how long that "time unit" is. And in fact different operators would transmit at different speed. An amateur person may need a few seconds to transmit a single character, a skilled professional can transmit 60 words per minute, and robotic transmitters may go way faster.
For this kata we assume the message receiving is performed automatically by the hardware that checks the line periodically, and if the line is connected (the key at the remote station is down), 1 is recorded, and if the line is not connected (remote key is up), 0 is recorded. After the message is fully received, it gets to you for decoding as a string containing only symbols 0 and 1.
For example, the message HEY JUDE, that is ···· · −·−− ·−−− ··− −·· · may be received as follows:
1100110011001100000011000000111111001100111111001111110000000000000011001111110011111100111111000000110011001111110000001111110011001100000011
As you may see, this transmission is perfectly accurate according to the standard, and the hardware sampled the line exactly two times per "dot".
That said, your task is to implement two functions:
- Function
decodeBits(bits), that should find out the transmission rate of 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 extra0's may naturally occur at the beginning and the end of a message, make sure to ignore them. Also if you have trouble discerning if the particular sequence of1's is a dot or a dash, assume it's a dot.
2. Function decodeMorse(morseCode), that would take the output of the previous function and return a human-readable string.
NOTE: For coding purposes you have to use ASCII characters . and -, not Unicode characters.
The Morse code table is preloaded for you (see the solution setup, to get its identifier in your language).
Eg:
morseCodes(".--") //to access the morse translation of ".--"
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!
After you master this kata, you may try to Decode the Morse code, for real.
Quelle: codewars.com
Lösung
Pseudo-Code
Wie immer gibt's reichlich Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Wir brauchen 2 Funktionen. Außerdem macht es Sinn, hier ein paar Hilfsfunktionen zu basteln. Das trägt zur Lesbarkeit und Übersichtlichkeit bei.
Schritt 2
Als Erstes basteln wir uns eine Hilfsfunktion um potentielle Nullen vom Anfang und Ende des Input-Strings zu entfernen.
Schritt 3
Dann können wir eine Hilfsfunktion erstellen, die die Transmission-Rate ermittelt (das ist der kniffligste Teil).
Schritt 4
Für die Transmission-Rate müssen wir die Bits in Zeichengruppen aufteilen. Auch das kann man noch mal in eine Hilfsfunktion auslagern.
Schritt 5
In der ersten Hauptfunktion decodeBits() entfernen wir dann mit unseren Hilfsfunktionen alle Nullen vom Anfang und Ende und ermitteln die Transmission-Rate.
Schritt 6
Dann ersetzen wir Bits entsprechend mit Leerzeichen bzw. Bindestrichen, Punkten oder wir löschen sie.
Schritt 7
Das Ergebnis zurückgeben und fertig ist die erste Hauptfunktion.
Schritt 8
In der zweiten Hauptfunktion decodeMorse() wandeln wir als Erstes den Input-String in ein Array von Morsecode-Wörtern um.
Schritt 9
Dann können wir durch dieses Array von Wörtern in Morsecode loopen.
Schritt 10
Danach loopen wir durch jedes Morsecode-Wort und ersetzen jeden Morsecode-Buchstaben mit Hilfe des MORSE_CODE-Objekts mit einem richtigen Buchstaben.
Schritt 11
Das Ergebnis geben wir als String zurück.
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Wenn du den Morsecode zum Testen brauchst (z.B. in RunJS), du findest ihn hier:
const morseCode: { [key: string]: string } = {
".-": "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",
};
Die erste Zeile meiner ersten Hilfsfunktion:
export function removeLeadingAndTrailingZeros(bits: string): string {
Dann wollen wir alle Nullen von Anfang und Ende entfernen. Dafür bietet sich eine RegEx an:
return bits.replace(/^0*|0*$/g, "");
}
Was genau passiert hier?
Das ist die Regex: /^0*|0*$/g
Die Regex matcht:
- Alle Nullen am Anfang des Strings (
^0*).
- ODER (
|)
- Alle Nullen am Ende des Strings (
0*$).
Mit .replace() werden dann die gematchten Nullen durch einen leeren String ("") ersetzt, also entfernt.
Weiter geht’s mit einer Hilfsfunktion für die zweite Hilfsfunktion.
Die erste Zeile meiner Hilfsfunktion für meine zweite Hilfsfunktion:
export function createArrWithCharGroups(str: string): string[] {
Auch hier bietet sich wieder eine RegEx an:
return str.match(/(.)\1*/g) || [];
}
Kurz: Die Regex sucht nach Gruppen von wiederholten, gleichen Zeichen.
Falls match keine Übereinstimmungen findet (z.B. wenn der String leer ist), gibt match null zurück. Um das zu verhindern, wird stattdessen ein leeres Array [] zurückgegeben.
Das war’s auch hier auch schon. Weiter geht’s mit der zweiten Hilfsfunktion um die Transmission-Rate zu ermitteln.
Dann die erste Zeile meiner zweiten Hilfsfunktion:
export function getTransmissionRate(bits: string): number {
Hier holen wir uns als Erstes die Zeichen-Gruppen in eine Variable:
const groups = createArrWithCharGroups(bits);
Dann ermitteln wir jeweils die Längen aller Zeichengruppen in diesem Array:
const groupsLengths = groups.map((group) => group.length);
Hier bietet sich .map() an, da wir genauso viele Elemente raus haben wollen, wie rein gehen.
Zum Schluss noch die Länge der kürzesten Gruppe ermitteln:
return Math.min(...groupsLengths);
}
Dann kann’s endlich mit den Hauptfunktionen losgehen!
Die erste Zeile meiner ersten Hauptfunktion (decodeBits()):
export function decodeBits(bits: string): string {
Als Erstes entfernen wir mit unserer ersten Hilfsfunktion alle Nullen vom Anfang und Ende des Input-Strings:
const cleanedBits = removeLeadingAndTrailingZeros(bits);
Dann ermitteln wir mit unserer zweiten Hilfsfunktion die Transmission-Rate:
const rate = getTransmissionRate(cleanedBits);
Als nächstes wandeln wir die Bits in Morsecode um:
return cleanedBits
.replaceAll("000000".repeat(rate), " ")
.replaceAll("111".repeat(rate), "-")
.replaceAll("000".repeat(rate), " ")
.replaceAll("1".repeat(rate), ".")
.replaceAll("0".repeat(rate), "");
}
Die .replaceAll()-Methods können wir wunderbar chainen, darum können wir das return schon oben setzen.
Weiter geht’s mit der zweiten Hauptfunktion.
Die erste Zeile meiner zweiten Hauptfunktion (decodeMorse()):
export function decodeMorse(morseCode: string): string {
Zuerst den Input-Morsecode in ein Array umwandeln:
return morseCode.split(" ");
Hier können wir wieder wunderbar chainen, darum setzen wir das return auch hier wieder bereits oben an.
Da die Morse-Wörter mit 3 Leerzeichen voneinander getrennt sind, führen wir den Split mit eben diesen 3 Leerzeichen durch.
Dann der Loop durch die Morse-Wörter:
.map((morseWord) =>
Wir wollen genauso viele Wörter zurück bekommen, wie wir rein geben. Daher bietet sich hier wieder ein .map()-Loop an.
Dann loopen wir durch jedes Morse-Wort:
morseWord.split(" ").map((morseChar) => MORSE_CODE[morseChar]);
Wir schlagen jedes Morse-Zeichen im MORSE_CODE-Wörterbuch nach und geben die Übersetzung zurück.
Danach wandeln wir das Zeichen-Array wieder in einen String um:
.join("")
)
Und zum Schluss nicht vergessen auch das Wörter-Array wieder in einen String umzuwandeln:
.join(" ");
}
Voilá! 💪
Komplettlösung
import { MORSE_CODE } from "./preloaded";
export function decodeBits(bits: string): string {
const cleanedBits = removeLeadingAndTrailingZeros(bits);
const rate = getTransmissionRate(cleanedBits);
return cleanedBits
.replaceAll("000000".repeat(rate), " ")
.replaceAll("111".repeat(rate), "-")
.replaceAll("000".repeat(rate), " ")
.replaceAll("1".repeat(rate), ".")
.replaceAll("0".repeat(rate), "");
}
export function decodeMorse(morseCode: string): string {
return morseCode
.split(" ")
.map((morseWord) =>
morseWord
.split(" ")
.map((morseChar) => MORSE_CODE[morseChar])
.join(""),
)
.join(" ");
}
// helpers
export function removeLeadingAndTrailingZeros(bits: string): string {
return bits.replace(/^0*|0*$/g, "");
}
export function getTransmissionRate(bits: string): number {
const groups = createArrWithCharGroups(bits);
const groupsLengths = groups.map((group) => group.length);
return Math.min(...groupsLengths);
}
export function createArrWithCharGroups(str: string): string[] {
return str.match(/(.)\1*/g) || [];
}