Advent of Code 2015 – Objektorientierte Lösungen in Java

Advent of Code 2015 – Tag 1 Lösung

Tag 1 ist schnell gelöst: Ein Counter wird für jede '(' hoch- und für jede ')' wieder runtergezählt – entweder bis zum Ende (Teil eins) oder bis der Zähler den Wert -1 erreicht (Teil zwei).

GitHub: Advent of Code 2015 Tag 1 Lösung

Advent of Code 2015 – Tag 2 Lösung

Tag 2 ist auch recht einfach – man muss nur jede Zeile in Länge, Breite und Höhe parsen und ein paar Grundrechenarten anwenden, um Flächen, Umfang und Volumen zu berechnen.

GitHub: Advent of Code 2015 Tag 2 Lösung

Advent of Code 2015 – Tag 3 Lösung

Die Lösung von Tag 3 habe ich mit einem Set implementiert, das alle Orte speichert, die Santa besucht hat. Die Lösung von Teil eins entspricht der Größe des Sets.

Für Teil zwei habe ich je ein Set für Santa und eines für Robo-Santa verwendet. Am Ende werden beide Sets zu einem zusammengeführt und dessen Größe zurückgegeben.

GitHub: Advent of Code 2015 Tag 3 Lösung

Advent of Code 2015 – Tag 4 Lösung

Um Tag 4 zu lösen, müssen wir über alle positiven Zahlen iterieren, bis wir einen Hash mit der geforderten Anzahl von führenden Nullen finden. Es geht etwa doppelt so schnell, wenn wir direkt im Byte-Array nach den führenden Nullen suchen und dieses nicht erst in einen Hex-String umwandeln.

GitHub: Advent of Code 2015 Tag 4 Lösung

Advent of Code 2015 – Tag 5 Lösung

Für Tag 5 habe ich zwei "Nice String"-Detektoren geschrieben, die das Interface Predicate<String> implementieren. Auf diese Weise können wir den Detektor für Teil zwei leicht austauschen.

GitHub: Advent of Code 2015 Tag 5 Lösung

Advent of Code 2015 – Tag 6 Lösung

Tag 6 habe ich mit einem zweidimensionalen Array von ints gelöst. Ich habe die beiden Regelsätze für Teil eins und zwei jeweils mit einer Map vom Kommando ("turn on", "toggle", "turn off") auf einen IntUnaryOperator implementiert, der die neue Helligkeit auf der Grundlage der vorherigen berechnet.

Dies ist der interessante Teil des Codes:

EnumMap<Command, IntUnaryOperator> commandToOperatorPart1 = new EnumMap<>(Command.class);
commandToOperatorPart1.put(TURN_ON, brightness -> 1);
commandToOperatorPart1.put(TOGGLE, brightness -> 1 - brightness);
commandToOperatorPart1.put(TURN_OFF, brightness -> 0);

EnumMap<Command, IntUnaryOperator> commandToOperatorPart2 = new EnumMap<>(Command.class);
commandToOperatorPart2.put(TURN_ON, brightness -> brightness + 1);
commandToOperatorPart2.put(TOGGLE, brightness -> brightness + 2);
commandToOperatorPart2.put(TURN_OFF, brightness -> Math.max(brightness - 1, 0));Code-Sprache: Java (java)

Und so wird eine solche Operation auf ein Feld im Array angewendet:

IntUnaryOperator operator = commandToOperator.get(command);
brightness[y][x] = operator.applyAsInt(brightness[y][x]);Code-Sprache: Java (java)

GitHub: Advent of Code 2015 Tag 6 Lösung

Advent of Code 2015 – Tag 7 Lösung

Das Domänenmodell für Tag 7 war ein bisschen schwierig zu gestalten. So sah es am Ende aus:

Wenn dieses Modell fertig verdrahtet ist, muss man nur noch die Instruction mit der destinationWireId finden und die Methode getSignal() für die WireSource dieser Instruction aufrufen.

GitHub: Advent of Code 2015 Tag 7 Lösung

Advent of Code 2015 – Tag 8 Lösung

An Tag 8 können wir uns ein wenig zurücklehnen. Die Escape- und Unescape-Methoden sind schnell implementiert.

