SPOILER ALERT: Wer sich zur Story oder zu den Lösungen des Advent of Code 2021 nicht spoilern möchte, sollte nicht weiterlesen.
Der Advent of Code 2021 ist vorbei, und zum zweiten Mal habe ich es geschafft, alle Puzzle zu lösen. Am Ende wurden die Puzzle wieder interessanter, also hier einige meiner Highlights der letzten Tage:
Tag 15 oder: Ich habe noch nie Dijkstra produktiv implementiert.
Tag 15 war eine relativ direkte kürzeste-Pfade-Suche mit positiven Kantenlängen. Teil zwei war einfach nur eine größere Variante von Teil 1, was bedeutete, dass man wirklich auf seinen Algorithmus und seine Datenstrukturen aufpassen sollte, weil das Ding sonst ewig rechnet.
Ich habe den Dijkstra-Algorithmus verwendet, den ich tatsächlich noch mehr oder weniger auswendig herunterschreiben konnte (die „weniger auswendig“-Teile konnte ich mir rekonstruieren aus dem was ich noch wusste.
Dieser Algorithmus ist einer, den ich an der Uni in mindestens drei verschiedenen Vorlesungen gelernt habe, aber bisher noch nie in Produktivcode anwenden musst. Also mal ganz nett, ihn wenigstens für ein Puzzle verwenden zu können.
Tag 16: Krumme Bit-Werte
Tag 16 bestand darin, irgendein Kommunikationsprotokoll, dass die Weihnachtselfen entwickelt haben, zu implementieren. Es war ein bisschen nervig zu implementieren, weil viele Blöcke vorkamen, die nicht nicht an 8-bit aligned waren. Wenn man das Parsen erst einmal hatte, war es aber ganz einfach. Dementsprechend bestand Aufgabe 1 praktisch nur aus dem Parsen und Aufgabe 1 darin, etwas mit den geparseten Daten zu machen.
Tag 17: Kurvendiskussionen
In Tag 17 musste man Bahnen berechnen, in denen man eine Sonde abschießt, damit sie in einem Tiefseegraben landet.
Die Gemeinheit: Die Sonde bewegt sich in diskreten Schritten, schießt also gerne auch mal über das Ziel hinaus.
Dieses war das einzige Puzzle, dass ich nicht am Tag der Veröffentlichung durchgekriegt habe, was aber auch daran lag, dass ich den ganzen Tag zu tun hatte (inkl. einer Rollenspielrunde am Abend).
An sich ist die Simulation recht einfach, aber ich brauchte eine Weile um eine geeignete Obergrenze für die Startgeschwindigkeit festzulegen (Tipp: Die Flugkurve ist symmetrisch). In Teil zwei hatte ich dann einen dummen Bug, den ich um 1 Uhr nachts nicht mehr beheben konnte, deswegen war ich erst am nächsten Morgen fertig.
Tag 18: Mathehausaufgaben
An Tag 18 musste man die Hausaufgaben von ein paar Scheibenbäuchen erledigen.
Die haben ein, gelinde gesagt, außergewöhnliches Zahlensystem. Ich hätte zur Umsetzung eine andere Datenstruktur wählen sollen. Ich kriege ja immer kribbeln wenn ich sehe, wie Leute in ihren Lösungen direkt auf Strings arbeiten, aber in diesem Fall wäre das vermutlich eine einfachere Lösung gewesen.
Trotzdem, ich habe es hingekriegt, rekursive, verändernde Aufrufe auf derselben Datenstruktur in rust zu implementieren (mit einer Menge &mut, ohne, dass mir der Compiler das komplett um die Ohren gehauen hat.
Tag 19: Rotation und Translation
An Tag 19 musste man Sonden, die ihre eigene Position und Ausrichtung nicht kannten, mit Hilfe von Baken in dasselbe Koordinatensystem bringen. Es gab eine Menge Rotationen und Koordinatensystemverschiebungen, ich musste mir ein Koordinatensystem aus Lego bauen, weil meine rechte Hand irgendwann nicht mehr flexibel genug war um mir das Koordinatensystem zu veranschaulichen.
Ein doofer Fehler, den ich gemacht habe: Ich habe irgendwie aus der Beschreibung herausgelesen, dass das Koordinatensystem auch gespiegelt werden kann. Kann es nicht. Nur Rotationen (um jede Achse, aber nur in 90°-Schritten).
Das ganze Herumgehampel hat mich irgendwie an meine Masterarbeit erinnert, wo ich auch verschiedene Koordinatensysteme (eines Roboterarms) ineinander umrechnen musste.
Tag 20: Die Tiefsee: Unendliche Weiten
In Tag 20 musste man eine Bildaufnahme verbessern. Im Prinzip war das hier wieder ein zellulärer Automat. Mit einem Trick: Das Bild ist unendlich groß, und auch der Bereich, der nicht vom initialen Zustand beeinflusst wurde, verändert sich. Das muss man berücksichtigen.
Lustigerweise hatte ich daran schon gedacht, aber während ich noch einen anderen Bug in meinem Code behoben habe, hatte ich das wieder vergessen. Irgendwann ist es mir wieder eingefallen, und dann hatte ich auch die korrekte Lösung.
Tag 21: Würfelspiele
Teil 1 von Tag 21 war ziemlich straighforward. Teil 2 war interessanter. Im Prinzip musste man die Anzahl von Wegen berechnen, in denen jeweils einer von zwei Spielern gewinnt, wenn man mit dreiseitigen Würfeln würfelt. Die Zahlen werden recht schnell ziemlich hoch, der Trick hier ist: Der nächste Schritt im Spiel hängt nur vom aktuellen Zustand ab, nicht von allen vorherigen Zuständen. So kann man alle Wege, die zu einem speziellen Zustand führen, zusammenfassen und spart dem Computer eine Menge Arbeit und Speicherauslastung.
Doof nur, wenn man aus Versehen zwei Mal für Spieler 2 spielt, anstatt für jeden Spieler einmal (doofer Tippfehler). Trotzdem habe ich das Puzzle während einer Zugfahrt fertig gekriegt.
Tag 22: Quaderspiele
Bei Tag 22 musste man zählen, wie viele Zellen in einer 3D-Matrix „an“ sind, wenn man verschiedene Quader von Zellen (die sich überschneiden können) nacheinander an- oder ausschaltet.
Ich habe direkt die Lösung gebaut, bei der man die Überschneidungen zwischen den Quadern berücksichtigt, so dass man nicht jede Zelle einzeln zählen muss und mich dabei wie schon an Tag 20 in meiner nur mäßig ausgeprägten räumlichen Vorstellungskraft für eine Weile verheddert.
Dann habe ich festgestellt, dass der Suchraum für Teil 1 so klein ist, dass ich da auch jede Zelle einzeln betrachten könnte. Weil meine Lösung da aber schon fast fertig war, habe ich die fertig gemacht.
Teil zwei hatte dann wie zu erwarten einen Suchraum mit mehreren hunder Milliarden Zellen, was für mich kein Problem war, weil meine Lösung mit Quader-Überschneidungen hier tatsächlich auch gut funktionierte.
Tag 23: Amphipoden-Wohnungen
Tag 23 war wieder ein kürzeste-Pfade-Problem, für das ich wieder den Algorithmus von Dijkstra verwenden konnte. Dieses Mal war es nicht sofort offensichtlich, dass man das als kürzester-Pfad-Problem modellieren kann, aber es hat sehr gut funktioniert.
Teil zwei wäre eigentlich kein Problem gewesen, aber ich hatte dummerweise meine Datenstrukturen für die Knoten und Kanten des Graphen so gewählt, dass ich alles hätte noch einmal schreiben müssen.
Stattdessen habe ich dann erst einmal den Code von Teil 1 in mühevoller Kleinarbeit refaktorisiert (dabei bin ich ein bisschen mit rust generics amok gelaufen) und konnte dann Teil 2 recht schnell lösen.
Tag 24: Bitte Seriennummer eingeben
In Tag 24 musste man eine ALU implementieren. Oder auch nicht. Eigentlich musste man nur den größten akzeptierten Eingangswert einer Berechnung herausfinden.
Es war Heiligabend, und ich habe es nicht auf die Reihe gekriegt. Codeanalyse (des input-Programms) hat mich nur mäßig weit gebracht. Am Ende habe ich dann, mit ein paar Vereinfachungen aus der Codeanalyse, einen brute-force-Ansatz gewählt. Der hat knapp eine Minute gearbeitet (mit optimiertem rust-code), eine Menge Speicher verbraten aber am Ende das korrekte Ergebnis herausgegeben.
Teil zwei war wie Teil 1, nur mit der niedrigsten akzeptierten Eingabe. Selber Ansatz, selbe Laufzeit.