JavaScript für Algorithmisches Kompetitives Programmieren

Vergangenes Jahr habe ich mir hin und wieder die Zeit mit kompetitiven Programmier-Wettbewerben vertrieben. Konkret geht es dabei darum, in einem begrenzten Zeitraum algorithmische Probleme zu lösen. Obwohl ich mit diesem Unterfangen noch ganz am Anfang stehe, war es trotzdem echt spannend und ich konnte aus den Aufgaben einige wichtige Erkenntnisse mitnehmen. Was das genau war, möchte ich jetzt genauer erzählen.

Zu dem Zweck werde ich meine Geschichte in drei Teile aufgliedern:

• Meine Motivation
• Die nötigen JavaScript-Funktionen
• Beobachtungen und Tipps für Anfänger

Meine Motivation

Viel zu oft wollte man mir schon weismachen, dass umfassendes Wissen über Algorithmen und Daten-Strukturen keinen echten Nutzen haben, wenn es um die Arbeitsrealität eines Programmierers geht, genauso wenig wie Erfolge in kompetitiven Programmier-Wettbewerben.

Da bin ich anderer Meinung, und zwar aus folgenden Gründen:

1. Man lernt und vertieft die eigene Sprache quasi nebenbei. Bei den Aufgaben konnte ich eine Menge über JavaScript lernen. Das waren Dinge, die vielleicht nicht sofort relevant waren, die mir aber später in diversen Arbeitsprozessen wieder in den Kopf kamen. In Wettbewerben kommen nämlich häufig Probleme dran, die in der Realität selten auftauchen, weswegen man sich vorher auch kaum den Kopf darüber zerbricht. Aber irgendwann kommen sie dann doch, wie z.B. die Herausforderung mit großen Zahlen umzugehen.
2. Man löst interessante Probleme. Darunter so natürliche und sinnvolle Fragen wie: Was ist der optimale Weg, um gewisse Aufgaben zu lösen und so wenig Zeit wie möglich darauf zu verwenden.
3. Das angeeignete Wissen ist fundamental. Für alle, die wie ich im Frontend arbeiten und allzu oft den frustrierenden Moment erleben, dass man etwas „wegwerfen“ muss, das man erst gestern gelernt hat – dann kann dieser Faktor zum sicheren Hafen unserer Arbeitsrealität werden. Das in Wettbewerben angeeignete Wissen wird noch in den nächsten Jahren hilfreich sein. Wenn nicht gar in den nächsten Jahrzehnten oder Jahrhunderten oder Quanten-Computer-Zeitrechnungen…
4. Man kann seine Programmiermuskeln spielen lassen – noch vor einem halben Jahr passierte es mir ziemlich häufig, dass ich es bei der Arbeit mit Fällen zu tun hatte, bei denen mir zwar die Lösung klar war, ich aber gleichzeitig echte Schwierigkeiten hatte, das ganz in Code umzusetzen. Jetzt ist oft sogar andersrum: Hat man einen Code-Algorithmus einmal verstanden fühlt sich das circa so an, als würde man eine fremde Sprache endlich flüssig sprechen – dass die Produktivität am Arbeitsplatz dadurch extrem ansteigt, muss ich wohl keinem erklären.
5. Und dieser Punkt führt uns zu einer letzten extrem wichtigen Fähigkeit: Man lernt, große Dinge in kleinere Teilbereiche aufzubrechen, damit man nicht die ganze Zeit mental den Überblick über das Große, oft überwältigende Ganze behalten muss. Der Grund dafür sind spezifische Algorithmen-Designs, wie z.B. das Teile-und-Herrsche-Verfahren oder das Prinzip des dynamischen Programmierens. Aus diesen Konzepten lässt sich ein tief gehendes Verständnis dafür ableiten, wie man Daten von einem Schritt des Algorithmus auf den nächsten vorbereiten und bearbeiten muss, damit man einerseits in einer niedrigen Zeitkomplexität bleibt, aber dennoch Daten in einem Format behält, das einfach zu bearbeiten ist.

Die wichtigsten JavaScript-Funktionen

Für JavaScript habe ich mich vor allem deshalb entschieden, weil ich die Sprache einfach besser kenne als andere Sprachen.

Im Vergleich zu C, Python und Java ist sie allerdings weniger gebräuchlich im kompetitiven Programmieren. Meine persönliche Vermutung ist, dass das historische Gründe hat. Nachdem ich mich selbst mit JavaScript an Programmierwettbewerbe herangewagt habe, halte ich aber auch zusätzliche nicht-historische Gründe für möglich (was natürlich nichts an der Tatsache ändert, dass ich JS als Programmiersprache liebe!). Nun aber zu den zu bearbeitenden Problemen:

Die großen Zahlen

Der maximal in JavaScript erlaubte Integer erscheint auf den ersten Blick relativ groß:

Number.MAX_SAFE_INTEGER === 9007199254740991

Allerdings nur, bis man dann auf ein Problem stößt, bei dem der maximal erlaubte Input noch größer ist als dieser Maximalwert (siehe zum Beispiel den Google Code Jam 2017und den Google Code Jam 2016 oder Ähnliches).

Manchmal kann auch ein zuerst verstecktes Problem auftreten, z.B. wenn wir Milliarden multiplizieren oder wenn wir Zahlen als IDs nutzen, werden irgendwann alle IDs, die größer als MAX_SAFE_INTEGER sind, von JavaScript als gleichwertig anerkannt:

Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 // true

Es gibt jetzt schon einige Libraries, die große Zahlen vertragen können und eine Initiative des Chrome-Teams widmet sich ebenfalls dieser Thematik. Das heißt, wir können uns auf eine erfreulichere Zukunft mit große Zahlen einstellen – wann die Zukunft aber endlich da sein wird, wissen wir noch nicht. Im Moment werden wir uns also mit diesem Ärgernis arrangieren müssen.

Die Gleitzahlen

Untenstehende Aussage ist ziemlich bekannt und wird in zahlreichen Artikeln aus der gesamten Community zitiert:

0.1 + 0.2 === 0.3 // false

Klar, das ist nicht JavaScript-spezifisch und es gibt auch einige sinnvolle Erklärungen für dieses Phänomen. Allerdings hätte ich es niemals für möglich gehalten, dass ich mich jemals mit diesem Problem rumschlagen würden müsste – bis ich versucht habe, das Problem aus dem Google Code Jam 2017 Runde 1A zu lösen. Dabei musste ich die Maximalanzahl von möglichen Anteilen berechnen, mit der Menge eines jeden Bestandteils als Input und einer möglichen Abweichung, um einen Mengenanteil als Konstante zu definieren.

Zur Lösung meines Problems könnte man nun folgende Funktion aus meinen Federn anwenden:

function getMinMaxWrong(total, serving) {
  var min = Math.ceil(total / (1.1 * serving));
  var max = Math.floor(total / (0.9 * serving));
  return min > max ? [0, 0] : [min, max];
}

console.log(getMinMaxWrong(2376, 3)); // [720, 879]

Scheint auf den ersten Blick korrekt zu sein, allerdings könnten wir sie nochmal umschreiben und diesmal Integer verwenden:

function getMinMaxRight(total, serving) {
  var min = Math.ceil(total * 10 / (11 * serving));
  var max = Math.floor(total * 10 / (9 * serving));
  return min > max ? [0, 0] : [min, max];
}

console.log(getMinMaxRight(2376, 3)); // [720, 880]

Rein mathematisch betrachtet sind diese beiden Formen gleich. Wenn wir sie aber in einer NodeJS-Umgebung ausführen, erhalten wir zwei unterschiedliche Umgebungen und die erste Lösung wird nicht durchgehen.

Die Reinheit von Array-Methoden

Es hat nicht allzu lange gedauert, bis ich mich total an diesen funktionierenden Ansatz und unveränderliche Array-Methoden wie map, filter, slice und reduce gewöhnt hatte. Ich habe sie eine zeitlang sogar dann angewendet, wenn simple for-Schleifen ausgereicht hätten, einfach nur, weil es sich cool angefühlt hat ?.

Später war ich davon überzeugt, dass alle anderen Array-Methoden einfach oberflächliche Kopien machen und immer neue Arrays anstelle des Originals zurückgeben würden.

Ich war der Meinung, dass ich es nach der Ausführung des untenstehenden Codes immer noch mit einem unsortierten arr zu tun hätte:

arrSorted = arr.sort((a, b) => a — b)

Diese Annahme war aber unrichtig, da sort und reverse das vorhandene Array-Objekt verändern.

Aus diesem Grund sollte man immer genau darüber Bescheid wissen, welche Methoden unsere Arrays verändern und welche nicht.

In diesem Fall ist noch ein weiterer Grund zur Vorsicht geboten: Wenn wir eine Rekursion verwenden, kann es sein, dass die Platzkomplexität im Inneren jedes rekursiven Funktionsaufrufs mit oberflächlichen Kopien aufgebläht wird.

Maximale Aufrufstapel

Ein weiterer wichtiger Punkt im Zusammenhang mit Rekursionen ist die maximale Größe von Aufrufstapeln.

Ich bin mir ziemlich sicher, dass jeder JavaScript-Entwickler mindestens einmal im Leben die folgende Nachricht als Resultat einer Ausführung einer unendlichen while oder for–Schleife erhalten hat:

Maximum call stack size exceeded.

Das große Problem hier ist, dass das nicht nur für Endlosschleifen gilt. Es hält uns auch davon ab, Rekursionen mit einer großen Anzahl an Wiederholungen durchzuführen.

