Inhalt
Die Fakten:
| Plattform: | codewars.com |
| Name: | Snail |
| Level: | 4 kyu |
| Sprache: | JavaScript |
Beschreibung:
Snail Sort
Given an n x n array, return the array elements arranged from outermost elements to the middle element, traveling clockwise.
array = [[1,2,3],
[4,5,6],
[7,8,9]]
snail(array) #=> [1,2,3,6,9,8,7,4,5]
For better understanding, please follow the numbers of the next array consecutively:
array = [[1,2,3],
[8,9,4],
[7,6,5]]
snail(array) #=> [1,2,3,4,5,6,7,8,9]
This image will illustrate things more clearly:
NOTE: The idea is not sort the elements from the lowest value to the highest; the idea is to traverse the 2-d array in a clockwise snailshell pattern.
NOTE 2: The 0x0 (empty matrix) is represented as en empty array inside an array [[]].
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 erstellen wir uns ein leeres Ergebnis-Array.
Schritt 2
Dann loopen wir solange durch die Input-Arrays, bis sie leer sind.
Schritt 3
Wir entfernen das jeweils das aktuell erste Element (die erste Zeile), (speichern es in einer Variablen) und fügen es zu unserem Ergebnis-Array hinzu.
Schritt 4
Danach entfernen wir die aktuell letzte Reihe und speichern sie in einer Variablen.
Schritt 5
Dann loopen wir durch die verbleibenden mittleren Zeilen.
Schritt 6
Wir entfernen von jeder mittleren Zeile das jeweils letzte Element und hängen es ans Ergebnis-Array.
Schritt 7
Jetzt können wir die letzte vom vorletzten Schritt umgedreht ans Ergebnis-Array anhängen.
Schritt 8
Dann wieder durch die mittleren Zeilen loopen.
Schritt 9
Diesmal das jeweils erste Element entfernen und ans Ergebnis-Array anhängen.
Schritt 10
Zum Schluss nur noch die Arrays im Ergebnis-Array auflösen und zurückgeben.
Code
Geil. Übersetzen wir unseren Pseudo-Code in JavaScript:
Lösungsschritte
Meine erste Zeile:
function snail(arrays) {
Zuerst das Ergebnis-Array initialisieren:
const result = [];
Dann der äußere Loop durch die Arrays, solange bis sie leer sind:
while (arrays.length) {
Jetzt schnappen wir uns die jeweils erste Zeile und hängen sie ans Ergebnis-Array:
const currFirstRow = arrays.shift();
result.push(currFirstRow);
Danach schnappen wir uns die letzte Zeile und speichern sie zwischen:
const currLastRow = arrays.pop();
if (!currLastRow) break;
Sollte es keine letzte Zeile geben, ist die Schnecke einzeilig und wir können den Loop direkt verlassen.
Ansonsten loopen wir dann durch die mittleren Zeilen:
for (let i = 0; i < arrays.length; i++) {
Wir schnappen uns das jeweils letzte Element jeder Zeile und hängen es ans Ergebnis-Array:
const currMiddleRow = arrays[i];
const currLast = currMiddleRow.pop();
result.push(currLast);
}
Dann hängen wir unsere zuvor zwischengespeicherte letzte Zeile umgedreht ans Ergebnis an:
result.push(currLastRow.reverse());
Dann loopen wir noch mal durch die mittleren Zeilen:
for (let i = 0; i < arrays.length; i++) {
Diesmal von unten nach oben. Und wir schnappen uns jetzt das jeweils erste Element:
const currMiddleRow = arrays[arrays.length - 1 - i];
const currFirst = currMiddleRow.shift();
result.push(currFirst);
}
}
Wenn alle Loops durch sind, können wir unser Ergebnis zurückgeben:
return result.flat();
}
Da ich hier einfach wild einen Mix aus Arrays und ordinären Zahlen ans Ergebnis angehangen habe, muss das noch ein Mal “geflatted” werden um ein sauberes eindimensionales Array zu erhalten.
Voilá! 💪
Komplettlösung
function snail(arrays) {
const result = [];
while (arrays.length) {
const currFirstRow = arrays.shift();
result.push(currFirstRow);
const currLastRow = arrays.pop();
if (!currLastRow) break;
// add middle rows last elements
for (let i = 0; i < arrays.length; i++) {
const currMiddleRow = arrays[i];
const currLast = currMiddleRow.pop();
result.push(currLast);
}
result.push(currLastRow.reverse());
// add middle rows first elements
for (let i = 0; i < arrays.length; i++) {
const currMiddleRow = arrays[arrays.length - 1 - i];
const currFirst = currMiddleRow.shift();
result.push(currFirst);
}
}
return result.flat();
}