Der Programmierpuzzleadventskalender Advent of Code ist für dieses Jahr durch. Dieses Jahr war das zehnte Mal, dass dieser Adventskalender seine Türchen öffnete, und anlässlich dieses Jubiläums ging es in einer rasanten Tour durch Raum und Zeit, um die Orte zu besuchen, die man in den vorherigen Advents of Code schon einmal besucht hat.
SPOILER ALERT: Das hier ist ein Rückblick auf den Advent of Code 2024 und vielleicht auch auf vorherige Advents of Code. Wer sich die Geschichte und die Puzzle nicht spoilern möchte, sollte hier aufhören zu lesen.
Erst einmal ein paar allgemeine Anmerkungen. Wie schon am Anfang des Monats geschrieben musste man dieses Mal Santas Chefhistoriker suchen, der unbedingt bei Santas Schlittenstart zusehen möchte, aber leider gerade nirgendwo zu finden ist. Die Vermutung ist: Er wird sich irgendwo an historisch relevanten Orten herumtreiben (d.h. Orte aus vorherigen Jahren). Deswegen nehmen dich die anderen Historiker mit, um ihn zu suchen.
Was die Puzzle angeht: Ich habe mich an den ersten Tagen erstaunlich schwer mit den Puzzlen getan (sie waren nicht schwer, aber dafür habe ich doch ein paar Probleme gehabt). Auf der anderen Seite habe ich es seit 2020 zum ersten Mal geschafft, alle Puzzle am Tag ihrer Veröffentlichung zu lösen.
Die Community (hauptsächlich auf reddit) war wieder sehr aktiv. Egal, wie sehr ich weiter unten über komische Kommentare auf reddit lästere: Die Community ist hilfsbereit und kreativ, sowohl in den Lösungen als auch in Visualisierungen und Memes. Aufgefallen ist mir, dass es gefühlt weniger Posts mit „Meine Lösung funktioniert für das Beispiel aber nicht für den wirklichen Input“ gab. Es gab sie, aber es waren weniger als letztes Jahr. Auch wieder dabei: eine inoffizielle Erhebung zu den Teilnehmern des AoC.
Während die Historiker den Chefhistoriker suchen hilft man nur in seltenen Fällen dabei, sondern löst meist irgendwelche anderen Probleme, die die Leute vor Ort haben. Am Ende stellt sich heraus: Der Chefhistoriker war die ganze Zeit in seinem Büro und hat gerarbeitet und war ganz am Anfang nur kurz weg, um sich Kaffee zu holen.
Die Puzzle
Meine Lösungen zu den Puzzles
Tag 2: Auf oder Ab
Am zweiten Tag musste man in Teil 1 kurze Zahlenfolge auf bestimmte Eigenschaften überprüfen. In Teil 2 musste man herausfinden, welche ungültigen Zahlenfolgen gültig werden, wenn man genau ein Element entfernt.
Auf reddit eine Menge Leute, die das einfach brute-forced haben. Ich selber habe einen Ansatz gewählt, bei dem ich nur vier Optionen ausprobieren musste. Auf reddit gab es auch ein paar, die es mit drei oder sogar nur zwei Optionen geschafft haben.
Tag 3: Corrupted Memory
An Tag 3 musste man arithmetische Operationen wie mul(9,6) in einem kauderwelsch von korrumpierten Speicher finden. Da ich in rust ohne externe Abhängigkeiten arbeite, konnte ich das nicht mit regulären Audrücken machen, auch wenn es hilfreich gewesen wäre. Schwierig war es aber trotzdem nicht. Auf reddit natürlich Programmieranfänger, die sich in Regexes einlesen.
Tag 5: Absolute Ordnung
Am fünften Tag musste man den Elfen helfen, das Schlittensicherheitshandbuch auszudrucken. Weil die Elfen immer alles etwas komisch machen, sind die Seiten seltsam sortiert. Ich habe erst einmal einen primitiven Ansatz gewählt (Sortierfunktion der Standardbibliothek, mit selbstgeschriebener Vergleichsfunktion, die die komischen Regeln beinhaltet). Hat auf Anhieb funktioniert. Ich hatte auch eine sauberere Lösung im Kopf, aber wie sich herausstellte wäre das keine gute Idee gwesen: Die Seitenreihenfolge ist nämlich nicht absolut. Sie funktioniert nur, weil jede zu sortierende Liste keine widersprüchlichen Kombinationen enthält.
Auf reddit gibt es ein paar Leute, die keine Lust hatten und einfach Bogosort verwendet haben.
Tag 6: Vagabundierende Wachen
Eine kleine Zeitreise. Um ein Paradox zu vermeiden, muss man einer Wache, die sich nach bestimmten Regeln verhält und and Hindernissen immer nach rechts abbiegt, ein zusätzliches Hindernis in den Weg legen, damit sie im Kreis läuft. Meine Brute-Force-Ansatz, einfach alle möglichen Positionen für ein Hindernis (also alle Positionen auf dem normalen Pfad der Wache) auszuprobieren lief in 1.5s durch, also habe ich mir keine Mühe gemacht, das weiter zu optimieren.
Tag 7: Gestohlene Operatoren
Dieses Mal musste man Gleichungen lösen, indem man die richtigen Operatoren einfügt. Die wurden nämlich von Elefanten gestohlen (makes just as much sense in context). Ich habe es wieder brute-forced, und es lief sogar schneller durch als meine brute-force-Lösung vom Vortag. Einzig ein dummer Tippfehler in Teil 2 hat mich Zeit gekostet.
Tag 9: Defragmentieren
Am neunten Tag musste man Flohkrebsen dabei helfen, ihre Festplatte zu defragmentieren. Meine Lösung ist eher unsauber (mir ging es nicht gut an dem Tag), funktioniert aber ohne Probleme. Auf reddit hingegen sind viele Leute darüber gestolpert, dass es Datei IDs größer als 9 gibt, wobei ich nicht einmal verstanden habe, warum das ein Problem ist. Stellt sich heraus: die haben auf Strings gearbeitet da kann jede Speicherzelle und einen code point als ID haben. ASCII-Codepoints reichen aber nicht aus für die Anzahl der Dateien. Anstatt eine ordentliche Lösung zu machen, sind einige Leute auf Unicode-IDs umgestiegen. Ich konnte nicht umhin anzumerken, wie viele Probleme dieser Ansatz bringt. Das war ungefähr auf dem Niveau der „twoneight“-Probleme aus dem letzten Jahr.
Tag 10: Lesen hilft, falsch lesen hilft mehr
Ein Pfadesucheproblem, bei dem man im ersten Teil alle Ziele, die man von einem Startpunkt erreichen kann, ausfindig machen muss. Ich habe es zuerst falsch gelesen und alle Pfade gezählt. Der Bug war leicht behoben. In Teil 2 musste man dann aber alle Pfade Zählen. Der Bug war ebensoleicht unbehoben wie ich ihn vorher behoben habe und ich war in fünf Minuten mit Teil 2 fertig.
Tag 11: You blink, you miss it
An Tag 11 musste man Steine zählen, die sich mit jedem Blinzeln nach bestimmten Regeln verfielfältigen. Exponentiell. Teil 2 war dann wie Teil 1, aber man blinzelte häufiger. Ein klassisches „und jetzt mach das gleiche noch einmal mit dieser riesigen Zahl“-Problem. Mit dynamic programming aber kein Problem.
Tag 12: Zäune ziehen
Dieses Mal musste man den Umfang von Gärten berechnen, damit Zäune gezogen werden können. In Teil zwei dann nicht den Umfang, sondern die Anzahl der Seiten. Meine Lösung ist hässlich und sie zu schreiben war frickelig. Wenn ich, wie einige Leute auf reddit, auf die Idee gekommen wäre dass die Anzahl der Ecken gleich die Anzahl der Kanten ist, wäre es vermutlich schöner geworden.
Tag 13: Lineare Gleichungen
Wieder eins von den Puzzeln, bei denen beim zweiten Teil eine unmöglich große Zahl gefordert wird. Ich habe einfach auf dem Papier eine generelle Lösung für das geforderte Gleichungssystem aufgestellt und die dann in das Programm übertragen. Hat auf Anhieb funktioniert, was mich selber erstaunt hat. Ich war mir sicher, ich hätte mich irgendwo verrechnet.
Tag 14: Weihnachts-Easteregg
Die Historiker müssen auf Toilette und der beste Ort dafür ist aus irgendeinem Grund das Osterhasenhauptquartier. Dort darf man sich als Weihnachtself natürlich nicht erwischen lassen, also musste man die Positionen der Wachroboter voraussagen.
In Teil 2 hat man dann vermutet, dass die Roboter vom Nordpol gestohlen oder kopiert wurden. Dazu musste man ein Easteregg finden (ironischerweise), bei dem sich die Roboter irgendwann in Form eines Tannenbaums gruppieren. Leider kriegt man keine Beschreibung, wie der Tannenbaum aussieht. Ich dachte zunächst, der Tannenbaum würde so aussehen wie der von 2015 und habe überschlagen, dass ich 30 Roboter in einer Reihe erwarten kann, wenn der Tannenbaum zu sehen ist.
Nun, diese Annahme war falsch, weil der Tannenbaum komplett anders aussah. Allerdings hatte er einen Rahmen, der diese Bedingung erfüllte, also war ich gerettet. Auf reddit haben sich viele über die ungenaue Spezifikation beschwert, auf der anderen Seite gab es aber auch eine Menge kreativer Methoden, den Tannenbaum zu finden. Von statistischen Analysen der Varianz der Roboterpositionen über groß angelegte Plots bis hin zu so einfachen Heuristiken wie meiner.
Tag 16: Rentierrennen
Den kürzesten Pfad für ein Rentier in einem Irrgarten finden. Das Besondere: Abbiegen ist viel, viel teurer als geradeaus laufen. Erster Einsatz von Dijkstra dieses Jahr.
Tag 17: Codeanalyse
Wieder eins von diesen Problemen wo man einen eigens erdachten Maschinencode ausführen muss. In Teil zwei musste man dann einen Input finden, der das Programm zu einem Quine macht. Dieser Input war natürlich wieder riesig, zu groß, um ihn per Brute Force herauszufinden. Also musste man das Programm analysieren (ich habe dafür einen Disassembler geschrieben um das Programm einfacher verstehen zu können). Dann konnte man Schritt für Schritt einen Input konstruieren, der die Lösung findet.
Mein Ansatz lag zuerst daneben, aber nicht weit daneben. Deswegen konnte ich den Rest doch mit Brute Force machen. Als ich das geschafft habe, habe ich in Ruhe noch die Bugs in meinem ersten Ansatz behoben, dann ging es.
Tag 18: Ein einfacher Einschub
Im Verhältnis zu den vorherigen Tagen war Tag 18 sehr einfach. Erst einen kürzesten Pfad mit Einheitskosten finden (BFS), dann herausfinden, ab welchem hinzugefügten Hindernis kein Pfad mehr zum Ziel führt. Mit binärer Suche einfach und effizient.
Tag 19: Handtücher in Heißen Bädern
Man muss herausfinden, wie bestimmte Streifenmuster mit vorgegebenen gestreiften Handtüchern zu bilden sind. Teil 2 war wieder effizient mit dynamic programming lösbar.
Tag 20: Schummelrennen
Eigentlich ein schönes Puzzle: Man musste einen kürzesten Pfad finden, wenn man ein mal für eine bestimmte Zeit Hindernisse ignorieren kann. Ein einfaches kürzeste-Pfade-Problem, aber leider ist für Teil 2 (man darf deutlich länger schummeln als bei Teil 1) der Suchraum wieder explodiert. Ich habe einen unbrauchbaren Ansatz gewählt und komplett implementiert. Dann habe ich noch einen unbrauchbaren Ansatz gewählt und komplett implementiert. Dann habe ich einen guten Ansatz gefunden, hatte aber einen Bug. Und noch einen Bug, und noch einen Bug. Der erste Tag, an dem ich richtig gelitten habe.
Tag 21: Robots all the way down
Einer der Historiker hat sich auf Santas Reindeer-Class-Raumschiff verirrt. Man muss ihn retten, indem man Mit Pfeiltasten einen Roboter steuert, mit Pfeiltasten einen Roboter zu steuern, der mit Pfeiltasten einen anderen Roboter steuert, der Code in ein Nummernpad eingibt.
Man soll die Länge der kürzesten Folge von Befehlen finden, die den letzten Roboter den richtigen Code eingeben lässt. Klingt einfach, oder? Ist es aber nicht. Es gibt viele subtile Probleme, hauptsächlich ist es wichtig, in welcher Reihenfolgen man die Befehle für eine Taste eingibt. Ich habe für Teil 1 ewig gebraucht.
Teil zwei war das gleiche, nur mit 25 Robotern an den Pfeiltasten anstatt nur zwei. Die Liste von Befehlen würde so lang, dass sie nicht mehr in den Speicher passt. Im Verhältnis zu Teil 1 habe ich das aber recht schnell mit – mal wieder – dynamic Programming gelöst, weil mir aufgefallen ist, dass man bestimmte Befehle unabhängig voneinander betrachten kann. Vermutlich das schwerste Puzzle dieses Jahr.
Tag 22: Bananen und Affen
Ein Affe hat den Raum-Zeit-Teleporter der Historiker geklaut. Um ihn zurückzukriegen muss man ihm Bananen geben, die man sich von anderen Affen erhandelt. Einfaches durch-die-Gegend-schieben von Zahlen, eine Erleichterung nach dem vorherigen Tag.
Tag 23: Die LAN-Party
Man muss direkt vernetzte Computer in einem Netzwerk finden. Ein Cliquenproblem, wie ich gelernt habe, das NP-Vollständig ist. Ich habe mal geschaut, wie man so etwas löst und bin auf den Bron-Kerbosch-Agorithmus gestoßen. Für den gegebenen Input hat das auch ziemlich schnell funktioniert.
Tag 24: Plus
An Heiligabend musste man zunächst Inputs durch einen logischen Schaltkreis (ohne Schleifen) schicken. Einfach. In Teil 2 stellte dich dann heraus, dass der Schaltkreis eigentlich addieren soll. Nach einigem Überlegen bin habe ich mir den Schaltkreis einfach geplotted (mit Graphviz und die Fehler manuell gesucht, das ging schneller. Ich habe bis jetzt keine Allgemeine Lösung, aber warum auch? Es war Heiligabend, ich hatte nicht viel Zeit für den AoC. Mit meiner manuellen Lösung hatte ich ironischerweise meinen bis dahin besten Rang erreicht.
Tag 25: Schlüssel-Schloss
Heute musste man dann schauen, welche Schlüssel auf welche Schlösser passten. Sie mussten nicht einmal genau passen. Ich konnte jeden Schlüssel und jedes Schloss als 64-bit Integer darstellen und konnte so das Problem effizient mit bitweisem AND lösen.
Jetzt bin ich durch und habe meinen persönlich besten Rang für die Lösung aller Puzzle in einem Jahr erreicht.