Wer schon mal mit einer Tiefensuche einen Baum traversiert hat, hat das vermutlich wie folgt umgesetzt:

1  procedure DFS(G,v):
2    label v as discovered
3    for all edges from v to w in G.adjacentEdges(v) do
4      if vertex w is not labeled as discovered then
5        recursively call DFS(G,w)

Genauso wollte ich ein Problem auf Codeforces angehen. Und genau diese Lösung, die für C++ wunderbar funktionierte, klappte bei Node nicht, da in einem der Tests tatsächlich die maximale Größe der Aufrufstapel überschritten wurde.

Glücklicherweise kann man dieses Problem umgehen, indem man eine nicht-rekursive Tiefensuche anwendet, die zwar an sich einige Einschränkungen mit sich bringt, in unserem konkreten Beispiel aber wunderbar funktioniert. Dasselbe Problem und die dazu passende Umgehung sind auf den Flood Fill –Algorithmus anwendbar und meines Wissens nach auch noch auf ein paar andere.

Wer dennoch auf einer rekursiven Lösung beharrt und über die zutreffenden Input-Limitationen Bescheid weiß (die meistens vorhanden sind), kann den maximalen Aufrufstapel der JavaScript-Engine berechnen, indem wir den folgenden Code-Schnipsel ausführen, den wir uns von Dr. Axel Rauschmayers Blogpost ausgeliehen haben.

function computeMaxCallStackSize() {
  try {
    return 1 + computeMaxCallStackSize();
  } catch (e) {
    // Call stack overflow
    return 1;
  }
}

Nun können wir feststellen, ob die Anzahl von rekursiven Wiederholungen im schlimmsten Fall diese Anzahl überschreitet.

Die Komplexität von Array-Methoden

Das exakt selbe Problem auf Codeforce zwang mich dazu, eine weitere Information über JavaCript Array Methoden zu lernen: Selbst, wenn sie dem Anschein nach dieselbe Sache tun, haben sie vermutlich eine völlig andere Zeitkomplexität.

Nehmen wir mal die Array-Methoden push/pop vs. shift/unshift mit einer Lägen von O(N) an.

Die ersten beiden Methoden haben eine Komplexität von O(1), denn sie

• Lesen die Array length Eigenschaft — O(1)
• Fügen eine weitere Eigenschaft zum Arry Objekt hinzu — O(1)
• Ändern die Array length Eigenschaft — O(1)

Und fertig.

Die anderen beiden Methoden müssen nicht nur die Array-Länge ändern, sondern auch die Werte aller ihrer O(N) Eigenschaften, da die Werte entweder nach vorn oder nach hinten verschoben werden. Dadurch entsteht eine O(N)-Komplexität für fast dieselbe Operation, die man auch mit O(1) ausführen könnte.

Strings sind unveränderlich

Hier eine kleine Info, die gar nicht mal JS-spezifisch ist: Man kann Arrays updaten mit:

arr = ['n', 'o']
arr[0] = 'y'
print(arr.join('')) // 'yo'

allerdings kann man einen String nicht wie folgt verändern:

str = 'no'
str[0] = 'y'
print(str)) // 'no'

Aus diesem Grund nutze ich oft einen kleinen Trick, um Strings in Arrays zu verwandeln, sie zu verarbeiten und sie anschließend gleich wieder zu Strings zurückkonvertieren:

// str -> arr
arr = str.split('')

// arr -> str
str = arr.join('')

Zugegeben, vom Standpunkt der Platzkomplexität ist diese Vorgehensweise nicht optimal, allerdings wird der Code dadurch in vielen Fällen lesbarer und einfacher anwendbar.

JS oder nicht JS – das ist hier die Frage…

Bei Programmier-Wettbewerben wird häufig die NodeJS auf eine alte Version beschränkt. Google Code Jam unterstützt beispielsweise nur die Version v4.8.2. Das bedeutet beispielsweise, dass man keine Klassen, keine let/const-Deklarationen und keine Restrukturierungen anwenden kann. Manchmal vergisst man dann, ob man sich gerade in einem Wettbewerb befindet oder doch an einem Projekt im Job arbeitet.

Das Problem mit den großen Zahlen ist definitiv ein Faktor, warum manche Probleme in JavaScript so schwierig zu lösen sind und das Problem mit der Maximalanzahl von Aufrufstapeln ist ein weiterer lästiger Faktor.

Die oben erwähnten Probleme in den Qualifikationsrunden habe ich gerne mit JS attackiert, besonders im Umgang mit Arrays. Für alle weiteren Schritte würde ich aber zu Python wechseln. Python hat wesentlich weniger Einschränkungen, kommt im maschinellen Lernen extrem häufig zum Einsatz und ist neben Java eine der zwei erlaubten Sprachen in der berühmt-berüchtigten Google Foobar Challenge ?.