GitHub: Advent of Code 2015 Tag 8 Lösung

Advent of Code 2015 – Tag 9 Lösung

An Tag 9 müssen wir das klassische "Problem des Handlungsreisenden" (Travelling salesman problem) lösen. Da wir nur ein paar Städte haben, können wir eine einfache Tiefensuche durchführen, um alle möglichen Routen zu finden, und ihre minimale und maximale Länge festhalten.

GitHub: Advent of Code 2015 Tag 9 Lösung

Advent of Code 2015 – Tag 10 Lösung

Ein Blick in den von Tag 10 verlinkten Wikipedia-Artikel lässt mich vermuten, dass die die Länge der Sequenz nach 40 Runden in der Größenordnung von einer Million liegt. Das sollte jeder moderne Computer in wenigen Millisekunden simulieren können.

Der Algorithmus ist schnell implementiert und löst Teil eins in 5 Millisekunden. Mein Ergebnis ist 492.982 – liegt also in der angepeilten Größenordnung.

Auch für Teil zwei – 50 Runden – braucht der Algorithmus nur 70 ms.

GitHub: Advent of Code 2015 Tag 10 Lösung

Advent of Code 2015 – Tag 11 Lösung

Der Algorithmus für Tag 11 schafft die Aufgabe auch ohne Optimierungen in unter 100 ms. Mit einigen Optimierungen lässt sich diese Zeit stark reduzieren:

• Der String wird zu Beginn in ein Character-Array umgewandelt; alle Operationen erfolgen auf diesem; die Rückumwandung in einen String erfolgt erst am Ende.
• Zu Beginn wird geprüft, ob das Passwort einen der Buchstaben i, l, o enthält. Wenn ja, dann wird die entsprechende Stelle sofort erhöht und alle Folgestellen auf 'a' gesetzt.
• Beim Hochzählen werden die Buchstaben i, l, o übersprungen.

Mit diesen Optimierungen findet der Algorithmus das nächste Passwort in 0,016 ms!

GitHub: Advent of Code 2015 Tag 11 Lösung

Advent of Code 2015 – Tag 12 Lösung

Teil eins von Tag 12 lässt sich mit einem simplen regulären Ausdruck lösen: "-?\d+" (die Anführungszeichen gehören nicht dazu). Wir müssen nur noch alle Treffer aufsummieren.

Teil zwei lässt sich mit einem JSON-Parser (z. B. Gson) und Rekursion gut lösen.

GitHub: Advent of Code 2015 Tag 12 Lösung

Advent of Code 2015 – Tag 13 Lösung

Tag 13 lässt sich mit einer Tiefensuche über alle möglichen Sitzordnungen schnell lösen.

GitHub: Advent of Code 2015 Tag 13 Lösung

Advent of Code 2015 – Tag 14 Lösung

Teil eins von Tag 14, also die Entfernung, die ein Rentier nach einer bestimmten Zeit zurückgelegt hat, lässt sich leicht berechnen.

Die gleiche Formel können wir für Teil zwei anwenden, mit ihr lässt sich die Aufgabe in weniger als einer Millisekunde lösen. Die Zeitkomplexität ist allerdings O(n² · m), wobei n die simulierte Zeit ist und m die Anzahl der Rentiere. Die benötigte Zeit wächst also im Quadrat mit der simulierten Zeit.

Schneller geht es, wenn wir den Fortschritt der Rentiere Sekunde für Sekunde simulieren (so habe ich Teil zwei letztlich implementiert). So erreichen wir die deutlich bessere Zeitkomplexität O(n · m).

GitHub: Advent of Code 2015 Tag 14 Lösung

Advent of Code 2015 – Tag 15 Lösung

Die Aufgabe von Tag 15 lässt sich wieder mit einer Tiefensuche lösen, über die wir für alle möglichen Kombinationen von Zutataten den jeweiligen Score berechnen. Für Teil 2 habe ich einfach die Berechnung des Scores angepasst: Sobald ein Keks keine 500 Kalorien hat, wird dessen Score als 0 festgelegt.

