SPOILER ALERT: Wer sich zum Plot oder zu den Puzzeln des Advent of Code 2022 und teilweise auch des Advent of Codes 2019 nicht spoilern möchte, sollte hier nicht weiterlesen.
Ich hatte ja Mitte des Monats schon einen Zwischenstand zum Advent of Code geposted. Mittlerweile bin ich durch, das letzte Puzzle habe ich am 25. Dezember gelöst. Wie schon vorher geschrieben sind alle meine Lösungen auf github zu finden. Die Lösungen für 2019 ebenso. Hier ein kleiner Rückblick:
Tag 18: Obsidian
Nachdem man in Tag 17 (wie schon im Zwischenstand erwähnt) einem Haufen in Tetris-Manier fallenden Steinen ausweichen musste, ging es in Tag 18 darum, die Oberfläche eines aus Voxeln bestehenden Magmastroms zu berechnen, welcher in Wasser floss und zu Obsidian erhärtete. Minecraft lässt grüßen.
Tag 19: Geoden
Überhaupt hatten viele der Puzzle Ähnlichkeiten mit Computer- oder Brettspielen. An Tag 19 musste man, um Geoden zu knacken, Roboter bauen. Ein Geodenknackroboter braucht Erz und Obsidian. Ein Obsidianabbauroboter braucht Erz und Ton. Ein Tonabbauroboter braucht Erz, und ein Erzabbauroboter braucht auch Erz.
Man hatte verschiedene Sets von Bauplänen, ein Zeitlimit (die geretteten Elefanten wurden langsam hungrig) einen Erzroboter zum Starten und die Aufgabe, herauszufinden, wie man bei Ablauf der Zeit die meisten Geoden geknackt hat. Teil zwei war dann das gleiche Problem, aber man hatte mehr Zeit und weniger Baupläne zum Durchprobieren (weil die Elefanten den Rest schon gefressen hatten).
Im Prinzip sehr ähnlich zu Tag 16, der ja bis dahin der schwierigste Tag gewesen ist. Auch in diesem Fall musste ich viel herumüberlegen, wie ich die Anzahl möglicher Zustände möglichst klein halten kann, weil mir ansonsten Speicherbedarf und Rechenzeit explodierten.
Glücklicherweise hatte ich Tag 16 noch in guter Erinnerung, so dass ich einiges, das ich gelernt habe, hier wieder anwenden konnte und deutlich schneller fertig war. Die erste brauchbare (also eine, die in meinen Arbeitsspeicher passte) brauchte wenige Minuten aber lieferte das richtige Ergebnis.
Dann fiel mir noch ein, dass ich die möglichen Zustände noch verringern konnte, indem ich nicht mehr Roboter baute, als ich entsprechende Rohstoffe in derselben Zeit verbrauchen konnte. Damit ging die Laufzeit dann runter auf vier Sekunden, also akzeptabel.
Zwischenspiel: 2019 Tag 18
Mit dem Wissen von Tag 16 und Tag 19 konnte ich dann auch Tag 18 von 2019 lösen. Dort hatte ich damals einen ähnlichen kürzeste-Pfade-Algorithmus versucht, war aber in Teil 2 an der schieren Menge von möglichen Zuständen gescheitert.
Ich habe also erst Teil 1 verbessert und dann Teil 2 implementiert. Nicht perfekt, aber es lief ein sieben Sekunden durch und ich hatte das Thema endlich abgehakt.
Tag 20: Grove Positioning System
An Tag 20 ging es dann endlich weiter mit dem eigentlichen Ziel. Allerdings war man ja von der Gruppe getrennt worden und musste erst die Koordinaten zum geheimen Hain mit den Sternfrüchten entschlüsseln.
Da es mit der Weihnachtselfischen Verschlüsselungstechnologie nicht so weit her war, war das auch recht einfach, so lange man aufpasste, mit ein paar Modulooperationen die Anzahl der Rechenschritte klein zu halten.
Tag 21: Mathematische Affen
An Tag 21 traf man dann wieder auf die Affenhorde, die man schon an Tag 11 getroffen hatte. Dieses SMal klauten sie zum Glück nicht die Ausrüstung. Laut der Übersetzung der Elefanten boten sie mir an, mir eine Abkürzung zum Sternfruchthain zu zeigen, wenn ich ein Rätsel löste.
Das war relativ simpel, trotz einiger Missverständnisse der Elefantenübersetzer.
Tag 22: Die Würfel des Wahnsinns
Tag 22 fing eigentlich ganz harmlos an: Die Affen haben mir die Abkürzung gezeigt und mir eine (etwas seltsam geformte) Karte gegeben. Auf dieser Karte muss ich einen bestimmten Weg entlangehen (ganz in Schatzsuchermanier: 15 Schritte geradeaus, Drehung nach links, 5 Schritte geradeaus, Drehung nach rechts, usw.) um an ein Passwort für den Hain zu kommen.
Das war einfach genug, doch Teil zwei hatte es in sich: bei näherer Betrachtung stellte sich die Karte als ein Würfelnetz heraus, das zu einem Würfel gefaltet werden musste und dann musste ich auf der Oberfläche dieses Würfels entlanggehen.
Ich habe zweieinhalb Tage an dieser Aufgabe gesessen und sie erst an Heiligabend gelöst. Es ist ja nicht nur so, dass ich herausfinden musste, welche der Quadrate des Würfelnetzes (für beliebige Würfelnetze) an welche Seite grenzte, ich musste ja auch die Orientierung der Koordinatensysteme der einzelnen Seiten zueinander herausfinden.
Ähnlich zu Tag 19 im letzten Jahr, wo ich mir ein 3D-Koordinatensystem aus Lego gebaut habe, habe ich mir für dieses Puzzle einige Würfelnetze aus Papier ausgeschnitten, Koordinatensysteme auf die einzelnen Seiten gemalt und diese als Hilfestellung verwendet, damit ich nicht alles im Kopf machen musste:
Nach vielen, vielen gehirnverdrehenden Stunden hatte ich irgendwann zumindest einen Ansatz: Ich nehme mir eine Art Normwürfel, bei der ich weiß, welche Seiten mit welchen verbunden und wie diese zueinander gedreht sind und versuche dann, meinen Inputwürfel um diesen Würfel herumzufalten.
Das hat am Ende funktioniert. Allerdings war mein Gehirn am Ende ziemlich matschig. Es ist unglaublich leicht, etwas aus Versehen gegen den Uhrzeigersinn zu drehen, wenn es eigentlich im Uhrzeigersinn gedreht werden müsste. Ich hatte am Ende einen ganzen haufen Tests, die nur geprüft haben, ob das Falten für die Beispieleingabe passt und sogar, ob ich den Normwürfel richtig zusammengestellt habe.
Danach musste ich „nur noch“ (es war Heiligabend und die Zeit war knapp) dumme Tippfehler in dem eigentlichen Laufalgorithmus beheben, und ich hatte endlich das richtige Ergebnis!
Tag 23: Bäume pflanzen
Tag 23 habe ich vor Tag 22 gelöst, aus den oben beschriebenen Gründen. Endlich beim Sternfruchthain angekommen musste man den Elfen helfen, die Pflanzen für das nächste Jahr zu setzen.
Das war ein zellulärer Automat und ziemlich einfach. Ich hatte zwar befürchtet, Teil 2 könnte wieder kompliziert werden, das war aber nicht der Fall.
Tag 24: Durch den Schneesturm
Tag 24 war wieder recht leicht, man musste einen sicheren Weg durch ein sich ständig (aber periodisch) veränderndes Muster von Blizzards bahnen.
In Teil 2 musste man noch einmal zurück und wieder hin, um die Snacks zu holen, die irgendein schusseliger Elf hat liegenlassen. Das war auch relativ leicht, da mir eingefallen ist, dass ich ja einfach die Karte um 180° drehen konnte und den Algorithmus aus Teil 1 unverändert auch für den Rückweg verwenden konnte.
Dieses Mal gab es auch keine riesigen Zustandsräume, also alles ganz harmlos. Umso mehr Zeit habe ich dann auf das Puzzle von Tag 22 verwendet.
Tag 25: Heißluftballons
Tag 25 war wieder recht einfach. Wie traditionell jedes Jahr gab es auch dieses Jahr am 25. nur ein Puzzle. Man musste Zahlen in einem seltsamen Format (das, wie ich später herausgefunden habe, an das balancierte Ternärsystem angelehnt war, nur halt mit Basis 5, also eigentlich ein balanciertes Quinärsystem) parsen (einfach), zusammenrechnen (trivial) und wieder im ursprünglichen Format ausgeben (ebenfalls recht einfach).
Damit war ich durch. Weihnachten war gerettet.
Nachspiel: 2019, Tag 22
Irgendwann zwischendurch hatte ich ja schon Tag 18 aus dem AoC 2019 nachgeholt. Als ich zwischendurch ein bisschen Zeit hatte, habe ich auch angefangen, Tag 22 aus 2019 nachzuholen. Hier ging es darum, eine große Anzahl Karten zu mischen (nach einem vorgegebenen, deterministischen Verfahren).
Teil 1 hatte ich damals schon gelöst. Die Anzahl der Karten war hier noch relativ klein, eine deutlich größere Zahl hätte aber auch keine Probleme bereitet. Es wurde nämlich nur verlangt, die Endposition der Karte herauszufinden, die am Anfang auf Position 2019 war. Schon damals hatte ich erkannt, dass das Mischverfahren so angelegt ist, dass ich die Position der einzelnen Karte unabhängig von den anderen berechnen konnte.
Teil 2 hingegen war deutlich kniffliger. Nicht nur hatte man deutlich mehr Karten (über hundert Billionen), sondern musste den Stapel auch über hundert Billionen Mal mischen. Millionen Mal? Kein Problem. Milliarden wäre auch noch mit Brute force gegangen, aber Billionen war unmöglich.
Ich habe eine ganze Weile gebraucht. Erst ist mir aufgefallen, dass ich alle Teilschritte des Mischverfahrens in eine Modulo-Multiplikation und eine Modulo-Addition vereinigen konnte.
Damit alleine war mir aber noch nicht geholfen. Das hätte zwar ein paar Milliarden Mischoperationen möglich gemacht, aber keine hundert Billionen.
Allerdings war diese vereinfachte Operation deutlich leichter mit modularer Arithmetik zu behandeln. Heraus kam ein bisschen modulares potenzieren und zwei modulare Divisionen. Ich musste mir echt einiges wieder anlesen, aber am Ende hatte ich das Ergebnis in konstanter Zeit ausgerechnet.
Naja, ich musste von i64 auch i128 umsteigen, weil die Multiplikationen trotz Modulo nicht mit i64 machbar waren, aber darüber werde ich mich nicht beschweren.
Fazit
Wieder ein gelungener Advent of Code. Ich kann anscheinend immer noch einiges, auch wenn ich ein paar Mal bewusst den leichteren (und langsameren) Weg genommen habe.
Einige meiner Lösungen waren deutlich langsamer als angegeben (15 Sekunden auf zehn Jahre alter Hardware), aber damit gebe ich mich erst einmal zufrieden.
Ich habe ein paar Sachen gelernt, ein paar Sachen wiederholt, die ich vergessen habe und einige der Puzzle waren für mich wirklich fordernd. Außerdem habe ich ein paar Puzzle von vor ein paar Jahren nachgeholt.
Ich habe mir noch nicht fest vorgenommen, nächstes Jahr auch teilzunehmen, aber ich werde es vermutlich tun. Auch wenn es schon eine ganze Menge Zeit frisst.