Die richtige Vorbereitung für die Qualifikationsrunden

Also, fühlt sich nach der bisherigen Lektüre jemand dazu berufen, sich ebenfalls die Hände schmutzig zu machen und zukünftige Wettbewerbe in Angriff zu nehmen? Vielleicht, um mithilfe von Programmier-Wettbewerben die eigenen Software-Sprachkenntnisse zu verbessern? Falls ja, würde ich persönlich empfehlen, am Anfang erst einmal die Probleme der vergangenen Jahre durchzuarbeiten. Einerseits, um ein Gefühl für die Aufgaben zu bekommen und andererseits, um ein bisschen Selbstvertrauen zu tanken – denn das braucht man, wenn man nicht einfach irgendwo einen Blick auf den richtigen Lösungsweg werfen kann.

Kleine vs. Große Datensätze

In Code Jam bekommt man für gewöhnlich ein kleines und ein großes Dataset zur Verfügung gestellt. Während bei der Lösung des großen Datensatzes fast immer die Zeitkomplexität zu berücksichtigen ist, kann das kleine Dataset quasi immer mit Brute Force gelöst werden.

Dadurch erhalten wir folgende Vorteile:

• Wir können Muster in den kleinen Datensätzen beobachten und erhalten wichtige Einblicke für den optimierten Algorithmus – das gilt besonders dann, wenn wir es mit einem Mathe-Problem zu tun haben
• Wir können die Lösung des großen Datensatzes anhand der Brute Force-Lösung des kleinen Datensatzes validieren
• Manchmal können wir sogar für den großen Datensatz die Brute Force-Methode anwenden (um das zu bestimmen, achten wir am besten auf Input-Limitationen und die Komplexität des Algorithmus)

Mathe

Häufig kommen Mathe-Fragen, bei denen es um Binärdarstellungen, die Teilbarkeit durch verschiedene Zahlen oder Primzahlen geht. Zugegeben: Es ist ein bisschen schwierig, sich konkret auf solche Dinge vorzubereiten. Ich persönlich verlasse mich hier hauptsächlich auf meine Erfahrungen in Mathe-Wettbewerben aus Schulzeiten und versuche immer wieder, mein Wissen ein bisschen zu erweitern, z.B. durch das Lösen von Wettbewerbsaufgaben aus früheren Jahren.

Wahrscheinlichkeitstheorie

Wahrscheinlichkeitsaufgaben kommen übrigens überraschend oft vor!

Um solche Aufgaben zu lösen, bei denen wir eine p1, p2,.., pn Wahrscheinlichkeit haben, dass ein gewisses Ereignis eintritt, reicht folgendes Wissen meiner Meinung nach für gewöhnlich aus:

• Mindestens ein Ereignis tritt ein ist: p1 + p2 + ... + pn
• Mindestens ein Ereignis tritt nicht ein ist: (1 — p1) + (1 — p2) + … + (1 — pn)
• Alle Ereignisse treten ein: p1 * p2 *… * pn
• Keines der Ereignisse tritt ein: (1 — p1) * (1 — p2) * … * (1 — pn)

Hier ein Beispiel: Runde 1C 2017

Bitweise Operationen

Die gesamte Programmier-Welt basiert auf der binären Natur von Signalen. Aus diesem Grund ist es ganz logisch, dass bei Wettbewerben häufig Probleme auftauchen werden, die ein gewisses Wissen über bitweise Operationen erfordern.

Hier ein Beispiel: Qualifikationsrunde 2011

Greedy-Algorithmus, Hash-Algorithmus und DP-Algorithmus

So gut wie alle Algorithmus-Aufgaben der bisherigen Qualifikations-Aufgaben konnte mit einem Greedy-Algorithmus, Hash-Algorithmus und DP-Algorithmus oder einer Kombination dieser Methoden gelöst werden. Diese Ansätze sind gar nicht so schwer. Es braucht nicht viel mehr, als ein bisschen Übung, um ein Gespür dafür zu bekommen, wann welcher Algorithmus Sinn ergibt.

Und was kommt danach?

Obwohl JavaScript in Wettbewerben bislang nicht sonderlich populär ist, gibt es ein paar Projekte, die hier Abhilfe schaffen:

trekhleb/javascript-algorithms
javascript-algorithms – Algorithms and data structures implemented in JavaScript with explanations and links to further…github.com

mgechev/javascript-algorithms
javascript-algorithms – JavaScript implementation of different computer science algorithms.github.com

Und hier ist mein Repository mit diversen Lösungen für die Code Jam-Qualifikationsrunden:

romanovma/google-codejam
GitHub is where people build software. More than 28 million people use GitHub to discover, fork, and contribute to over…github.com

Ich hoffe, ihr hattet Freude an meinen Gedankengängen und jetzt viel Spaß und Erfolg beim Üben!