Advent of Code 2025: Effiziente Algorithmen für Range-Berechnungen

Die Advent of Code 2025-Challenge stellt Entwickler vor komplexe Probleme, die oft mit ineffizienten Brute-Force-Methoden gelöst werden können – aber nicht sollten. Tag 5 der Herausforderung konzentriert sich auf die Verarbeitung von Zahlenbereichen und zeigt, wie strategische Algorithmen die Rechenleistung um ein Vielfaches steigern.

Vom Brute-Force zum intelligenten Algorithmus

Ein naiver Ansatz würde alle 1.000 gegebenen IDs nacheinander gegen fast 200 Bereiche prüfen. Bei bis zu 200.000 Operationen pro Eingabe wäre dies zwar technisch machbar – die Ausführung würde vermutlich in Millisekunden abgeschlossen sein – doch die eigentliche Herausforderung liegt im Verständnis, dass selbst kleine Verbesserungen in der Effizienz entscheidend sein können. Die Kernfrage lautet daher: Wie lässt sich die Komplexität reduzieren, ohne die Genauigkeit zu beeinträchtigen?

Die Lösung liegt in der Sortierung. Durch das Sortieren der IDs in aufsteigender Reihenfolge und der Bereiche nach ihrem unteren Grenzwert wird die Suche nach Übereinstimmungen beschleunigt. Statt 1.000 Iterationen über alle IDs und 200 Prüfungen pro Iteration reduziert sich die Anzahl der notwendigen Operationen auf etwa 200 – eine deutliche Optimierung. Der Schlüssel liegt darin, dass nach dem Sortieren nur noch die Bereiche durchsucht werden müssen, bis der erste passende Wert gefunden oder der Bereich überschritten wird. Dies minimiert die Anzahl der Vergleiche und verbessert die Laufzeit signifikant.

Implementierung der optimierten Strategie

Die Umsetzung des Algorithmus erfordert präzise Datenverarbeitung. Zunächst müssen die Eingabedaten in zwei Listen aufgeteilt und konvertiert werden:

let [ranges, ids] = input.split('\n\n');

ranges = ranges
  .split('\n')
  .map(str => str.split('-').map(Number))
  .sort((a, b) => a[0] - b[0]);

ids = ids
  .split('\n')
  .map(Number)
  .sort((a, b) => a - b);

Die erste Liste enthält die sortierten Bereiche, die zweite die sortierten IDs. Anschließend wird jeder Bereich durchlaufen und nach IDs gefiltert, die innerhalb der Grenzen liegen. Um Mehrfachzählungen zu vermeiden, werden die gefundenen IDs aus der Liste entfernt:

let count = ranges.reduce((total, range) => {
  const matches = ids.filter(id => id >= range[0] && id <= range[1]);
  if (matches.length > 0) {
    ids.splice(ids.indexOf(matches[0]), matches.length);
    total += matches.length;
  }
  return total;
}, 0);

Diese Methode stellt sicher, dass jede ID nur einmal gezählt wird, während die Sortierung die Effizienz der Suche maximiert. Tests mit den Beispielwerten bestätigen die Korrektheit des Ansatzes und liefern das erwartete Ergebnis.

Erweiterung auf Teil 2: Berechnung aller Zahlen in überlappenden Bereichen

Teil 2 der Aufgabe erfordert die Berechnung der Gesamtzahl aller Zahlen, die in den überlappenden Bereichen liegen. Da die Zahlenbereiche extrem groß sein können, ist eine explizite Auflistung aller Werte nicht praktikabel. Stattdessen wird eine Merging-Strategie angewendet, bei der überlappende Bereiche zusammengefasst und anschließend die Differenz zwischen Ober- und Untergrenze berechnet wird.

Der Algorithmus beginnt mit der Sortierung der Bereiche nach ihrem unteren Grenzwert – eine bereits aus Teil 1 bekannte Strategie. Anschließend wird eine Liste erstellt, die zunächst den ersten Bereich enthält. Für jeden weiteren Bereich wird geprüft, ob dieser mit dem letzten Bereich in der Liste überlappt. Falls ja, wird die obere Grenze des letzten Bereichs aktualisiert. Andernfalls wird der neue Bereich als separates Element hinzugefügt:

let mergedRanges = [];
mergedRanges.push(ranges[0]);

for (let i = 1; i < ranges.length; i++) {
  const current = ranges[i];
  const last = mergedRanges[mergedRanges.length - 1];

  if (current[0] <= last[1]) {
    last[1] = Math.max(last[1], current[1]);
  } else {
    mergedRanges.push(current);
  }
}

Nach der Zusammenführung der Bereiche wird die Gesamtzahl der enthaltenen Zahlen berechnet, indem für jeden Bereich die Differenz zwischen Ober- und Untergrenze zuzüglich eins summiert wird:

const totalNumbers = mergedRanges.reduce((sum, range) => {
  return sum + (range[1] - range[0] + 1);
}, 0);

Debugging und Optimierung: Warum die erste Lösung scheiterte

Nach erfolgreicher Validierung mit den Beispielwerten führte die Anwendung des Algorithmus auf die tatsächlichen Eingabedaten zu einem zu niedrigen Ergebnis. Die Analyse zeigte, dass ein logischer Fehler im Merging-Prozess vorlag: Die Bedingung für das Zusammenführen von Bereichen wurde nicht korrekt umgesetzt. Durch die Anpassung der Vergleichslogik und die Einführung einer zusätzlichen Prüfung der oberen Grenzen konnte der Fehler behoben werden.

if (current[0] <= last[1]) {
  last[1] = Math.max(last[1], current[1]);
} else {
  mergedRanges.push(current);
}

Diese Anpassung stellt sicher, dass alle möglichen Überlappungen korrekt erfasst werden, unabhängig von der Reihenfolge der Bereiche.

Fazit: Effizienz durch klare Algorithmen

Die Herausforderung von Advent of Code 2025 Tag 5 verdeutlicht, wie entscheidend fundierte Algorithmen für die Lösung komplexer Probleme sind. Durch den Einsatz von Sortierung, Reduktion und Merging-Strategien lassen sich brute-force Ansätze nicht nur optimieren, sondern auch skalierbar gestalten. Die gewonnenen Erkenntnisse sind nicht nur für Programmierwettbewerbe relevant, sondern bieten auch wertvolle Impulse für die Entwicklung effizienter Softwarelösungen im Berufsalltag. Die nächste Herausforderung wird zeigen, ob diese Prinzipien auch in anderen Kontexten Anwendung finden können.