GitHub: Advent of Code 2015 Tag 15 Lösung

Advent of Code 2015 – Tag 16 Lösung

Die Lösung für Tag 16 kann sehr elegant mit einem Predicate<Sue> als abstrakte Basisklasse für ein Strategy Pattern implementiert werden. So können für Teil eins und Teil zwei leicht zwei unterschiedliche Strategien implementiert werden.

Da alle angeforderten Eigenschaften vorab bekannt sind, könnten sie in entsprechend benannten Variablen gespeichert werden, wobei eine nicht bekannte Eigenschaft als null oder -1 gespeichert werden könnte. Eleganter und flexibler ist eine Liste von Tupeln von Eigenschaftname und -wert. Eine nicht bekannte Eigenschaft zeichnet sich dann durch Nichtvorhandensein in der Liste aus.

GitHub: Advent of Code 2015 Tag 16 Lösung

Advent of Code 2015 – Tag 17 Lösung

Die Aufgabe von Tag 17 kann per Tiefensuche gelöst werden. Bei 20 Containern gibt es genau 2²⁰ – also etwas mehr als eine Million – verschiedene Kombinationen. Es dauert etwa 3,2 Millisekunden, diese alle durchzuprobieren.

Doch es gibt eine Menge Optimierungspotential:

1. Ist bei einer unvollständigen Kombination das Zielvolumen exakt erreicht, haben wir eine Kombination gefunden und brauchen den Pfad nicht weiter zu verfolgen – die restlichen Container werden nicht benötigt.
2. Ist bei einer unvollständigen Kombination das Zielvolumen überschritten, können wir den aktuellen Pfad abbrechen.
3. Wenn die aktuelle Summe plus das kleinste Element der restlichen Elemente die Zielsumme überschreitet, können wir den Pfad ebenfalls abbrechen. Das kleinste Element der letzten x Elemente können wir vorab für jede Position innerhalb der Containerfolge bestimmen.
4. Wenn die Summe der Volumen der restlichen Container nicht ausreicht, um die noch benötigte Restsumme zu erreichen, können wir den Pfad ebenfalls abbrechen. Die Restsummen der letzten x Elemente können wir ebenfalls vorab berechnen.

Mit diesen Optimierungen dauert es nur noch 0,15 ms, alle passenden Kombinationen zu finden. Die Optomierungen haben den Algorithmus also um mehr als Faktor 20 beschleunigt.

GitHub: Advent of Code 2015 Tag 17 Lösung

Advent of Code 2015 – Tag 18 Lösung

An Tag 18 müssen wir Conway's Game of Life implementieren. Da unser Grid begrenzt ist und relativ viele lebende Zellen enthält, eignet sich ein zweidimensionalen boolean-Array. (Bei unbegrenzten Feldern oder wenigen lebenden Zellen kann man auch nur die lebenden Zellen in einer Collection speichern.)

Die Anpassungen für Teil zwei – die vier Ecken immer eingeschaltet zu lassen – sind schnell erledigt.

GitHub: Advent of Code 2015 Tag 18 Lösung

Advent of Code 2015 – Tag 19 Lösung

Teil eins der Aufgabe von Tag 19 ist schnell gelöst, indem wir das Molekül Atom für Atom durchgehen, die Atome jeweils durch all ihre Ersetzungen ersetzen und die entstandenen Moleküle in einem Set speichern. Dessen Größe ist am Ende die Lösung.

Teil zwei ist deutlich komplexer. Ich habe mehrere Brute-Force-Lösungen durchprobiert: Breitensuche vorwärts, Tiefensuche vorwärts, Breitensuche rückwärts, Tiefensuche rückwärts. Der einzige Weg, der in akzeptabler Zeit überhaupt zu einer Lösung führte, war eine Tiefensuche rückwärts (d. h. der Versuch, vom Zielmolekül durch umgekehrtes Anwenden der Ersetzungsregeln zum Elektron zu gelangen) – mit Priorisierung der Ersetzungsregeln absteigend nach Länge des Zielmoleküls. Auf diese Weise wurde nach wenigen Sekunden zumindest ein Ergebnis gefunden. Doch es hätte mehrere Tage gedauert, die Tiefensuche bis zum Ende laufen zu lassen.

