Advent of Code 2025 – Java Lösungen
5. Dezember 2025Dieses Jahr habe ich wieder beim Advent of Code mitgemacht. In diesem Artikel findest du meine Lösungen. Mein Ziel ist es, die Lösungen möglichst verständlich zu implementieren, nicht möglichst „smart“ oder kurz. Ich setze SonarQube ein, um eine möglichst hohe Code-Qualität zu erreichen.
Ich werden außerdem versuchen, möglichst viele Features des aktuellen Java 25 zu verwenden – einschließlich Preview-Features.
Wer Advent of Code noch nicht kennt: Es gibt – in eine vorweihnachtliche Geschichte verpackt – jeden Tag eine Programmieraufgabe. Oder besser gesagt: jeden Tag zwei – nämlich eine, die sich recht schnell lösen lässt – und eine zweite, bei der einem in der Regel die Zeit- oder Platzkomplexität der ersten Lösung einen Strich durch die Rechnung macht … und man noch mal von vorne überlegen muss.
Die Lösungen findest du in diesem GitHub-Projekt: Advent of Code 2025 – Java 25 Solutions.
Hier findest du meine Lösungen für Advent of Code 2015 und Advent of Code 2022.
Und jetzt geht's los!
Advent of Code 2025 – Tag 1 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 1 Aufgabe
Advent of Code 2025 beginnt recht knifflig!
Wir beginnen mit einem Parser für die Rotation:
private static int parseRotation(String s) {
int multiplicator = s.charAt(0) == 'R' ? 1 : -1;
return multiplicator * Integer.parseInt(s.substring(1));
}Code-Sprache: Java (java)Teil 1
Teil 1 ist noch schnell gelöst: wir müssen für jede Zeile der Eingabe die Rotationen ausführen und immer dann einen Counter hochzählen, wenn nach der Rotation der Zeiger auf der Null steht:
position = Math.floorMod(position + rotation, DIAL_SIZE);
if (position == 0) {
zeroCount++;
}Code-Sprache: Java (java)Wichtig ist dabei, dass wir Math.floorMod(...) verwenden und nicht den %-Operator, denn der berechnet in Java nicht den Modulo, sondern den Rest nach einer Teilung. Beispielsweise ergibt -140 % 100 nicht etwa 60, sondern -40. Um 60 zu erhalten, müssen wir Math.floorMod(-140, 100) aufrufen.
Teil 2
Teil 2 müssen wir komplett anders angehen. Zunächst einmal berechnen wir die neue Position ohne die Modulo-Operation:
position += rotation;Code-Sprache: Java (java)Jetzt müssen wir unterscheiden, ob wir rechts oder links herum gedreht haben. Bei einer Rechts-Rotation ist die Berechnung einfach: die Häufigkeit, mit der der Zeiger auf die Null gezeigt hat, ist die Position geteilt durch DIAL_SIZE:
if (rotation > 0) {
zeroCount += position / DIAL_SIZE;
}Code-Sprache: Java (java)Bei einer Links-Rotation ist die Berechnung komplizierter:
else {
zeroCount += (DIAL_SIZE - position) / DIAL_SIZE;
boolean startedAtZero = position - rotation == 0;
if (startedAtZero) {
zeroCount--;
}
}Code-Sprache: Java (java)Da wir mit einer negativen Zahl arbeiten, müssen wir diese zunächst von DIAL_SIZE subtrahieren. Dann ist noch ein Sonderfall zu beachten: Wenn der Zeiger zu Beginn der Operation auf Null steht, würde diese Null mitgezählt werden. Deshalb müssen wir in diesem Fall eine Null abziehen.
Der else-Block ließe sich auch „smart“ wie folgt schreiben:
else {
zeroCount += (DIAL_SIZE - position) / DIAL_SIZE - (position - rotation == 0 ? 1 : 0);
}Code-Sprache: Java (java)Ich halte aber die erste, etwas längere Variante für deutlich besser lesbar.
Zum Schluss müssen wir die Position wieder auf den Zahlenbereich 0–99 „normalisieren“:
position = Math.floorMod(position, DIAL_SIZE);Code-Sprache: Java (java)Die vollständige Lösung findest du hier: Advent of Code 2025 – Tag 1 Java-Lösung
Advent of Code 2025 – Tag 2 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 2 Aufgabe
Für Tag 2 schreibe ich zunächst einen Range-Klasse, die eine Zeile der Eingabe parsen und einen Stream aller Zahlen des Zahlenbereichs zurückgeben kann (diese Klasse werden wir praktischerweise an späteren Tagen wiederverwenden können):
public record Range(long from, long to) {
public static Range parse(String s) {
String[] split = s.split("-");
return new Range(Long.parseLong(split[0]), Long.parseLong(split[1]));
}
public LongStream ids() {
return LongStream.rangeClosed(from, to);
}
}Code-Sprache: Java (java)Teil 1 und 2 unterscheiden sich durch die maximale Anzahl Wiederholungen innerhalb einer ID. Bei Teil 1 sind es zwei Wiederholungen, bei Teil 2 gibt es keine Begrenzung – ich verwende Integer.MAX_VALUE.
Damit kann ich schon mal eine Hauptfunktion schreiben:
static long solve(String input, int maxRepetitions) {
return Stream.of(input.split(","))
.map(Range::parse)
.flatMapToLong(Range::ids)
.filter(id -> isInvalidId(id, maxRepetitions))
.sum();
}Code-Sprache: Java (java)Jetzt brauchen wir nur noch eine isInvalidId(...)-Methode.
Ich zeige sie dir zunächst und erkläre sie danach:
private static boolean isInvalidId(long id, int maxRepetitions) {
String idString = Long.toString(id);
int idLength = idString.length();
int minSequenceLength = Math.ceilDiv(idLength, maxRepetitions);
int maxSequenceLength = idLength / 2;
for (int sequenceLength = minSequenceLength;
sequenceLength <= maxSequenceLength;
sequenceLength++) {
if (containsOnlyRepetitions(idString, idLength, sequenceLength)) {
return true;
}
}
return false;
}Code-Sprache: Java (java)Zunächst wird hier die minmale und maximale Länge der sich wiederholenden Teilsequenz berechnet:
- Die minimale Länge ist die Länge der ID geteilt durch die maximale Anzahl an Wiederholungen (und das ganze aufgerundet). Für Teil 1 wäre das die Hälfte der ID-Länge, für Teil 2 in der Praxis immer 1, da
maxRepitionsdort jaInteger.MAX_VALUEIst. - Die maximale Länge ist die Länge der ID geteilt durch die minimale Anzahl an Wiederholungen (und das ganze abgerundet) – und die minimale Anzahl an Wiederholungen ist bei beiden Teilen der Aufgabe 2.
Dann iterieren wir von der minimalen zur maximalen Länge und prüfen, ob die ID nur aus Wiederholungen von Teilsequenzen eben dieser Länge besteht.
Und das passiert in der folgenden Methode, containsOnlyRepetitions(...):
private static boolean containsOnlyRepetitions(String idString,
int idLength,
int sequenceLength) {
if (idLength % sequenceLength != 0) {
return false;
}
String sequence = idString.substring(0, sequenceLength);
for (int i = sequenceLength; i < idLength; i += sequenceLength) {
if (!sequence.equals(idString.substring(i, i + sequenceLength))) {
return false;
}
}
return true;
}Code-Sprache: Java (java)Zu Beginn prüfen wir, ob die Länge der ID ein Vielfaches von der Länge der Teilsequenz ist. Wenn nicht, können wir direkt false zurückgeben (das wäre z. B. der Fall, wenn die Länge der ID 9 ist und die Länge der Teilsequenzen 2).
Danach bestimmen wir die Teilsequenz und prüfen mit einer simplen Schleife, ob die ID nur aus diesen Teilsequenzen besteht.
Die vollständige Lösung findest du hier: Advent of Code 2025 – Tag 2 Java-Lösung
Advent of Code 2025 – Tag 3 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 3 Aufgabe
Tag 3 lässt sich mit einem relativ simplen Algorithmus lösen.
Wir iterieren über die Anzahl der Batterien, die wir zusammenschalten wollen – und suchen in jeder Iteration in der Batterie-Bank das erste Vorkommnis der größten noch verbleibenden Zahl. Dabei starten wir rechts von der zuletzt verwendeten Batterie und enden bei [Bankgröße minus Anzahl noch benötigter Batterien].
Ich zeige dir das am Beispiel der Batterie-Bank 234234234234278 (Länge: 15) und der 12 als Anzahl an zusammengeschalteten Batterien:
Wir suchen in den ersten vier Batterien nach der größten (um danach noch mindestens elf weitere Batterien zur Verfügung zu haben):
234234234234278
^^^^Code-Sprache: Klartext (plaintext)Die größte Zahl ist die 4 an der dritten Position – die Batterien davor können wir ignorieren (durch einen Punkt ersetzt):
..4234234234278
^Code-Sprache: Klartext (plaintext)Die restlichen elf Batterien müssen wir im verbleibenden Bereich 234234234278 (Länge: 12) suchen. Dieses Mal dürfen wir nur in den ersten zwei Batterien nach der größten suchen, um danach noch mindestens zehn weitere zu haben:
..4234234234278
^^Code-Sprache: Klartext (plaintext)Die größte Zahl ist die 3 – die davor können wir wieder ignorieren:
..4.34234234278
^ Code-Sprache: Klartext (plaintext)Nach der 3 verbleiben zehn weitere Batterien. Wir brauchen insgesamt zwölf, haben zwei, also brauchen wir noch alle zehn verbleibenden:
..4.34234234278
^^^^^^^^^^Code-Sprache: Klartext (plaintext)Und damit haben wir das Ergebnis: 434234234278
Die Implementierung dieses Algorithmus findest du hier: Advent of Code 2025 – Tag 3 Java-Lösung
Advent of Code 2025 – Tag 4 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 4 Aufgabe
An Tag 4 können wir das Entfernen der Rollen durch den Gabelstapler einfach simulieren. Über einen speziellen Algorithmus müssen wir uns heute nicht den Kopf zerbrechen.
Wir iterieren dazu über die gesamte Eingabematrix und zählen für jedes Feld die benachbarten Rollen. Sind es weniger als 4, markieren wir das Feld als erreichbar (oder speichern es in einer Liste).
Für Teil 1 geben wir die Anzahl erreichbarer Felder zurück.
Für Teil 2 entfernen wir sie aus der Matrix und wiederholen den gesamten Prozess – so lange, bis keine weiteren Rollen entfernt werden können.
Meine Lösung findest du hier: Advent of Code 2025 – Tag 4 Java-Lösung
Advent of Code 2025 – Tag 5 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 5 Aufgabe
An Tag 5 können wir die Range-Klasse von Tag 1 wiederverwenden und erweitern!
Für Teil 1 fügen wir eine contains(...)-Methode ein, mit der wir dann einfach für alle Zutaten prüfen, ob sie in den Ranges der frischen Zutaten enthalten sind:
public record Range(long from, long to) {
. . .
boolean contains(long value) {
return value >= from && value <= to;
}
}Code-Sprache: Java (java)Teil 2 hört sich erstmal simpel an: Müssen wir einfach nur die Längen aller Ranges aufaddieren?
Natürlich nicht ;-)
Denn die Ranges überschneiden sich teilweise – und die Zutaten der sich überschneidenen Bereiche würden wir so mehrfach zählen.
Anstatt nun die sich überschneidenen Bereiche wieder herauszurechnen, bin ich einen anderen Weg gegangen: Ich habe ein RangeSet implementiert, das nur disjunkte Ranges enthalten darf – also solche, die sich nicht überschneiden. Diesem RangeSet werden alle Ranges hinzugefügt – und beim Hinzufügen prüft das RangeSet, ob sich der hinzugefügte Range mit einem der bestehenden Ranges überschneidet. Wenn ja, werden bestehender Range und hinzugefügter Range gemerged. Hier ein Beispiel:
Ranges im Set: ....xxxxx........xxxxxx......xxxxx....
Neuer Range: .......xxxxx..........................
Gemergter Range: xxxxxxxx
Ranges nach Merge: ....xxxxxxxx.....xxxxxx......xxxxx....Code-Sprache: Klartext (plaintext)Jetzt kann es allerdings auch passieren, dass der neue Range sich mit mehreren bestehenden Ranges überschneidet. Daher wird für den gemergten Range erneut geprüft, ob dieser sich mit den bestehenden Ranges überschneidet und ggf. noch einmal gemerged. Das wird solange wiederholt, bis es keine Überschneidungen mehr gibt:
Ranges im Set: ....xxxxx........xxxxxx......xxxxx....
Neuer Range: .......xxxxxxxxxxxxx..................
1. gemergter Range: xxxxxxxxxxxxxxxx
2. gemergter Range: xxxxxxxxxxxxxxxxxxx
Ranges nach Merge: ....xxxxxxxxxxxxxxxxxxx......xxxxx....Code-Sprache: Klartext (plaintext)Beim Mergen zweier Ranges müssen vier Fälle unterschieden werden:
- Range 1 enthält Range 2 vollständig
- Range 2 enthält Range 1 vollständig
- Range 1 überschneidet sich, von links kommend, mit Range 2 (oder berührt Range 2)
- Range 2 überschneidet sich, von links kommend, mit Range 1 (oder berührt Range 1)
Nachdem so alle Ranges von frischen Zutaten dem RangeSet hinzugefügt und Überschneidungen gemerged wurden, müssen wir tatsächlich nur noch die Längen aller diskunkten Ranges aufaddieren.
Meine Lösung findest du hier: Advent of Code 2025 – Tag 6 Java-Lösung
Die Range- und RangeSet-Klassen findest du im common-Paket.
Advent of Code 2025 – Tag 6 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 6 Aufgabe
An Tag 6 müssen wir Zahlen aus einer Matrix auslesen und diese dann addieren oder multiplizieren – dabei müssen wir in Teil 1 die Zahlen zweilenweise lesen und in Teil 2 spaltenweise.
Teil 1 ist schnell erledigt: Wir splitten die Zeile mit dem regulären Ausdruck „\s+“ (= mindestens ein Leerzeichen):
private static final Pattern PATTERN = Pattern.compile("\\s+");
. . .
String[] numbers = PATTERN.split(line.strip());Code-Sprache: Java (java)Dann müssen wir die Teilstrings nur noch in Zahlen konvertieren, diese in Listen für die „Probleme“ sammeln und zuletzt alle Zahlen innerhalb dieser Listen addieren oder multiplizieren.
Für Teil 2 müssen wir die Textdatei nicht von oben nach unten lesen, sondern von links nach rechts (oder rechts nach links – beides ist gleich gut). Innerhalb einer Spalte lesen wir eine Zahl, indem wir die Ziffern von oben nach unten lesen. Leerzeichen sehen wir einfach als Nullen an. Sobald wir in einer gesamten Spalte eine Null lesen, d. h. alle Zeilen in dieser Spalte leer waren, wissen wir, dass wir alle Spalten eines „Problems“ gelesen haben und beginnen ab der nächsten Spalte, die Zahlen für das nächste „Problem“ zu lesen.
Die Methode readNumbersInColumns(...) zeigt, wie über die Spalten iteriert wird:
private static void readNumbersInColumns(List<String> lines, List<Problem> problems) {
int columnCount = lines.getFirst().length();
int problemIndex = 0;
for (int column = 0; column < columnCount; column++) {
long number = readNumberInColumn(lines, column);
if (number != 0) {
problems.get(problemIndex).addNumber(number);
} else { // separator column
problemIndex++;
}
}
}Code-Sprache: Java (java)Die Methode readnumberInColumn(...) liest eine Zahl aus einer Spalte, indem sie die Ziffern von oben nach unten liest:
private static long readNumberInColumn(List<String> lines, int column) {
long number = 0;
for (int row = 0; row < lines.size() - 1; row++) {
char digit = lines.get(row).charAt(column);
if (digit != ' ') {
number = number * 10 + (digit - '0');
}
}
return number;
}Code-Sprache: Java (java)Die vollständige Lösung findest du hier: Advent of Code 2025 – Tag 6 Java-Lösung
Advent of Code 2025 – Tag 7 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 7 Aufgabe
Teil 1 ist schnell gelöst – im Grunde müssen wir nur die Splitter im Puzzle Input zählen.
Eine triviale Lösung für Teil 2 wäre eine Rekursion, die für jeden Pfad, den ein Tachyon nimmt, prüft, wie viele weitere mögliche Pfade durch die Anlage es gibt:
static long solve(List<String> input) {
int startPosition = input.getFirst().indexOf('S');
return solve(input, 2, startPosition);
}
private static long solve(List<String> input, int row, int col) {
if (row + 2 > input.size()) {
return 1;
}
if (input.get(row).charAt(col) == '^') {
return solve(input, row + 2, col - 1) + solve(input, row + 2, col + 1);
} else {
return solve(input, row + 2, col);
}
}Code-Sprache: Java (java)Dabei würden wir aber – ähnlich wie bei der rekursiven Berechnung der Fibonacci-Funktion – die weiteren Pfade von zahlreichen Positionen aus (zu denen wir auf unterschiedlichen Wegen gelangt sind) mehrfach berechnen. Die Zeitkomplexität wäre exponentiell!
Wesentlich einfacher ist es, die Anzahl der Timelines, auf der ein Punkt erreicht werden kann, auf der Karte zu speichern, und dabei zusammentreffende Timelines zu addieren:
. . . . . . . 1 . . . . . . .
. . . . . . 1 ^ 1 . . . . . .
. . . . . . 1 . 1 . . . . . .
. . . . . 1 ^ 2 ^ 1 . . . . .
. . . . . 1 . 2 . 1 . . . . .
. . . . 1 ^ 3 ^ 3 ^ 1 . . . .
. . . . 1 . 3 . 3 . 1 . . . .
. . . 1 ^ 4 ^ 3 3 1 ^ 1 . . .
. . . 1 . 4 . 3 3 1 . 1 . . .
. . 1 ^ 5 ^ 4 3 4 ^ 2 ^ 1 . .
. . 1 . 5 . 4 3 4 . 2 . 1 . .
. 1 ^ 1 5 4 ^ 7 4 . 2 1 ^ 1 .
. 1 . 1 5 4 . 7 4 . 2 1 . 1 .
1 ^ 2 ^ 10 ^ 11 ^ 11 ^ 2 1 1 ^ 1
1 . 2 . 10 . 11 . 11 . 2 1 1 . 1Code-Sprache: Klartext (plaintext)Dann müssen wir am Ende nur noch die Zahlen der letzten Reihe aufaddieren, um die gesamte Anzahl an Timelines zu erhalten.
Meine Lösung findest du hier: Advent of Code 2025 – Tag 7 Java-Lösung
Advent of Code 2025 – Tag 8 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 8 Aufgabe
An Tag 8 haben wir zwei grundlegende Herausforderungen zu lösen:
- Wir müssen in jeder Iteration ein noch nicht genutztes Paar von Anschlussdosen mit der kürzesten Entfernung zueinander finden.
- Wir müssen Paare von Anschlussdosen zu Schaltkreisen zusammenfügen.
Herausforderung 1: Verbleibendes Paar mit der kürzesten Entfernung finden
Ein trivialer Ansatz ist es, die bereits genutzten Paare in einem Set zu speichern und in jeder Iteration für alle verbleibenden Paare die Entfernung zueinander zu berechnen und dabei das Paar mit der kürzesten Entfernung zu bestimmen. Die Zeitkomplexität pro Iteration ist O(n²) – bei m Iterationen ist das O(m * n²).
Ein etwas besserer Ansatz ist es, vorab die Entfernungen aller möglichen Paare zu berechnen und in einer Distanz-Matrix zu speichern – und dann in jeder Iteration ohne erneute Berechnung der Entfernung das Paar mit der kürzesten Entfernung zu bestimmen. Das wäre zwar deutlich schneller, aber die Zeitkomplexität bleibt unverändert – O(m * n²).
Der beste Ansatz ist es, vorab die Paare nach ihrer Entfernung zu sortieren – dann müssen wir im weiteren Verlauf lediglich über die Liste der sortierten Paare iterieren. Die Zeitkomplexität ist nur noch O(n² + m).
Im Code habe ich dafür einen Record angelegt, der ein Paar von Anschlussdosen (in Form von Point3D-Objekten) und deren Entfernung zueinander speichert:
record Point3DPairWithDistance(Point3D first, Point3D second, double distance) {}Code-Sprache: Java (java)Der folgende Code wandelt eine Liste von Point3D-Objekten in eine Liste dieser Records um:
private static List<Point3DPairWithDistance> computePairsWithDistance(
List<Point3D> points) {
int numberOfPoints = points.size();
List<Point3DPairWithDistance> pairs = new ArrayList<>();
for (int i = 0; i < numberOfPoints; i++) {
Point3D first = points.get(i);
for (int j = i + 1; j < numberOfPoints; j++) {
Point3D second = points.get(j);
pairs.add(new Point3DPairWithDistance(first, second, first.distanceTo(second)));
}
}
return pairs;
}Code-Sprache: Java (java)Und dann muss diese Liste nur noch sortiert werden:
pairs.sort(Comparator.comparing(Point3DPairWithDistance::distance));Code-Sprache: Java (java)Herausforderung 2: Anschlussdosen zu Schaltkreisen zusammenfügen
Um die Anschlussdosen zu Schaltkreisen zusammenzufügen, lege ich eine Klasse CircuitSet an. Diese speichert eine Liste von Schaltkreisen, wobei ein Schaltkreis ein Set von Dosen ist, und eine Dose wiederum durch ein Point3D-Objekt dargestellt wird:
private final List<Set<Point3D>> circuits = new ArrayList<>();Code-Sprache: Java (java)Dem Konstruktor übergebe ich alle Dosen, und dieser legt zunächst für jede einzelne Dose einen Schaltkreis an:
CircuitSet(List<Point3D> points) {
for (Point3D point : points) {
Set<Point3D> circuit = new HashSet<>();
circuit.add(point);
circuits.add(newCircuit);
}
}Code-Sprache: Java (java)Um nun ein Paar von Dosen hinzuzufügen, suche ich zunächst, in welchen Schaltkreisen die Dosen enthalten sind. Sind diese im gleichen Schaltkreis, ist keine weitere Aktion erforderlich. Sind sie in unterschiedlichen Schaltkreisen, merge ich Schaltkreis A in Schaltkreis B und entferne dann Schaltkreis A:
void add(Point3DPairWithDistance pair) {
int firstIndex = -1;
int secondIndex = -1;
for (int i = 0; i < circuits.size(); i++) {
Set<Point3D> circuit = circuits.get(i);
if (circuit.contains(pair.first())) {
firstIndex = i;
}
if (circuit.contains(pair.second())) {
secondIndex = i;
}
}
// Connect circuits if both are in different ones
if (firstIndex != secondIndex) {
circuits.get(firstIndex).addAll(circuits.get(secondIndex));
circuits.remove(secondIndex);
}
}Code-Sprache: Java (java)Die vollständige Lösung findest du hier: Advent of Code 2025 – Tag 8 Java-Lösung
Advent of Code 2025 – Tag 9 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 9 Aufgabe
An Tag 9 war Teil 1 einmal wieder schnell durch einen Brute-Force-Ansatz erledigt: einfach für alle möglichen Kombinationen aus zwei roten Fliesen die Fläche berechnen und davon die Größe bestimmen.
An Teil 2 musste ich länger knobeln – und hier wird es sicher zahlreiche unterschiedliche Lösungen geben.
Zunächst habe ich eine zweidimensionales Matrix angelegt, dort alle Kanten „eingezeichnet“ und dann den Bereich außerhalb der Kanten mit Floodfill gefüllt. Warum außerhalb? Das war einfacher als innerhalb, da ich dazu bloß noch einen fliesenbreiten Rand um die Matrix legen musste und dann an Position (0, 0) mit dem Füllen beginnen konnte.
Danach habe ich wieder mit dem Brute-Force-Ansatz für alle möglichen Kombinationen aus zwei roten Fliesen geprüft, ob sich eine Fliese des dadurch aufgespannten Rechtecks in dem mit Floodfill gefüllten Bereich (also außerhalb der roten und grünen Fliesen) befindet – und dann von allen Rechtecken, für die das nicht der Fall war, das größte ausgewählt.
Mit den Beispiel-Daten hat das auch gut funktioniert – beim echten Puzzle Input stieß dieser Algorithmus allerdings an seine Grenzen, denn die Matrix wird dabei knapp 100.000 x 100.000, also zehn Milliarden Fliesen groß. Das Zeichnen des Randes ging noch einigermaßen schnell, aber Floodfill war einige Minuten beschäftigt.
Ich habe lange über einen komplett anderen, mathematischeren Algorithmus nachgedacht – bin dann aber letztlich auf die Idee gekommen, die Koordinaten zu „komprimieren“. Denn von den 100.000 x 100.000 möglichen X- und Y-Koordinaten können bei 496 roten Fliesen ja auch maximal jeweils 496 unterschiedliche genutzt sein – bzw. sogar nur 248, denn jeweils zwei Fliesen befinden sich ja an denselben X-Koordinaten, und jeweils zwei Fliesen befinden sich an denselben Y-Koordinaten.
Ich habe dazu alle verwendeten X- und Y-Koordinaten gesammelt, sortiert, und dann aus allen Positionen komprimierte Positionen gemacht, indem ich zusätzlich zu den tatsächlichen Koordinaten auch die Indizes der X- und Y-Koordinaten in der jeweiligen sortierten Koordinatenliste gespeichert habe.
So sieht eine kom[primierte Position aus:
record CompressedPosition(int row, int col, int compressedRow, int compressedCol) {}Code-Sprache: Java (java)Und so der „Kompressionsalgorithmus“:
static List<CompressedPosition> compress(List<Position> positions) {
Set<Integer> rows = new HashSet<>();
Set<Integer> cols = new HashSet<>();
for (Position position : positions) {
rows.add(position.row());
cols.add(position.col());
}
Map<Integer, Integer> rowIndices = getIndexMap(rows);
Map<Integer, Integer> colIndices = getIndexMap(cols);
return positions.stream()
.map(position -> new CompressedPosition(
position.row(), position.col(),
rowIndices.get(position.row()), colIndices.get(position.col())))
.toList();
}
private static Map<Integer, Integer> getIndexMap(Set<Integer> cols) {
List<Integer> sorted = new ArrayList<>(cols);
Collections.sort(sorted);
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < sorted.size(); i++) {
indexMap.put(sorted.get(i), i);
}
return indexMap;
}Code-Sprache: Java (java)Danach konnte ich den gesamten Algorithmus einfach auf den komprimierten Koordinaten ausführen (Größe: 248 x 248) und musste lediglich für die Berechnung der Größe eines Rechtecks auf die unkomprimierten Koordinaten zurückgreifen.
Der Brute-Force-Ansatz des Prüfens aller möglichen Kombinationen zweier roter Fliesen sowie der Brute-Force-Ansatz des Prüfens, ob ein Rechteck eine Fliese außerhalb des rot-grünen-Bereichs umfasst, stellt offenbar kein Problem dar, denn die Lösung von Teil 2 dauert so weniger als 100 ms.
Hier findest du meine vollständige Lösung: Advent of Code 2025 – Tag 9 Java-Lösung
Die Komprimierung findest du in der Klasse PositionsCompressor, das Zeichnen des Randes und den FloodFill-Algorithmus in TileFloor und das Berechnen der Flächen und die Bestimmung der größten Fläche in MovieTheater.
Advent of Code 2025 – Tag 10 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 10 Aufgabe
Teil 1
Am zehnten Tag ist Teil 1 schnell gelöst, sobald man sich einer Sache bewusst wird:
Jeder Schalter muss maximal ein Mal gedrückt werden – denn ein zweites Mal macht die Änderung wieder rückgängig. Drei Mal drücken führt zum gleichen Ergebnis wie ein Mal drücken, usw.
Die maximale Anzahl Button-Konfigurationen im Puzzle Input ist 13. Damit kommen wir auf maximal 213-1, also 8.191 mögliche Kombinationen, die Buttons zu drücken. Somit sind der eingesetzte Algorithmus und die Art und Weise, wie wir den Zustand der Lichter und die Button-Konfigurationen speichern, ziemlich egal.
Ich habe eine Breitensuche implementiert, und den Status der Lichter und die Button-Konfigurationen habe ich als Bitset in einem int gespeichert. Damit reduziert sich die Berechnung eines Schaltvorgangs auf eine einzige XOR-Operation:
record Lights(int bits) {
. . .
Lights toggle(ButtonWiring buttonWiring) {
return new Lights(bits ^ buttonWiring.bits());
}
}Code-Sprache: Java (java)In der Queue für die Breitensuche speichere ich ComputationState-Objekte, die wie folgt aussehen:
private record ComputationState(Lights lights, int buttonIndex, int depth) {}Code-Sprache: Java (java)Ein ComputationState-Objekt enthält den Zustand der Lichter, den Index des nächsten Buttons (wir probieren in jedem Zustand alle Buttons rechts des zuletzt gedrückten Buttons aus) und die aktuelle Suchtiefe. Die Breitensuche ist dann in rund einem Dutzend Zeilen Code implementiert:
int solvePart1() {
Queue<ComputationState> queue = new ArrayDeque<>();
queue.add(new ComputationState(new Lights(), 0, 0));
while (!queue.isEmpty()) {
ComputationState state = queue.remove();
for (int i = state.buttonIndex(); i < buttonWirings.size(); i++) {
Lights lights = state.lights().toggle(buttonWirings.get(i));
if (lights.equals(lightsGoal)) {
return state.depth() + 1;
} else {
queue.add(new ComputationState(lights, i + 1, state.depth() + 1));
}
}
}
throw new IllegalStateException("No solution found");
}Code-Sprache: Java (java)Teil 2
Für Teil 2 habe ich mehrere Stunden mit verschiednen Brute-Force-Ansätzen experimentiert, bin dann aber zu dem Schluss gekommen, dass das Problem dafür zu groß ist – selbst mit den smartesten Abbruchbedingungen.
Das Problem muss stattdessen mathematisch angegangen werden! Wenn wir die Button-Konfigurationen als Vektoren von Nullen und Eisen darstellen (bi), und den Zielzustand als Vektor von Joltage-Leveln (j), dann können wir folgende Gleichung aufstellen, wobei xi die Häufigkeiten sind, mit der die jeweiligen Buttons gedrückt werden müssen:
Dann müssen wir „nur noch“ diejenige Lösung dieser Gleichung finden, bei der die Summe x1 + x2 + ... + xn am kleinsten ist.
Lösen können wir diese Gleichung mit dem Gaußsches Eliminationsverfahren. Ich habe in 280 Zeilen Java-Code – und unter Verwendung von Primitive Types in instanceof – eine vereinfachte Variante davon implementiert, die mit maximal drei unbekannten Variablen umgehen kann. Du findest diese Implementierung in der Klasse GaussianElimination.
Die vollständige Lösung findest du hier: Advent of Code 2025 – Tag 10 Java-Lösung
Advent of Code 2025 – Tag 11 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 11 Aufgabe
An Tag 11 müssen wir einen gerichteten azyklischen Graph aufbauen und darin die Anzahl der möglichen Pfade zwischen zwei Punkten finden. In Teil 2 kommt erschwerend hinzu, dass die Pfade durch zwei weitere Punkte gehen müssen.
Teil 1
Teil 1 lässt sich mit einer Tiefensuche lösen und einem Cache, in dem wir für diejenigen Knotenpunkte, die wir vollständig abgearbeitet haben, speichern, auf wie vielen Pfaden wir von dort das Ziel erreicht haben. Sobald wir einen Kontenpunkt erreichen, der in diesem Cache liegt, brauchen wir die Wege von dort nicht noch einmal zu überprüfen.
Dieser „Cache“ ist zunächst einfach nur ein Feld pathsFoundFromHere in den Knoten-Objekten, welches zu Beginn null ist und dann während der Rekursion nach und nach gesetzt wird:
class Device {
private final String name;
private final String[] outputNames;
private Integer pathsFoundFromHere;
. . .
}Code-Sprache: Java (java)Am Ende der Rekursion liegt im pathsFoundFromHere-Feld des Startknotens die Lösung. Dank des Caches dauert die Suche weniger als einer Millisekunde.
Teil 2
Für Teil 2 habe ich das pathsFoundFromHere-Feld durch ein visitedInfo-Feld ersetzt, in dem ich die Anzahl der Pfade zum Ziel aufgeschlüsselt habe in:
- Anzahl der Pfade, auf denen die Knoten
dacundfftliegen - Anzahl der Pfade, auf denen nur der Knoten
dacliegt - Anzahl der Pfade, auf denen nur der Knoten
fftliegt - Anzahl der Pfade, auf denen weder der Knoten
dacnoch der Knotenfftliegt
So sieht die zugehörige Klasse VistedInfo aus:
class VisitedInfo {
private long pathsWithBothFoundFromHere;
private long pathsWithOnlyDacFromHere;
private long pathsWithOnlyFftFromHere;
private long pathsWithNoneFromHere;
. . .
}Code-Sprache: Java (java)Sobald ich von einem Knoten aus einen Knoten erreiche, der bereits abgearbeitete wurde, addiere ich die VisitedInfo des erreichten Knotens zur VisistedInfo des aktuellen Knotens – die Parameter dac und fft geben dabei an, ob der aktuelle Knoten dac oder fft ist:
void add(VisitedInfo other, boolean dac, boolean fft) {
if (dac) {
pathsWithBothFoundFromHere += other.pathsWithBothFoundFromHere
+ other.pathsWithOnlyFftFromHere;
pathsWithOnlyDacFromHere += other.pathsWithOnlyDacFromHere
+ other.pathsWithNoneFromHere;
} else if (fft) {
pathsWithBothFoundFromHere += other.pathsWithBothFoundFromHere
+ other.pathsWithOnlyDacFromHere;
pathsWithOnlyFftFromHere += other.pathsWithOnlyFftFromHere
+ other.pathsWithNoneFromHere;
} else {
pathsWithBothFoundFromHere += other.pathsWithBothFoundFromHere;
pathsWithOnlyDacFromHere += other.pathsWithOnlyDacFromHere;
pathsWithOnlyFftFromHere += other.pathsWithOnlyFftFromHere;
pathsWithNoneFromHere += other.pathsWithNoneFromHere;
}
}Code-Sprache: Java (java)Die Abarbeitung des gesamten Graphen dauert so auch bei Teil 2 weniger als eine Millisekunde, und die Lösung finden wir am Ende im Feld visitedInfo.pathsWithBothFoundFromHere des Startknotens.
Die vollständige Lösung findest du hier: Advent of Code 2025 – Tag 11 Java-Lösung
Advent of Code 2025 – Tag 12 Java-Lösung
Aufgabe: Advent of Code 2025 – Tag 12 Aufgabe
Tag 12 habe ich zunächst mit einer Tiefensuche implementiert: Ich lege jedes Geschenk nach und nach in allen möglichen Rotationen und Spiegelungen unter den Baum – solange, bis alle Geschenke entweder passen ... oder nicht.
Für die Beispieldaten funktioniert das noch – für den eigentlichen Puzzle Input aber nicht mehr, da die Anzahl an möglichen Kombinationen astronomisch hoch sind.
Die Suche nach möglichen vorzeitigen Abbruchbedingungen führte dieses Mal zum Glück schnell zu einem Ergebnis: Wenn man die Anzahl der Pixel aller zu platzierenden Geschenke mit der Anzahl der freien Pixel unter dem Baum vergleicht, fällt auf, dass unter 546 der 1.000 Weihnachtsbäume gar nicht genug Platz für alle Geschenke sein kann – egal wie man sie anordnet:
int pixelsAvailable = width * height;
int pixelsRequired = 0;
List<Present> presentsToFit = new ArrayList<>();
for (int presentIndex = 0; presentIndex < presentCounts.length; presentIndex++) {
int presentCount = presentCounts[presentIndex];
for (int i = 0; i < presentCount; i++) {
Present present = presents.get(presentIndex);
presentsToFit.add(present);
Shape shape = present.shapeRotations().getFirst();
pixelsRequired += shape.pixelCount();
}
}
if (pixelsRequired > pixelsAvailable) {
return false;
}Code-Sprache: Java (java)Für die restlichen 454 Weihnachtsbäume findet die Tiefensuche in wenigen Millisekunden eine Lösung. Das machte mich etwas stutzig.
Ich habe dann noch eine zweite Abbruchbedingung eingebaut: Wenn der Platz unter dem Baum in drei mal drei Pixel große Raster eingeteilt wird und wir jedes Geschenk in ein solches Feld legen, ohne dessen Muster zu betrachten – passen dann alle Geschenke?
Im Code sind das wenige Zeilen:
int numberOfPresentsThatWouldFitRegardlessOfTheirShape = (width / 3) * (height / 3);
if (presentsToFit.size() <= numberOfPresentsThatWouldFitRegardlessOfTheirShape) {
return true;
}Code-Sprache: Java (java)Und tatsächlich ist das der Fall für alle verbleibenden 546 Weihnachtsbäume.
Die Tiefensuche brauchen wir also gar nicht, um die Lösung zu berechnen. Ich habe sie trotzdem im Code gelassen, um die Beispielaufgabe zu lösen. Du findest sie in der Klasse Tree.
Hier findest du meine vollständige Implementierung: Advent of Code 2025 – Tag 12 Java-Lösung
Das Ende
Und damit ist Advent of Code 2025 auch schon zu Ende gegangen. In diesem Jahr dauerte Advent of Code nur 12 Tage statt der üblichen 24. Der Entwickler erklärt hier, dass ihm der Aufwand, 24 Rätsel zu erstellen, einfach zu hoch geworden sei.
Ich muss zugeben, ich bin ebenfalls erleichtert, denn auch das Lösen der Aufgaben kostet viel Zeit. Zwölf Aufgaben sind für meinen Geschmack vollkommen ausreichend. Und so werde ich vielleicht auch regelmäßiger teilnehmen – ich freue mich jetzt schon auf 2026!