Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Range Extraction |
| Level: | 4 kyu |
| Sprache: | JavaScript |
Beschreibung:
A format for expressing an ordered list of integers is to use a comma separated list of either
- individual integers
- or a range of integers denoted by the starting integer separated from the end integer in the range by a dash, '-'. The range includes all integers in the interval including both endpoints. It is not considered a range unless it spans at least 3 numbers. For example "12,13,15-17"
Complete the solution so that it takes a list of integers in increasing order and returns a correctly formatted string in the range format.
Example:
solution([-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20]);
// returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
solution([-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
solution([-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
solution([-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
Solution.rangeExtraction(new int[] {-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20})
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
RangeExtraction.Extract(new[] {-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20});
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
RangeExtraction.Extract({-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20});
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
range_extraction({-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20});
// returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
range_extraction((const []){-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20}, 23);
/* returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20" */
nums: dd -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20
mov rdi, nums
mov rsi, 20
call range_extraction
; RAX <- `-10--8,-6,-3-1,3-5,7-11,14,15,17-20\0`
rangeextraction([-10 -9 -8 -6 -3 -2 -1 0 1 3 4 5 7 8 9 10 11 14 15 17 18 19 20])
# returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
solution(List(-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20))
// "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
(solution '(-10 -9 -8 -6 -3 -2 -1 0 1 3 4 5 7 8 9 10 11 14 15 17 18 19 20))
; returns "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
solution([-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 14, 15, 17, 18, 19, 20])
// returns '-10--8,-6,-3-1,3-5,7-11,14,15,17-20'
Rangeextraction
xs = [-10, -9, -8, -6, -3, -2, -1, 0, 1, 3, 4, 5, 7, 8, 9, 10, 11,
14, 15, 17, 18, 19, 20]
res = "-10--8,-6,-3-1,3-5,7-11,14,15,17-20"
Courtesy of rosettacode.org
Quelle: codewars.com
Lösung
Pseudo-Code
Es gibt wie immer viele Varianten, hier ist eine meiner.
Erst die Lösungsschritte in Pseudo-Code. Los geht’s:
Lösungsschritte
Schritt 1
Als Erstes brauchen wir 2 Variablen, genauer Arrays. Eine um unser Endergebnis zu speichern und eine zum Zwischenspeichern der aktuellen potentiellen Range
Schritt 2
Dann loopen wir durch die Zahlen des Input-Arrays
Schritt 3
In jeder Iteration berechnen wir den Abstand der aktuellen zur nächsten Zahl
Schritt 4
Wenn dieser Abstand 1 ist, können wir die aktuelle Zahl ruhigen Gewissens an unser Zwischenspeicher-Array hängen
Schritt 5
Wenn der Abstand nicht 1 ist, prüfen wir ob unser Zwischenspeicher-Array leer ist
Schritt 6
Wenn es nicht leer ist, haben wir gerade die letzte Zahl der aktuellen Range und hängen sie noch ans Zwischenspeicher-Array an
Schritt 7
Dann prüfen wir, ob die aktuelle Range im Zwischenspeicher-Array 3 oder mehr Zahlen beeinhaltet
Schritt 8
Wenn ja, können wir die erste und die letzte Zahl der aktuellen Range, getrennt mit einem Bindestrich an unser Endergebnis-Array hängen
Schritt 9
Ansonsten hängen wir nur die beiden Zahlen an, die im Zwischenspeicher-Array sind
Schritt 10
Nachdem wir eine Range hatten, dürfen wir nicht vergessen, das Zwischenspeicher-Array wieder zu leeren
Schritt 11
Wenn der Abstand nicht 1 war und das Zwischenspeicher-Array aktuell leer ist, hängen wir die Zahl wie sie ist an das Endergebnis-Array
Schritt 12
Nach dem Loop noch Endergebnis komma-getrennt ausgeben, fertig!
Code
Geil. Übersetzen wir unseren Pseudo-Code in JavaScript:
Lösungsschritte
Meine erste Zeile (ich habe list in nums umbenannt):
function solution(nums) {
Zuerst unsere beiden Arrays für Endergebnis und zum Zwischenspeichern einer potentiellen aktuellen Range:
const output = [];
let currRange = [];
Dann der Loop durch die Zahlen des Input-Arrays:
for (let i = 0; i < nums.length; i++) {
const currNum = nums[i];
const nextNum = nums[i + 1] ?? Infinity;
Die aktuell und die nächste Zahl speichere ich mir der Übersichtlichkeit halber jeweils in einer Variablen zwischen.
Sollte die nächste Zahl null oder undefined, also nicht existent sein, setze ich sie auf Unendlich. Damit ist sie in jedem Fall ‘pseudo’-größer als die aktuelle Zahl.
Da sie 0 sein kann und 0 falsy ist, kann ich hier nicht einfach das logische ODER (||) verwenden, sondern verwende den Nullish coalescing operator (??).
Dann berechnen wir den Abstand zwischen der aktuellen und der nächsten Zahl:
const distance = Math.abs(currNum - nextNum);
Den reinen Abstand zwischen den beiden Zahlen berechnen wir mit dem Betrag ihrer Differenz (Math.abs()). Wir streichen also quasi ein potentielles (negatives) Vorzeichen.
Dann prüfen wir, ob der Abstand 1 ist:
if (distance === 1) {
currRange.push(currNum);
continue;
}
Dann können wir die aktuelle Zahl an das Zwischenspeicher-Array anhängen.
Mit continue beenden wir die aktuelle Iteration und springen direkt zur nächsten Zahl. Ohne dass der restliche Code in der For-Schleife ausgeführt wird.
Ich bin ein großer Fan dieses Keywords, denn so kann man sich jede Menge unübersichtlicher if-else-Konstruktionen sparen. Mehr dazu findest du hier.
Wenn der Abstand nicht 1 ist, prüfen wir, ob unser Zwischenspeicher-Array gerade leer ist:
if (currRange.length) {
currRange.push(currNum);
Wenn also beides zutrifft hieße das, dass die aktuelle Zahl auch die letzte Zahl der aktuellen Range ist. Die können wir auch noch ans aktuelle Zwischenspeicher-Array anhängen.
Dann müssen wir noch prüfen, ob die aktuelle Range lang genug ist, um als Range definiert werden zu können:
if (currRange.length >= 3) output.push(currRange[0] + "-" + currNum);
Wenn ja, können wir die erste Zahl der Range und die letzte (also die aktuelle) verbunden mit einem - an unser Ergebnis-Array anhängen.
Wenn nicht, hängen wir nur die erste und die letzte Zahl ohne - an:
else output.push(currRange[0], currNum);
Nicht vergessen die aktuelle Range, also das Zwischenspeicher-Array zurückzusetzen:
currRange = [];
continue;
}
Wenn der Abstand nicht 1 ist und auch das Zwischenspeicher-Array leer ist, hängen wir unsere aktuelle Zahl schnöde an das Ergebnis-Array:
output.push(currNum);
}
Nach dem Loop nur noch das Ergebnis-Array in einen String umwandeln und zurückgeben:
return output.join(",");
}
Voilá! 💪
Komplettlösung
function solution(nums) {
const output = [];
let currRange = [];
for (let i = 0; i < nums.length; i++) {
const currNum = nums[i];
const nextNum = nums[i + 1] ?? Infinity;
const distance = Math.abs(currNum - nextNum);
if (distance === 1) {
currRange.push(currNum);
continue;
}
if (currRange.length) {
currRange.push(currNum);
if (currRange.length >= 3) output.push(currRange[0] + "-" + currNum);
else output.push(currRange[0], currNum);
currRange = [];
continue;
}
output.push(currNum);
}
return output.join(",");
}