Auf eine bessere Lösung brachte mich erst ein Blick in das entsprechende Reddit-Topic:

Wenn wir uns die Ersetzungsregeln genauer anschauen, fällt auf, dass diese einem der folgenden Muster zuzuordnen sind, wobei X für ein beliebiges Atom steht:

• e => XX
• X => XX
• X => XRnXAr
• X => XRnXYXAr
• X => XRnXYXYXAr

Rn, Y und Ar stehen nur auf der rechten Seite der Regeln. Wenn wir sie durch '(', ',' und ')' ersetzen, sehen die Regeln wie folgt aus:

• e => XX
• X => XX
• X => X(X)
• X => X(X,X)
• X => X(X,X,X)

Auf der linken Seite steht immer genau ein Atom. Und jedes Zielmuster hat eine spezifische Länge. Die Anwendung eines bestimmten Musters verlängert also das Molekul um eine bestimmte Anzahl Atome:

• e => XX – von 1 auf 2, also +1
• X => XX – von 1 auf 2, also +1
• X => X(X) – von 1 auf 4, also +3
• X => X(X,X) – von 1 auf 6, also +5
• X => X(X,X,X) – von 1 auf 8, also +7

Wenn wir keine Klammern und Kommas hätten, wäre die Anzahl der Schritte, um von einem Atom ("e") zu n Atomen zu gelangen genau n-1, da wir das Molekül in jedem Schritt um ein Atom verlängern.

Beispiel: Um von "e" zu "XXXX" (n = 4) zu gelangen, bräuchten wir 4-1 = 3 Schritte:

1. e → XX
2. XX → XXX
3. XXX → XXXX

Wenn wir zusätzlich die Regel X => X(X) beachten, verlängert sich das Molekül zusätzlich um die "Klammer-Atome". Um aus dem Zielmolekül die Anzahl der Schritte zu berechnen, können wir diese "Klammer-Atome" einfach wieder abziehen. Wir bräuchten also n-1-(Anzahl der Klammern) Schritte.

Beispiel: Um von "e" zu "X(X)X(X)" (n = 8) zu gelangen, bräuchten wir 8-1-4 = 3 Schritte:

1. e → XX
2. XX → X(X)X (erstes X ersetzt)
3. X(X)X → X(X)X(X) (letztes X ersetzt)

Wenn wir nun auch noch die Regeln X => X(X,X) und X => X(X,X,X) beachten, verlängert sich das Molekül mit jedem Komma um zwei weitere Atome: das Komma-Atom selbst und das auf das Komma folgende Atom. Für jedes Komma müssen wir also zwei Atome abziehen. Als Gesamtformel ergibt sich:

Anzahl Schritte = Anzahl Zielatome - 1 - Anzahl Klammern - 2 × Anzahl Kommas

Beispiel: Um von "e" zu "X(X,X(X,X,X))X" (n = 14) zu gelangen, bräuchten wir 14-1-4-2×4 = 3 Schritte:

1. e → XX
2. XX → X(X,X)X (erstes X ersetzt)
3. X(X,X)X → X(X,X(X,X,X))X (zweites X innerhalb der Klammern ersetzt)

Mittels dieser Formel ist auch Teil 2 der Aufgabe schnell gelöst.

GitHub: Advent of Code 2015 Tag 19 Lösung

Advent of Code 2015 – Tag 20 Lösung

Teilaufgabe eins von Tag 20 können wir auch wie folgt formulieren:

Gesucht ist das kleinste n, für das die Teilerfunktion σ₁(n) >= p ist (mit p = Puzzle Input / 10).

Diese Funktion ist schnell implementiert und für Teilaufgabe zwei schnell mit ein paar zusätzlichen Parametern adaptiert.

GitHub: Advent of Code 2015 Tag 20 Lösung

Advent of Code 2015 – Tag 21 Lösung

Für Tag 21 habe ich einen Simulator geschrieben, der das Spiel mit gegebenen Parametern ("hit points", "damage", "armor" pro Spieler) durchspielt und den Sieger zurückgibt. Mit dem Simulator können alle erlaubten Kombinationen von Waffe, Verteidigung und Ringen (es gibt nur 1.080 solcher Kombinationen) durchgespielt werden.

