Advent of Code 2022 – Objektorientierte Lösungen in Java
1. Dezember 2022Ungeduldig? Dann geht es hier ohne Umwege zu meinen Lösungen für Advent of Code 2022 :-)
Was ist Advent of Code?
Advent of Code ist eine jährliche, vorweihnachtliche Serie von Programmieraufgaben, die als Adventskalender verpackt sind. Hinter dessen Türen verbergen sich täglich neue – von Tag zu Tag schwierigere – Herausforderungen.
Die Aufgaben können in einer beliebigen Programmiersprache gelöst werden und bestehen jeweils aus zwei Teilaufgaben.
Wie schwer ist Advent of Code?
Die erste Teilaufgabe ist meist relativ schnell gelöst.
Bei der zweiten Aufgabe wird die Größenordnung des Problems drastisch angehoben. Das führt in der Regel dazu, dass die Lösung noch einmal überarbeitet werden muss, da der intuitiv implementierte Algorithmus oft eine zu hohe Komplexitätsklasse aufweist und Stunden, Tage oder gar Monate für die Lösung der Aufgabe brauchen würde.
Kurz nach der Veröffentlichung eines neuen Advent-of-Code-Rätsels findet man bereits die ersten Lösungen im entsprechenden Reddit. Diese bestehen meist aus prozeduralem Spaghetti-Code, der nicht besonders gut lesbar, geschweige denn wartbar, ist.
Meine Advent of Code Antworten 2022
Ich habe mir daher die Mühe gemacht, jede Aufgabe wirklich objektorientiert und testgetrieben in Java zu implementieren, so dass eine Lösung aus kleinen, verständlichen, miteinander interagierenden Objekten entsteht.
Dieser Ansatz führt in der Regel auch dazu, dass sich die Optimierungen, die für Teilaufgabe zwei notwendig sind, auf einen kleinen Ausschnitt des Codes beschränken – oft auf eine einzige Klasse.
Meine Lösungen findest du in diesem GitHub-Projekt: Advent of Code 2022 – Object-oriented Solutions in Java.
Advent of Code 2022 – Tag 1 Lösung
Die Aufgaben von Tag 1 lassen sich elegant mit Java Streams lösen. Die folgende Methode liefert einen Stream der Kaloriensummen für jeden Block:
static IntStream getCaloriesSums(String input) {
String[] blocks = input.split("\\n\\n");
return Arrays.stream(blocks)
.mapToInt(block -> block.lines().mapToInt(Integer::parseInt).sum());
}Code-Sprache: Java (java)Den größten Block ermitteln wir mittels max():
static int calculateMaxCalories(String input) {
IntStream caloriesSums = getCaloriesSums(input);
return caloriesSums.max().orElse(0);
}Code-Sprache: Java (java)Für die Summe der drei größten Blocks müssen wir den Stream absteigend sortieren. Dazu ist leider ein Boxing und ein Unboxing erforderlich, da sich ein IntStream nur aufsteigend sortieren lässt:
static int calculateSumOfTopThreeCalories(String input) {
IntStream caloriesSums = getCaloriesSums(input);
return caloriesSums
.boxed()
.sorted(Comparator.reverseOrder())
.mapToInt(Integer::valueOf)
.limit(3)
.sum();
}Code-Sprache: Java (java)GitHub: Advent of Code 2022 Tag 1 Lösung
Advent of Code 2022 – Tag 2 Lösung
An Tag 2 müssen wir einen Simulator für Schere-Stein-Papier schreiben. Teilaufgabe zwei, bei der wir vom Spielergebnis auf den Zug rückschließen müssen, habe ich durch ausprobieren gelöst – es gibt ja nur drei mögliche Züge. Eleganter wäre es natürlich, den eigenen Zug aus dem Zug dem Gegners und dem gewünschten Ergebnis zu berechnen.
GitHub: Advent of Code 2022 Tag 2 Lösung
Advent of Code 2022 – Tag 3 Lösung
An Tag 3 müssen wir einen Algorithmus implementieren, der aus mehreren Listen von Gegenständen (aus zwei Fächern eines Rucksacks bzw. aus drei Rucksäcken) diejenigen herausfiltert, die mehrfach vorkommen.
Wenn wir dabei jedes Element einer Liste mit allen Elementen der zwei anderen Listen vergleichen, kämen wir auf eine Zeitkomplexität von O(n²).
Da die Menge der möglichen Elemente (A-Z und a-z) sehr klein ist, können wir stattdessen ein Array mit Bitsets für jedes mögliche Element anlegen, dann über jede Liste iterieren und für jedes enthaltene Element ein Bit für die entsprechende Liste setzen und zuletzt prüfen, für welche Elemente alle Bits gesetzt sind. Dieser Algorithmus hat die deutlich bessere Zeitkomplexität O(n).
GitHub: Advent of Code 2022 Tag 3 Lösung
Advent of Code 2022 – Tag 4 Lösung
Für Tag 4 habe ich eine Klasse SectionAssignment implementiert. Diese speichert den Start- und Endpunkt einer Sektion und bietet Methoden, um zu prüfen, ob eine Sektion eine andere umschließt bzw. ob zwei Sektionen teilweise überlappen:
record SectionAssignment(int start, int end) {
boolean fullyContains(SectionAssignment other) {
return start <= other.start && end >= other.end;
}
boolean overlaps(SectionAssignment other) {
return start >= other.start && start <= other.end
|| end >= other.start && end <= other.end
|| other.start >= start && other.start <= end
|| other.end >= start && other.end <= end;
}
}
Code-Sprache: Java (java)Mit dieser Klasse sind beide Teilaufgaben schnell gelöst.
GitHub: Advent of Code 2022 Tag 4 Lösung
Advent of Code 2022 – Tag 5 Lösung
An Tag 5 habe ich das Strategy Pattern angewendet, um die zwei Arten von Kränen zu implementieren und austauschbar zu machen:
Die move()-Methoden sehen wie folgt aus. Der CrateMover 9000 nimmt – nach und nach – die gewünschte Anzahl von Kisten von einem Stapel und stellt sie auf den anderen:
class CrateMover9000 implements CrateMover {
@Override
public void move(CrateStacks crateStacks, Move move) {
CrateStack fromStack = CrateMover.getSourceStack(crateStacks, move);
CrateStack toStack = CrateMover.getTargetStack(crateStacks, move);
for (int i = 0; i < move.number(); i++) {
toStack.push(fromStack.pop());
}
}
}Code-Sprache: Java (java)CrateMover 9001 benutzt einen Hilfs-Stack, um die Reihenfolge der Kisten zwischendurch umzudrehen:
class CrateMover9001 implements CrateMover {
@Override
public void move(CrateStacks crateStacks, Move move) {
CrateStack fromStack = CrateMover.getSourceStack(crateStacks, move);
CrateStack toStack = CrateMover.getTargetStack(crateStacks, move);
Deque<Crate> helperStack = new LinkedList<>();
for (int i = 0; i < move.number(); i++) {
helperStack.push(fromStack.pop());
}
while (!helperStack.isEmpty()) {
toStack.push(helperStack.pop());
}
}
}Code-Sprache: Java (java)GitHub: Advent of Code 2022 Tag 5 Lösung
Advent of Code 2022 – Tag 6 Lösung
Die Lösung für Tag 6 habe ich mit einem Set<Character> implementiert. Von jeder Position in der Zeichenkette werden die zurückliegenden Zeichen entsprechend der Marker-Länge in das Set geschrieben. Sobald das Set ein Zeichen bereits enthält, wird das Set zurückgesetzt und der Versuch beim nächsten Zeichen wiederholt – solange, bis der Marker (also die entsprechende Anzahl unterschiedlicher Zeichen) gefunden wurde.
GitHub: Advent of Code 2022 Tag 6 Lösung
Advent of Code 2022 – Tag 7 Lösung
Für Tag 7 habe ich einen Parser geschrieben, der aus den vorgegebenen Kommandos einen Verzeichnis-Baum aus folgenden Klassen (entsprechend dem Composite Pattern) aufbaut:
Für die Lösung von Teil eins müssen wir dann nur noch alle Unterverzeichnisse rekursiv durchgehen und diejenigen herausfiltern, die dem Größenkriterium entsprechen. Das lässt sich sehr elegant mit Javas Stream API lösen:
long sumOfSizes =
root.listWithAllSubDirectories().stream()
.mapToLong(Directory::totalSize)
.filter(totalSize -> totalSize <= maxTotalSize)
.sum();Code-Sprache: Java (java)Für Teil zwei müssen wir ebenfalls nach Größe filtern und dann das kleinste Verzeichnis bestimmen:
long freeSpace = 70_000_000 - root.totalSize();
long moreSpaceNeeded = 30_000_000 - freeSpace;
long smallestDirectoryToDeleteTotalSize =
root.listWithAllSubDirectories().stream()
.filter(directory -> directory.totalSize() >= moreSpaceNeeded)
.min(Comparator.comparing(Directory::totalSize))
.orElseThrow()
.totalSize();Code-Sprache: Java (java)GitHub: Advent of Code 2022 Tag 7 Lösung
Advent of Code 2022 – Tag 8 Lösung
Um die Aufgabe für Tag 8 zu lösen, brauchen wir keine Tricks, nur etwas Programmierarbeit. Wir können hier viel für die Verständlichkeit des Codes tun, indem wir Richtungen als Enum und Positionen als Record modellieren (die moveTo(...)-Methode ist mit der in Java 14 eingeführten Switch Expression implementiert):
enum Direction {
TOP,
RIGHT,
BOTTOM,
LEFT;
}
record Position(int column, int row) {
Position moveTo(Direction direction) {
return switch (direction) {
case TOP -> new Position(column, row - 1);
case RIGHT -> new Position(column + 1, row);
case BOTTOM -> new Position(column, row + 1);
case LEFT -> new Position(column - 1, row);
};
}
}Code-Sprache: Java (java)Mittels Position.moveTo(...) können wir dann von jedem Feld aus in die vier Himmelsrichtungen laufen und die Höhe der Bäume mit den Kriterien der jeweiligen Teilaufgabe abgleichen.
GitHub: Advent of Code 2022 Tag 8 Lösung
Advent of Code 2022 – Tag 9 Lösung
Den Position-Record können wir an Tag 9 erneut einsetzen, um die Knoten des Seils zu speichern und einen nach dem anderen entsprechend der vorgegebenen Regeln zu bewegen.
Die Position des jeweils letzten Knotens speichern wir in einem Set<Position>. Dessen Größe ist am Ende die Lösung der Aufgabe.
GitHub: Advent of Code 2022 Tag 9 Lösung
Advent of Code 2022 – Tag 10 Lösung
An Tag 10 müssen wir einen einfachen CPU-Emulator implementieren, der zwei verschiedene Operationen ausführen kann und während der Dauer dieser Operationen entsprechend des X-Registers und der aktuellen X-Position des Bildschirms auf diesem ein Pixel an- oder abschaltet. Die Implementierung erfordert weder Tricks noch Optimierungen.
Advent of Code 2022 – Tag 11 Lösung
Das Problem bei Teil zwei von Tag 11 ist, dass der "Worry Level" durch das Quadrieren schnell gigantische Ausmaße annimmt. Der Trick, um den Worry Level gering zu halten ohne dabei die Spiellogik zu ändern, ist es die Formel für die Erholung
worryLevel = worryLevel / 3;Code-Sprache: Java (java)zu ersetzen durch
worryLevel = worryLevel % reliefDivisorCode-Sprache: Java (java)wobei der reliefDivisor das Produkt aller verschiedenen Nenner der "Test"-Operationen ist.
Im Beispiel haben wir die folgenden vier Tests:
Test: divisible by 23
Test: divisible by 19
Test: divisible by 13
Test: divisible by 17Code-Sprache: Klartext (plaintext)Der reliefDivisor berechnet sich für das Beispiel als 23 × 19 × 13 × 17 = 96.577
Wenn wir nun zur Erholung den Worry Level auf den Rest bei Teilung durch diesen Wert setzen, ist sichergestellt, dass a) der Worry Level klein bleibt und b) sich das Ergebnis der "Test"-Operationen nicht ändern, egal bei welchem Affen sich ein Item befindet.
Advent of Code 2022 – Tag 12 Lösung
Für Tag 12 habe ich einen Breadth-First-Algorithmus implementiert, der von der Startposition zu allen erreichbaren Felder geht und dann von jedem erreichbaren Feld weiter zu allen von dort erreichbaren Feldern, usw. Bereits in einem vorherigen Schritt erreichte Felder werden ignoriert, da dorthin bereits ein kürzerer Weg gefunden wurde.
Für Teil zwei habe ich einfach den Algorithmus aus Teil eins auf alle möglichen Startfelder angewendet und den kürzesten aller kürzesten Wege bestimmt.
Die relativ geringe Größe des Problems hat diese triviale Lösung ermöglicht. Bei einer deutlich größeren Karte hätte man auch vom Ziel zurück zum Start gehen können und beim ersten Erreichen eines potentiellen Startfeldes die bis dahin zurückgelegten Felder zurückgeben können.
Advent of Code 2022 – Tag 13 Lösung
Für Tag 13 habe ich einen Comparator geschrieben, den ich sowohl in Teil eins verwende, um zu zählen, wie viele Paket-Paare in der richtigen Reihenfolge liegen, als auch in Teil zwei, um die Pakete mittels List.sort() zu sortieren.
Advent of Code 2022 – Tag 14 Lösung
Die Aufgabe von Tag 14 lässt sich sehr leicht mit einem Raster von Tiles lösen. Teil zwei erfordert heute keine besonderen Tricks.
Advent of Code 2022 – Tag 15 Lösung
Die triviale Lösung für Tag 15 funktioniert ebenfalls mit einem Raster. Bei Teil zwei erweist sich ein Raster allerdings als zu aufwändig.
Der Trick ist es, die durch die Sensoren abgedeckten Bereiche nicht in einem Raster, sondern mit Start- und Endpositionen zu speichern, dabei angrenzende oder überschneidende Bereiche zu kombinieren, und letztlich daraus die nicht abgedeckte Position zu ermitteln.
Advent of Code 2022 – Tag 16 Lösung
Die Aufgabe von Tag 16 kann mit einer Tiefensuche gelöst werden. Dabei gibt es nicht die eine Optimierung, sondern mehrere, die den Algorithmus jeweils um einen signifikanten Faktor schneller machen. Ich habe die folgenden vier Optimierungen angewendet:
- Der Algorithmus prüft in jeder Situation, ob dieselbe Situation (d. h. die Kombination aus Ventilstellungen, Aktorpositionen und abgelaufene Minuten) bereits zuvor aufgetreten ist. Wenn ja, und wenn diese Situation zu gleich viel oder mehr abgelassenem Druck geführt hat, muss der aktuelle Weg nicht weiter erkundet werden.
- In jeder Situation wird berechnet, wie viel Druck in der restlichen Zeit maximal abgelassen werden kann, wenn die Ventile nach absteigender Durchflussmenge geöffnet werden. Ergibt dies ein schlechteres Ergebnis als das aktuell beste, wird der Weg nicht weiter verfolgt.
- Bei dem Vergleich der Situation mit allen bisherigen Situationen gelten zwei Situationen auch dann als gleich, wenn die Positionen von dir und dem Elefanten vertauscht sind.
- Wenn erkannt wird, dass ein Aktor im Kreis gelaufen ist, ohne auf diesem ein Ventil geöffnet zu haben, wird der aktuelle Weg ebenfalls nicht weiter verfolgt.
Mit Hilfe dieser Optimierungen lässt sich Teilaufgabe zwei in etwa zwei Sekunden lösen.
Advent of Code 2022 – Tag 17 Lösung
Die Simulation für Tag 17 ist mit binären Operationen relativ schnell implementiert: "shift left" und "shift right", um den Felsen zu verschieben, "bitwise and" für die Kollisionsprüfung und "bitwise or" für die Manifestierung eines Felsens.
1.000.000.000.000 Felsen zu simulieren hätte mit meiner initialen Implementierung allerdings knapp 20 Stunden gedauert.
Der Trick für Teilaufgabe zwei besteht darin, Wiederholungen in den Fall- und Verschiebemustern zu finden. Dazu speichert mein Algorithmus eine Kombination aus aktuellem Felsen, aktueller Position in der Eingabe und Höhenprofil der oberen Felsenreihen als Key in einer Map mit aktuell höchstem Felsen und Anzahl der bisher gefallenen Felsen als Value.
Sobald dieselbe Kombination erneut auftritt (was überraschend schnell passiert), können wir mit Hilfe der Anzahl zwischenzeitlich gefallener Felsen und des zwischenzeitlichen Wachstums des Felsenberges in wenigen Millisekunden ein paar Milliarden Schritte überspringen. So lässt sich auch Teilaufgabe zwei in wenigen hundert Millisekunden lösen.
Advent of Code 2022 – Tag 18 Lösung
Teilaufgabe eins von Tag 18 ist schnell gelöst. Wir speichern alle Cubes in einem Set und iterieren dann über dieses und zählen – mit Hilfe von Set contains() – diejenigen Seiten, auf denen sich kein Cube befindet.
Teil zwei habe ich mit iterativem Floodfill gelöst. Dabei wird der Bereich außerhalb des Droplets Cube für Cube mit "Dampf" gefüllt. Jedesmal, wenn ein Cube nicht gefüllt werden kann, weil sich dort Lava befindet, wird ein Counter hochgezählt. Dieser Counter enthält am Ende die gesuchte Außenfläche.
Advent of Code 2022 – Tag 19 Lösung
Tag 19 erinnert an die Ventil-Aufgabe von Tag 16. Auch diese Aufgabe löst man mittels einer Tiefensuche und diversen Optimierungen:
- Unter der Annahme, dass wir in jeder Runde einen Geode-Roboter produzieren, können wir berechnen, wie viele Geoden von einer bestimmten Situation aus maximal noch produziert werden könnten. Ist diese Zahl kleiner als der aktuelle Bestwert, braucht der aktuelle Pfad nicht weiter erforscht zu werden.
- Wenn ein bestimmter Roboter auch in der vorherigen Runde hätte gekauft werden können – in der Runde aber gar kein Roboter gekauft wurde, dann brauchen wir ihn auch jetzt nicht zu kaufen. Sparen macht nur für einen anderen Roboter Sinn.
- In der letzten Minute brauchen wir keine Roboter zu produzieren.
- In der vorletzten Minute brauchen wir nur Geode-Roboter zu produzieren.
- In der vor-vorletzten Minute brauchen wir nur Geode-, Ore- oder Obsidian-Roboter (also keine Clay-Roboter) zu produzieren.
Meine Implementierung löst Teil eins in 4 Sekunden und Teil zwei in 52 Sekunden.
Advent of Code 2022 – Tag 20 Lösung
Die Lösung für Tag 20 lässt sich gut mit einer doppelt verketteten, zirkulären Liste implementieren. Teil eins kommt ganz ohne Optimierungen aus.
Bei Teil zwei müssten wir die Knoten mehrere Billionen Mal verschieben. Das können wir mit einer einfachen Formel auf ein paar Tausend reduzieren:
long distance = node.value() % (size - 1);Code-Sprache: Java (java)Der Trick dabei ist, nicht durch size (die Anzahl der Elemente) zu teilen, sondern durch size - 1. Du kannst das am Beispiel nachvollziehen: In der Liste der Länge 7 müsstest du ein Elemente sechs mal nach rechts schieben, damit es wieder an seinem Ausgangspunkt ankommt.
Advent of Code 2022 – Tag 21 Lösung
Für die Lösung von Tag 21 habe ich einen gerichteten azyklischen Graph (Directed acyclic graph) der mathematischen Operationen aufgebaut. Da die Ergebnisse mancher Operationen mehrfach verwendet werden, werden sie gespeichert, sobald sie einmal berechnet wurden.
Für Teil zwei habe ich zunächst versucht, eine Tiefensuche zu implementieren, d. h. verschiedene Werte für den “humn”-Knoten einzusetzen und dann zu prüfen, ob beide Operanden des “root”-Knotens gleich sind. Diese Variante habe ich noch dahingehend optimiert, dass ich zwischen zwei Versuchen nicht alle gespeicherten Ergebnisse gelöscht habe, sondern nur diejenigen auf dem Pfad von “root” zu “humn”. Doch auch so hätte die Berechnung zu lange gedauert, um diese Lösung zu akzeptieren.
Basierend auf der eben genannten Optimierung konnte ich eine deutlich schnellere Lösung implementieren. Und zwar können wir einfach die mathematischen Operationen auf dem Weg von “root” zu “humn” rückwärts ausführen und kommen so in wenigen Millisekunden zum Ergebnis.
Advent of Code 2022 – Tag 22 Lösung
Tag 22 fing einmal wieder leicht an. Mit einem zweidimensionalen Raster und ein paar Sonderbehandlungen für die Bereiche außerhalb der Karte ist Teil eins schnell gelöst.
Teil zwei ist deutlich kniffliger. Ich habe dazu Logik geschrieben, die die Koordinaten auf der Karte in Koordinaten auf einer Würfelseite mappt, dann die Würfenseite mittels einer zusätzlichen Liste von Kantenverbindungen (“Wurmlöchern”) verschiebt und dreht, und zuletzt die Koordinaten auf der verschobenen und gedrehten Würfelseite wieder zurück auf die Koordinaten der globalen Karte mappt.
Die Liste von Kantenverbindungen habe ich manuell aus meinem Puzzle Input generiert. Meine Lösung wird daher nicht ohne manuelle Anpassung der Kantenverbindungen bei allen funktionieren (es sei denn die Eingabe hat dasselbe Schnittmuster). Man kann die Kantenverbindungen auch algorithmisch bestimmen, aber dazu hat mir die Zeit gefehlt. Vielleicht hole ich das noch nach.
Advent of Code 2022 – Tag 23 Lösung
An Tag 23 können wir uns bereits bei der Lösung der ersten Teilaufgabe darauf einstellen, dass wir in Teilaufgabe zwei vermutlich mehr als zehn Runden simulieren müssen. Da das Feld so immer weiter wachsen wird, sollten wir die Elfen nicht in einem zweidimensionalen Array speichern.
Mein Algorithmus speichert die Elfen als Liste und zusätzlich deren Positionen in einem Set<Position>. So lässt sich die Kollisionsprüfung leicht mittelns Set.contains() lösen. Die Lösung von Teilaufgabe zwei dauert so weniger als eine Sekunde.
Advent of Code 2022 – Tag 24 Lösung
An Tag 24 müssen wir erneut einen Pathfinding-Algorithmus implementieren. Für die heutige Aufgabe ist eine Tiefensuche nicht geeignet, da sich die Karte bei jedem Zug ändert. Bei meinem Puzzle Input dauert es 95.400 Schritte, bis das Ziel das erste Mal erreicht wird und etwas über eine Minute, bis Teilaufgabe eins gelöst ist.
Eine Breitensuche löst Teil ein in nur 95 ms und Teil zwei in 130 ms.
Optimiert habe ich die Berechnung der freien Positionen. Statt die komplette Spielkarte für jeden Schritt zu simulieren, berechne ich mittels Modulo-Operation, ob ein Feld zu einer bestimmten Zeit frei ist oder nicht:
boolean isBlizzardAtMinute(Position pos, int minute) {
return tiles[modulo(pos.row() + minute, height)][pos.column()] == Tile.UP
|| tiles[modulo(pos.row() - minute, height)][pos.column()] == Tile.DOWN
|| tiles[pos.row()][modulo(pos.column() + minute, width)] == Tile.LEFT
|| tiles[pos.row()][modulo(pos.column() - minute, width)] == Tile.UP;
}Code-Sprache: Java (java)Advent of Code 2022 – Tag 25 Lösung
Die Lösung für Tag 25 besteht nur aus wenigen Zeilen Code. Der kniffligere Teil ist das Umwandeln einer Dezimalzahl in einen Snafu-String. Hier die entsprechende Methode:
static String toSnafuString(long decimal) {
StringBuilder result = new StringBuilder();
do {
long fives = (decimal + 2) / 5;
int digit = (int) (decimal - 5 * fives);
result.insert(0, convertDecimalToSnafuDigit(digit));
decimal = fives;
} while (decimal != 0);
return result.toString();
}Code-Sprache: Java (java)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