Inhalt
Die Fakten:
Plattform: | codewars.com |
Name: | A Simple Music Decoder |
Level: | 6 kyu |
Sprache: | TypeScript |
Beschreibung:
You have been hired by a major MP3 player manufacturer to implement a new music compression standard. In this kata you will implement the DECODER, and its companion kata deals with the ENCODER.
Specification
The input signal is represented as a comma-separated string of integers and tokens (sequence descriptors). Tokens must be expanded as follows.
number*count
is expanded asnumber
repeatedcount
timesfirst-last
is expanded as a sequence of consecutive numbers starting withfirst
and ending withlast
. This is true for both ascending and descending orderfirst-last/interval
is similarly expanded, as sequence starting withfirst
, ending withlast
, where the numbers are separated byinterval
. Note that interval does NOT have a sign
Examples
"1,3-5,7-11,14,15,17-20"
is expanded to[1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]
"0-4/2, 5, 7-9"
is expanded to[0, 2, 4, 5, 7, 8, 9]
"0-4/2, 5, 7-5"
is expanded to[0, 2, 4, 5, 7, 6, 5]
"0-4/2, 5, 7-5, 5*4"
is expanded to[0, 2, 4, 5, 7, 6, 5, 5, 5, 5, 5]
Input
A string of comma-separated integers and tokens (sequence descriptors)
Output
An array of integers
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
Ich schlage vor, dass wir jede Range in einem Token in ein Array mit Zahlen auflösen.
Schritt 2
Dafür macht es Sinn eine eigene Hilfsfunktion zu erstellen.
Schritt 3
Wenn wir der Hilfsfunktion das Intervall mit übergeben, können wir sie für beide möglichen Intervall-Tokens verwenden.
Schritt 4
In der Hilfsfunktion sollten wir dann als Erstes das bis
also das -
finden.
Schritt 5
Da eine Range auch bei negativen Zahlen starten und enden kann, können allerdings mehrere -
enthalten sein.
Schritt 6
Eine Möglichkeit ist, das -
zu finden, welches das erste -
nach dem ersten Zeichen ist.
Schritt 7
Dann können wir Start und Ende der Range bestimmen.
Schritt 8
Wenn der Anfang der Range kleiner als das Ende ist, müssen wir vorwärts zählen, ansonsten rückwärts.
Schritt 9
Jetzt können wir ein Array mit den Zahlen von Anfang bis Ende mit dem richtigen Intervall befüllen.
Schritt 10
Dann können wir uns um die Hauptfunktion kümmern.
Schritt 11
Zuerst loopen wir durch die einzelnen Tokens.
Schritt 12
Da wir alle Ranges und Tokens mit *
in Arrays auflösen, loopen wir hier am besten direkt mit .flatMap()
!
Schritt 13
Jetzt brauchen wir nur noch 3
Bedingungen.
Schritt 14
- Wenn das aktuelle Token ein
*
enthält, geben wir dem Array ein Array mitx
Wiederholungen der Zahl zurück.
Schritt 15
- Wenn das aktuelle Token ein
/
enthält, geben wir dem Array ein Array mit den Zahlen von-bis mit dem entsprechenden Intervall zurück.
Schritt 16
- Wenn das Token nur ein
-
enthält, geben wir dem Array ein Array mit den Zahlen von-bis mit dem Intervall1
zurück.
Schritt 17
Ansonsten geben wir dem Array das Token als Zahl zurück.
Schritt 18
Das Ganze noch zurückgeben, fertig!
Code
Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:
Lösungsschritte
Die erste Zeile meiner Hilfsfunktion:
function createArrayFromRange(range: string, interval: number = 1): number[] {
Die Hilfsfunktion bekommt den Range-String und ein optionales Intervall. Wenn kein Intervall übergeben wird, setzen wir es standardmäßig auf 1
.
Jetzt suchen wir die Position des richtigen -
:
const dashPosition = range.indexOf("-", 1);
Da auch an der ersten Stelle ein -
stehen kann, suchen wir den Index des ersten -
nach dem ersten Element. Dafür steht die 1
im zweiten Argument von .indexOf()
.
Mit der dashPosition
können wir dann Anfang und Ende der Range definieren:
const start = Number(range.slice(0, dashPosition));
const end = Number(range.slice(dashPosition + 1));
Jetzt können wir die Länge der Range definieren:
const arrLen = Math.abs(start - end) / interval + 1;
Außerdem müssen wir ermitteln in welche Richtung die Range geht:
const signedInterval = start < end ? +interval : -interval;
Wenn wir beides haben können wir das Array erstellen:
return Array(arrLen)
.fill(0)
.map((_, i) => start + i * signedInterval);
}
Wir erstellen ein leeres Array mit der oben ermittelten Länge. Das füllen wir zuerst mit Nullen und anschließend mit den richtigen Zahlen der Range.
Das Ganze noch zurückgeben und fertig ist die Hilfsfunktion um Ranges in Arrays umzuwandeln. Weiter geht’s mit der Hauptfunktion!
Hier die erste Zeile meiner Hauptfunktion:
export function uncompress(music: string): number[] {
Als Erstes der Loop durch die Tokens:
return music.split(",").flatMap((token) => {
Wie oben erwähnt, eignet sich hier wunderbar .flatMap()
, damit wir die ganzen Subarrays in einem Rutsch mit auflösen können.
Unser return
können wir bereits hier mit hinsetzen.
Dann die erste Bedingung:
if (token.includes("*")) {
const [num, count] = token.split("*").map(Number);
return Array(count).fill(num);
}
Jetzt die zweite Bedingung:
if (token.includes("/")) {
const [range, interval] = token.split("/");
return createArrayFromRange(range, Number(interval));
}
Hier kommt zum ersten Mal unsere Hilfsfunktion zu Einsatz. Geil!
Dann die dritte Bedingung:
if (token.includes("-")) return createArrayFromRange(token);
Ich spare mir hier das Gewurschtel mit wilden if...else
-Konstrunktionen. Darum ist es wichtig, dass der Check (für Ranges) mit dem -
nach dem Check (für Ranges) mit dem /
kommt!
In allen übrigen Fällen ist das aktuelle Token eine Zahl. Die geben wir einfach als solche zurück:
return Number(token);
});
}
Voilá! 💪
Schönes Kata! Bisschen schwierig zu erklären... Aber ich hoffe es hat Dir trotzdem Spaß gemacht! 😉
Komplettlösung
export function uncompress(music: string): number[] {
return music.split(",").flatMap((token) => {
if (token.includes("*")) {
const [num, count] = token.split("*").map(Number);
return Array(count).fill(num);
}
if (token.includes("/")) {
const [range, interval] = token.split("/");
return createArrayFromRange(range, Number(interval));
}
if (token.includes("-")) return createArrayFromRange(token);
return Number(token);
});
}
function createArrayFromRange(range: string, interval: number = 1): number[] {
const dashPosition = range.indexOf("-", 1);
const start = Number(range.slice(0, dashPosition));
const end = Number(range.slice(dashPosition + 1));
const arrLen = Math.abs(start - end) / interval + 1;
const signedInterval = start < end ? +interval : -interval;
return Array(arrLen)
.fill(0)
.map((_, i) => start + i * signedInterval);
}