Wenn wir vorab die möglichen Kombinationen nach Gesamtkosten sortieren (aufsteigend für Teilaufgabe eins und absteigend für Teilaufgabe zwei), dann können wir die Simulationen abbrechen, sobald die erste Kombination gefunden wurde, bei der der Spieler (bei Teilaufgabe eins) bzw. der Boss (bei Teilaufgabe zwei) gewinnt.

GitHub: Advent of Code 2015 Tag 21 Lösung

Advent of Code 2015 – Tag 22 Lösung

Die Aufgabe von Tag 22 kann gut mit einer Breitensuche gelöst werden, da es pro Spielrunde nicht allzu viele Möglichkeiten gibt (die bezahlbaren und aktuell nicht aktiven Zaubersprüche).

Ich habe die Breitensuche mit einer PriorityQueue implementiert, die die erreichten Spielstände nach Gesamtkosten aufsteigend sortiert.

Wenn eine Lösung gefunden wurde und wir einen Zauberspruch überspringen mussten (weil dieser nicht bezahlbar war oder bereits aktiv ist), könnten wir noch eine bessere Lösung finden – von einem weiter hinten in der Queue liegenden Spielstand aus mit gleich viel oder höheren Kosten kombiniert mit einem günstigeren Zauberspruch.

Wir brauchen die Suche jedoch nur solange fortzusetzen, bis die Kosten des Spielstands in der Queue plus die Kosten des günstigsten Zauberspruchs gleich oder höher als die Kosten der bisher besten Lösung sind. Alle weiteren Spielstände in der Queue würden zu einer teureren Lösung führen.

Die Anpassungen für Teil zwei sind minimal.

GitHub: Advent of Code 2015 Tag 22 Lösung

Advent of Code 2015 – Tag 23 Lösung

An Tag 23 müssen wir eine CPU mit zwei Registern und sechs Instruktionen emulieren. Dies ist recht einfach, und auch die Änderungen für Teil zwei sind schnell gemacht.

GitHub: Advent of Code 2015 Tag 23 Lösung

Advent of Code 2015 – Tag 24 Lösung

Für die Aufgabe von Tag 24 eignet sich wieder eine Tiefensuche über die möglichen Paket-Kombinationen. Dabei müssen wir nur für das erste Abteil eine optimale Lösung finden. Wannimmer wir für das erste Abteil eine Lösung gefunden haben und diese besser ist als die bisher beste Lösung, müssen wir nur prüfen, ob es für die restlichen Abteile wenigstens eine Lösung gibt.

Sobald die Tiefensuche für das erste Abteil zu mehr Paketen führt als die bisher beste Lösung, kann der entsprechende Pfad abgebrochen werden.

Meine Implementierung findet eine Lösung für Teil eins in 1,5 s und für Teil zwei in 40 ms.

GitHub: Advent of Code 2015 Tag 24 Lösung

Advent of Code 2015 – Tag 25 Lösung

An Tag 25 von Advent of Code 2015 müssen wir einen Code-Generator implementieren. Die Beschreibung der Aufgabe ist lang, die Lösung erfordert aber nur wenige Zeilen Code:

static int solve(int row, int col) {
  int elementIndex = calculateElementIndex(row - 1, col - 1);
  return getCode(elementIndex);
}

static int calculateElementIndex(int row, int col) {
  int diagonalNumber = row + col;
  int diagonalStart = diagonalNumber * (diagonalNumber + 1) / 2;
  return diagonalStart + col;
}

static int getCode(int iterations) {
  int code = 20_151_125;
  for (int i = 0; i < iterations; i++) {
    code = (int) (code * 252_533L % 33_554_393);
  }
  return code;
}
Code-Sprache: Java (java)

GitHub: Advent of Code 2015 Tag 25 Lösung

Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende. Möchtest du per E-Mail informiert werden, wenn ich einen neuen Artikel veröffentliche? Dann klicke hier, um dich in den HappyCoders-E-Mail-Verteiler einzutragen