SPOILER ALERT: Dieser Artikel enthält Informationen über die Story und über Puzzle des Advent of Code 2022. Wer die Geschichte noch selber lesen oder die Puzzles noch selber lösen will, sollte nicht weiterlesen.
Wie schon erwähnt, mache ich dieses Jahr wieder beim Advent of Code mit. Gestern, Tag 16, war der erste Tag, der mich wirklich gefordert hat. Mit anderen Worten: Es wird langsam interessant.
Doch fangen wir mal weiter vorne an…
Notrufsignale
Nach einem Unfall mit einer kaputten Hängebrücke (bei der man vom Rest der Gruppe getrennt wurde), einigen nervigen Affen, einer Kletterpartie, um besseren Empfang zu bekommen (Tag 12, hier habe ich bei Teil zwei wider besseren Wissens eine sehr unperformante Lösung gewählt, weil sie deutlich schneller zu implementieren war und trotzdem in einer Sekunde durchlief) habe ich an Tag 13 ein Notrufsignal empfangen.
Das Signal kam aus einer Höhle (hinter einem Wasserfall, versteht sich), und nach einigen Problemen mit fallendem und rutschendem Sand (Tag 14) konnte man den Ursprung des Notrufsignals ausfindig machen (Tag 15).
Wie schon häufig waren hier die Eingaben so gewählt, dass eine simple Brute-Force-Methode nicht funktioniert hätte. Man hätte ein quadratisches Areal mit vier Millionen Einheiten Kantenlänge durchsuchen müssen.
Glücklicherweise hatte ich in Teil 1 eine recht effiziente Lösung für das Durchsuchen einer Zeile geschrieben. In Teil zwei habe ich es mir dann erspart, eine effiziente Lösung zu finden und habe einfach vier Millionen mal den Algorithmus von Teil 1 aufgerufen, was passabel schnell war (kleiner als eine Sekunde mit Compileroptimierung in rust).
Viele Ventile
An Tag 16, also gestern, ging es dann aber ans Eingemachte. Das Notrufsignal stammte von einer Herde Elefanten in der Höhle, die es irgendwie geschafft hatten, ein Funkgerät zu bedienen. Just in diesem Moment entschied sich der Vulkan, der unter der Höhle liegt, auszubrechen.
Der Vulkan schien das auch in der Vergangenheit schon getan zu haben, jedenfalls hatte jemand ein System aus Leitungen und Ventilen angelegt, um Druck abzulassen.
Dummerweise hatte man nur sehr begrenzt Zeit, um die Ventile zu öffnen. Zu allem Überfluss waren auch noch die meisten Ventile kaputt und über ein großes Höhlensystem verteilt.
Die Aufgabe war also, die Ventile so aufzumachen, dass sie den größtmöglichen Druckablass ermöglichten. Man hatte allerdings nur 30 Minuten Zeit, zwischen Ventilen hin- und herzulaufen kostet Zeit, und Ventile zu öffnen kostet auch Zeit. Zudem war der Druckablass abhängig davon, wann ein Ventil geöffnet wurde. Je früher geöffnet, desto höher der gesamte Druckablass.
Ich habe mir eine Weile den Kopf darüber zerbrochen, wie ich das lösen kann. Am Ende habe ich eine Graphenexploration über die möglichen Zustände gemacht. Teil eines jeden Zustands waren aktuelle Position, verbliebene Zeit, geöffnete Ventile und erreichte Punkte.
Die Lösung funktioniert für die Beispieldaten, war aber viel zu langsam für die echten Daten.
Optimierungen
Nun ist in so einem Fall recht schnell klar, was der Grund ist: Es gibt einfach zu viele erreichbare Zustände, der Suchraum explodiert. Wie reduziere ich also die möglichen Zustände?
Nach einigem Überlegen habe ich die Punkte aus dem Zustand herausgenommen. Schließlich ist es egal, wie viele Punkte ich an einem Zustand habe, um herauszufinden, wie ich von diesem Zustand aus noch mehr Punkte bekommen kann.
Dafür musste ich die Punkte natürlich trotzdem behandeln, also habe ich die Graphenexploration so modifiziert, dass Zustände mit den meisten Punkten bevorzugt behandelt wurden, und wenn ich in einem Zustand war, den ich schon früher mal mit mehr Punkten besucht habe, habe ich ihn für die Exploration einfach ignoriert.
Das hat den Suchraum dann ausreichen eingeschränkt, dass ich in passabler Zeit ein Ergebnis bekommen habe.
Elefanten helfen
Nur, dass das natürlich nicht ausreichte. Also musste ich in Teil 2 des Puzzles auch noch einen Elefanten anlernen, die Ventile zu öffnen.
Das kostete vier Minuten, also war zumindest der Suchraum ein bisschen kleiner. Auf der anderen Seite wurde der Suchraum enorm größer, weil der Elefant nun auch eine Position hatte. Die Suche nach der optimalen Lösung lief also wieder zu langsam um benutzbar zu sein.
Gleiches Spiel wie vorher: Wie können wir die Anzahl der Zustände verringern? Nach ein paar fehlgeschlagenen Versuchen die Zeit oder die geöffneten Ventile ähnlich der Punkte auszulagern, ist mir am Input etwas aufgefallen.
Die vorher erwähnten kaputten Ventile: die meisten von ihnen hatten nur direkte Verbindungen zu zwei anderen Ventilen. Ich könnte also diese Ventile wegoptimieren und durch direkte Wege zu den nicht-kaputten Ventilen ersetzen.
Dummerweise musste ich dafür Wegkosten einführen. Das heißt es reichte nicht mehr, nur meine eigene Zeit zu tracken und den Elefanten gleichzeitig mit mir agieren zu lassen (was vorher möglich war, weil jede Aktion gleich viel Zeit kostete). Der Elefant brauchte einen eigenen timer, und ich musste auch noch aufpassen, dass bei meiner Berechnung der Aktionen trotzdem alles in der richtigen Reihenfolge passierte.
Trotzdem war das Programm noch nicht schnell genug.
Ein paar zunehmend verzweifeltere Stunden und viele unbrauchbare Ansätze später kam mir endlich der Geistesblitz: Ein Problem ist, dass ein Großteil des Zustandsraumes darin besteht, dass sowohl ich als auch der Elefant nur hin- und hergehen ohne etwas zu tun. Das ist kein sinnvolles Verhalten, ist aber Teil des Zustandsraumes und wird deswegen auch untersucht.
Also habe ich das zu-einem-Ventil-gehen und das Öffnen eines Ventils zu einer Aktion zusammengefasst. Und wie schon im letzten Jahr, wo ich den Algorithmus von Dijkstra implementieren konnte, habe ich hier den Floyd-Warshall-Algorithms zum ersten Mal außerhalb einer Vorlesung verwendet. Im Gegensatz zum Dijsktra-Algorithmus musste ich aber die Details hier nachschauen. Ich habe mir den Floyd-Algorithmus nie merken können.
Damit war die Lösung schon viel schneller, zumindest für die Beispieldaten und für den ersten Puzzleteil. Teil 2 lief aber immer noch lange und verschlang viel Speicher.
Mein Gehirn war von der stundenlangen Konzentration schon ganz vernebelt. Irgendwann ist mir dann aufgefallen, dass es ja eine Symmetrie zwischen mir und dem Elefanten gibt, was einige Zustände identisch macht und damit den Zustandsraum wieder einschränkt.
Trotzdem war es noch zu langsam… dachte ich. Tatsächlich lief es aber in etwas über einer Minute durch. Da es mittlerweile nach 23:00 Uhr war, war ich damit zufrieden und schlief ein.
Tödliches Tetris
Die Ventil-Aktion hatte mir und den Elefanten ein bisschen Zeit erkauft. Es wurde jedoch wärmer, und Steine fingen an, von der Höhlendecke zu fallen und sich in Tetris-Manier aufzuschichten. Um herauszufinden, wo es sicher war, musste man eine Simulation erstellen.
Teil 1 war also recht einfach, wenn ich nicht diesen Tippfehler gehabt hätte, der zu einer falschen Lösung geführt hat. Sobald der behoben war, war meine Steinfallsimulation recht elegant gelöst und funktionierte super.
Dann (Teil 2) wollten diese undankbaren Dickhäuter aber lieber auf Nummer sicher gehen und eine Billion Steine simuliert sehen. Mit anderen Worten: ein typischer Fall von: das passt nicht in den Speicher, wir müssen tricksen.
Mein üblicher Ansatz hier ist, irgendwelche Regelmäßigkeiten zu finden, mit denen man den Wert nach einer Billion Iterationen dann einfach ausrechnen kann.
Da mein Gehirn vom Vortag aber immer noch matschig war, konnte ich partout keine Zyklen erkennen. Nach Stunden der Suche habe ich dann mit einem sehr holprigen Zyklusdetektor eine Lösung gefunden.
Jetzt gehe ich schlafen.