Gestern öffnete sich das letzte Türchen des diesjährigen Advent of Code. Wie üblich für Tag 25 war das Puzzle angemessen, aber nicht übermäßig schwierig. Was man, ebenfalls wie üblich, nicht über jeden Tag sagen kann. SPOILER ALERT: Im Folgenden erzähle ich was über die Puzzle und die Rahmenhandlung des Advent of Code dieses Jahr. Wer die Puzzle noch machen oder die Story noch lesen möchte, sollte nicht weiterlesen.
Eine Fetch-Quest
Wie schon in meinem ursprünglichen Post zum Advent of Code dieses Jahr erzählt, ging es darum, die weltweite Schneeproduktion zu retten. Die Wettermaschine aus 2015 ist dafür zu klein. Also wird man mit einem Tribok in den Himmel geschossen, um zu schauen, was denn da oben los ist.
Diese Aufgabe entfaltet sich zu einer klassischen fetch-quest. Knapp die ersten zwei Drittel der Puzzle laufen nach dem folgenden Schema ab:
- Man landet auf einer schwebenden Insel
- man reist auf der schwebenden Insel umher und löst Puzzle, um sich die Zeit zu vertreiben.
- man trifft auf jemanden, der einem sagt, dass auf der Insel etwas von der nächsthöhergelegenen Insel fehlt, um das zu liefern, was die Insel darunter braucht.
- Man löst ein Puzzle, um zur nächsten Insel weiterzureisen.
Man landet zunächst auf der Schneeinsel, der Wasser für die Schneeproduktion fehlt. Von dortaus reist man per Seilbahn weiter zur Insel-Insel (eine Schwebende Insel, die einen See und viele Insel beherbergt), die zwar Wasser hat, aber keinen Sand, um das Wasser für die Schneeinsel zu filtern. Per Luftschiff geht es weiter zur Wüsteninsel, die zwar Sand hat, aber keine Ersatzteile für die Geräte, um den Sand nach unten zu liefern.
Von der Wüsteninsel reist man dann per Hanggleiter zur Getriebeinsel weiter. Dort fehlt Lava als Energiequelle zur Herstellung der Teile, also wird man mit Federn zur Lavainsel geschleudert. Dort muss man einem überdrehten Rentier mit Schutzhelm- und Brille dabei helfen, die Spiegel auszurichten, um die Lavaproduktion wieder in Gang zu kriegen.
Das letzte Drittel geht man wieder die Inseln herunter, löst auf jeder Ebene Probleme zur effizienten Verarbeitung der von oben kommenden Materialien, bis man endlich die Schneeproduktion wieder in Gang gebracht hat.
Die Community
Wie immer lohnt es sich, die Reddit-Community zu verfolgen. Dort werden zum einen Lösungsansätze diskutiert (und man kann anderen beim Debuggen ihres Codes helfen). Vor allem aber kann man sich exotische Lösungsansätze (in esoterischen Sprachen, aber auch in Spielen wie Minecraft, oder in Tabellenkalkulationsprogrammen) sowie schöne Visualisierungen anschauen (wobei die Visualisierungen in den letzten Jahren schöner waren, aber das kann auch daran liegen, dass es dieses Jahr einfach nicht so schöne Vorlagen zur Visualisierung gab).
Allgemein ist mir dieses Jahr aufgefallen, dass die Mods (und Mod-Bots) deutlich rigoroser auf die Form von Posts achteten, unter jeden unzureichend formatierten Post war ein Kommentar von einem Mod oder einem Bot.
„Ungerade Puzzle sind schwer“
Vom Inhalt her sind mir am Anfang hauptsächlich drei Dinge aufgefallen. Zum einen gab es eine Menge Beschwerden über überdurchschnittlich schwere Puzzle und Memes über eine wahrgenommene odd-day-rule, nach der die ungeraden Tage schwierige und die geraden Tage leichte Puzzle hatte. Ich fand die Puzzle am Anfang nicht schwierig, und die gerade-ungerade-Regel hatte sich nach wenigen Tagen auch erledigt.
„Schreibt gefälligst schöneren Code!“
Die zweite Sache, die mir aufgefallen ist: Am Anfang gab es auffällig viele Posts, die sich über die Code-Qualität von Puzzle-Lösungen beschwerten. Darauf waren die allgemeinen Antworten:
- die Code-Beispiele, die man sieht, sind häufig von Leuten, die Hilfe suchen, also unerfahrene Teilnehmer, von denen man keine hohe Code-Qualität erwarten kann
- der Sinn des Advent of Code besteht darin, die Puzzle zu lösen, nicht, wartbaren Code zu schreiben
- „wir müssen den ganzen Arbeitstag lesbaren Code schreiben, in meiner Freizeit mache ich, was ich will“.
Ich persönlich schreibe gerne ordentlichen Code, habe das im AoC aber auch gerne über Bord geworfen, wenn ich am Problem verzweifelte und einfach nur noch eine Lösung wollte.
„Die Beispiele sind schlecht!“
Die dritte auffällige Sache war, waren Beschwerden über die Beispielinputs. Zur Erinnerung: Jedes Puzzle hat einen mehr oder weniger individuellen Input für jeden Spieler, für den eine Lösung gefunden werden muss. Dazu gibt es verkürzte Beispielinputs, um das Problem besser zu verstehen, und um den eigenen Code testen zu können.
Wie jedes Jahr gab es auch dieses Mal jede Menge Posts à la „Help! Code runs on example, but not on real input“. Aber das sind nicht die Posts, die ich meine. Die, die ich meine sind mehr in der Art „Die Beispiele sind schlecht, weil sie nicht jeden Randfall behandeln, wenn mein Code auf dem Beispiel funktioniert, sollte er auch auf dem echten Input funktionieren“. Dazu war die einhellige Meinung: Die Beispiele müssen nicht jeden Randfall abdecken, dazu sind sie nicht da. Alle Randfälle sind explizit oder implizit in der Problembeschreibung enthalten.
„Ich will nicht mehr“
Zum Ende sind mir dann (mehr als in den letzten Jahren) Posts von Leute aufgefallen, die nicht mehr mitkamen und sich dafür schlecht fühlten. Die oft gegebene (imho richtige) Antwort darauf war: Du musst die Puzzle nicht lösen. Das ist Freizeit, es soll Spaß machen, wenn es keinen Spaß mehr macht oder zu viel Stress bereitet, mach nicht weiter“.
Nicht, dass ich mich daran gehalten hätte. Ich sage mir jedes Jahr, dass ich aufhöre, wenn es zu viel Stress macht, und ich höre dann doch nie auf.
Die Puzzle
Allgemein waren die Puzzle nicht schwieriger oder einfacher als in den letzten Jahren. Es gab jedoch viele Puzzle mit dem Schema: Teil zwei ist Teil eins, aber um ein paar Milliarden bis ein paar Quadrillionen hochskaliert. Solche Puzzle gab es auch früher immer, aber diese Mal gabe es viele davon.
Tag 1: twone, nineight und sevenine
Tag 1 war minimal aufwändiger als übliche Puzzle für Tag 1. Aber man kann auch nur so viele Lösungen von „Rechne alle Zahlen im Input zusammen“ machen. Im ersten Teil musste man die erste und letzte Ziffer in einem String zusammensuchen und daraus eine Zahl bilden.
In Teil zwei musste man auch Strings wie one, two, usw. berücksichtigen. Eigentlich ganz einfach. Allerdings gabe es auch Kombinationen wie „twone“ oder fiveight, bei denen sich zwei Ziffern Buchstaben teilen. Wenn man einfach nur nach diesen Wörtern gesucht hat, war das kein Problem. Viele Leute haben jedoch eine schwierigere Lösung gewählt, indem sie zuerst die Worte durch Ziffern ersetzt haben, anstatt nach ihnen zu suchen. twone wurde zu 2ne, die dort vorhandene one ging verloren.
Suchen und ersetzen ist schwieriger als einfach nur zu suchen, und in diesem Fall lieferte es falsche Ergebnisse. Viele Programmiersprachen liefern aber praktische Hilfsfunktionen zum Ersetzen, also kann ich zumindest verstehen, wie man darauf kommt. Ich habe jedoch mindestens eine Lösung in C gesehen, die das gleiche gemacht hat, ohne die Suchen/Ersetzen-Hilfsfunktion. In diesem Fall hat die Person dahinter extra mehr Aufwand betrieben, um eine falsche Lösung zu bekommen. Das verstehe ich nicht.
Erstaunlich viele Leute haben ihren Ansatz auch nicht geändert, als ihnen dieses Problem bewusst wurde. Stattdessen haben sie Sonderfälle eingebaut, z.B. um twone durch 21 zu ersetzen. Das gab schnell eine lange und unvollständige Liste von Ersetzungen. Zumal man Kombinationen wie eightwone beliebig oft aneinanderreihen kann, eine einfache Ersetzungsregel also nicht immer funktioniert.
Tag 3: Zahnräder
Über Tag 2 gab es praktisch keine Beschwerden auf reddit. An Tag 3 ging es um Zahlen, deren Textdarstellungen im Input an bestimmte Sonderzeichen grenzte (und zwar in zwei Dimensionen). Das fanden ein paar Leute schwierig. An diesem Punkt hatten sich einige in den Kopf gesetzt, dass ungerade Tage schwierig und gerade Tage einfach sind.
Tag 4: Rubbellose
An Tag 2 ging es um Rubelllose. In Teil 2 konnte man mit jedem Los mehrere Lose der nachfolgenden Kategorie gewinnen. Die Frage war, wie viele Lose man insgesamt gewinnt.
Also auch wieder einfach. Wie es ein paar Leute geschafft haben, auf minutenlange Programmlaufzeiten zu kommen, habe ich bis heute nicht verstanden.
Tag 5: Samen-Dünger-Mapping
An Tag 5 musste man zunächst Zahlen durch mehrere hintereinanderfolgende Mappings schicken. In Teil 2 musst man nicht einzelne Zahlen, sondern Zahlenbereiche mappen. Das war imho der erste ein wenig anspruchsvolle Tag. Ein naiver Ansatz (alle Zahlen in den Zahlenbereichen individuell mappen) hätte ewig gebraucht, die Bereiche waren in der Größenordnung 10⁹ bis 10¹⁰.
Eine bessere Lösung war, ganze Zahlenbereiche zu mappen. Dabei mussten diese Zahlenbereiche aber ständig aufgeteilt werden. Ich habe es irgendwie geschafft, dass das Ding schon beim ersten Versuch lief, ohne einen einzigen off-by-one-Fehler.
Tag 6: Modellbootrennen
An Tag 6 musste man ein Modellbootsrennen gewinnen. Teil 1 habe ich mit brute-force gelöst. Teil zwei war Teil 1, aber hochskaliert. Brute-force hat trotzdem noch funktioniert. Ich habe aber später noch eine effizientere Lösung implementiert.
Tag 7: Elfenpoker
Tag 7 war wieder einfach. Man musste Punkte zusammenrechnen, die sich aus den Werten einer Poker-Hand ergaben. Wenn ich die Beschreibung ordentlich gelesen hätte, dann hätte ich das auch auf Anhieb gelöst. So musste ich eine Extrarunde drehen. Wenigstens war mein Fehler so eklatant, dass meine Lösung schon für den Beispielinput fehlschlug.
Tag 8: Durch die Wüste
In Tag 8 musste man der Wegbeschreibung eines Geistes folgen. Teil 2 wäre eigentlich auch einfach gewesen, wenn ich die Problembeschreibung richtig gelesen hätte.
Tag 9: Vorhersagen
In Tag 9 musste man Werte aus einer Kette von Werten vorhersagen, in Teil zwei auch einen vorgegangenen Wert extrapolieren, also im Prinzip Teil 1 rückwärts. Auf reddit: Kommentare, wie einfach doch Tag 9 war (und dann auch noch am Wochenende, wo die Schwierigkeit sonst häufig hoch geht).
Tag 10: Hamsterröhren
In Tag 10, Teil 1 musste man einen Hamster durch ein Röhrensystem verfolgen. Schwierig war hier nur, den Input zu parsen. In Teil zwei musste man die von der Haupröhre eingeschlossene Fläche ermitteln. Bisher das kniffligste Puzzle, aber mit einem Trick konnte ich mir die Lösung wesentlich einfach machen. Hier wieder: Umrechnung zwischen zwei Koordinatensystemen, habe eine Menge dummer Umrechnungsfehler gemacht.
Tag 11: Sterneabstände
Tag 11 war auch wieder einfach, aber auch wieder eines der Puzzles, wo Teil 2 eine Hochskalierung von Teil 1 war. Eine effiziente Lösung war trotzdem recht offensichtlich, auch wenn ich natürlich wieder off-by-one-Fehler gemacht habe.
Tag 12: kaputte Federn, ganze Federn, unbekannte Federn
Über Tag 12 wäre ich fast gestolptert. Für mich definitiv einer der schwierigsten Tage dieses Jahr. Meine Lösung am Ende war ein Programmierchaos voller Sonderfälle, bis ich da alle Bugs raus hatte, war fast Mitternacht.
Tag 13: Tal der Spiegel
Tag 13 war wieder einfach, selbst Teil 2 war mit einem einfachen Brute-Force-Ansatz zu lösen. Ich habe darauf verzichtet, Teil 2 zu optimieren, weil ich immer noch von Tag 12 überwältigt war.
Tag 14: Rollende Steine
Tag 14 war wieder eins von diesen Hochskalierungsproblemen. In diesem Fall habe ich es gelöst, indem ich nach Zyklen Ausschau gehalten habe. Das hätte deutlich besser funktioniert, wenn ich nicht schon wieder einen dummen off-by-one-Fehler gemacht hätte.
Tag 16: Spiegel und Licht
Tag 15 war einfach, nicht der Rede wert. Tag 16 war eine schöne Graphenexploration, Teil 2 ging einfach genug zu bruteforcen, also habe ich das gemacht.
Tag 17: Lava-Loren
Tag 17 war ein klassisches kürzeste-Pfade-Problem mit positiven Kantenkosten, also: ALgorithmus von Dijkstra. Es gab einen Twist, aber der war nicht der Rede wert, nicht so wie der Irrgarten mit dem Elefanten im letzten Jahr. Teil 2 erforderte nur leichte Anpassungen.
Tag 18: Gräben graben
Tag 18, Teil 2 war für mich hauptsächlich deswegen schwierig, weil mir das notwendige Hintergrundwissen fehlte. Eine kurze Internetrecherche brachte mir die Gaussche Trapezformel, mit der ich das Problem lösen konnte, zumindest, nachdem ich für ein paar diskrete Eigenheiten beachtet habe.
Tag 19: Workflows
Tag 19 war ein solides Kombinatorikpuzzel, das ich zu meiner eigenen Überraschung ohne off-by-one-Fehler hingekriegt habe.
Tag 20: Schaltkreise
Tag 20 war einer der vier schwierigsten Tage dieses Jahr. Man musste wieder einmal eine Aufgabe extrem hochskalieren. Eine Lösung habe ich erst gefunden, als ich mir meinen Input angeschaut und festgestellt habe, dass er im Prinzip aus vier digitalen Zählern bestand, die alle zur gleichen Zeit eine bestimmte Zahl haben mussten. Nachdem ich diese Zahlen ermittelt habe, konnte ich einfach das kleinste gemeinsame Vielfache dieser Zahlen nehmen, um an das Ergebnis zu kommen.
Tag 21: Unendliche Gärten
Tag 21 fing, wie auch Tag 20, harmlos an. Trotzdem war es für mich eines der schwierigsten Puzzle. In Teil 1 musste man einem Elfen sagen, auf welchen Feldern im Garten er landen kann, wenn er 64 Schritte geht (wobei er immer auch besuchte Felder wieder besuchen kann).
Teil 2 erweiterte dieses Problem auf über 2,5 Millionen Schritte und einen unendlichen Garten (der Garten aus Teil 1, zyklisch aneinendergereiht). Eine einfache Graphenexploration fiel also nicht in Betracht.
Mir ist schnell aufgefallen, dass der Äußere Rand des Gartens aus begehbaren Feldern besteht. Was mir nicht sofort aufgefallen ist, war, dass auch die mittlerewn Achsen immer komplett frei waren. Damit konnte ich dann die Lösung finden. Allerdings nicht ohne noch eine Menge Fehler im Code zu machen, hauptsächlich, welche Felder jetzt mit geraden und welchen mit ungeraden Schritten erreichbar waren. Wenigstens konnte ich die Ergebnisse aus Teil 1 nutzen.
Die ist auch glaube ich das erste Puzzle (überhaupt), bei dem meine Lösung nur für den echten Input, nicht für den Beispielinput funktioniert, weil der Beispielinput nicht die freien Achsen in der Mitte hat, die für meinen Ansatz essentiell waren. Ich musste meine eigenen Beispiele bauen, um den Tag zu schaffen.
Tag 21 war der erste Tag dieses Jahr, den ich nicht innerhalb von 24 Stunden nach Veröffentlichung gelöse habe.
Tag 22: Sandstein-Jenga
Tag 22 war ein breather. Keine Probleme hier, bis auf dass ich genauer hätte lesen sollen, welchen Wert ich bei Teil 2 als Lösung angeben soll.
Auf reddit fanden ein paar Leute selbst Teil 1 extrem schwierig. Insbesondere hatten einige Leute übersehen, dass der Input in keiner Weise sortiert war.
Tag 23: Längster Pfad
In Tag 23 musste man ein längster-Pfad-Problem lösen. Das ist nur laut Wikipedia NP-vollständig. In Teil 1 war das auch kein Problem, beim genaueren Betrachten war der Graph ein gerichteter azyklischer Graph, für den das Problem leicht zu lösen ist.
In Teil 2 viel diese Spezialität weg, aber die Anzahl der Knoten war (nach einer kleinen Optimierung, die ich schon in Teil 1 benutzt habe), nur 36. Mein Brute-Force-Ansatz hat zwar 45 Sekunden gebraucht (also muss es noch eine schnellere Lösung geben), aber das Ergebnis war korrekt, also habe ich nicht länger nachgehakt.
Tag 24: Hagelsturm
Tag 24 hat mir Weihnachten versaut. In Teil zwei musste man einen Stein werfen, so dass er (wenn er sich auf einer geraden Linie bei konstanter Geschwindigkeit bewegt) alle Hagelkörner im Input trifft (die sich auch bei konstanter Geschwindigeit auf einer geraden Linie bewegen). Gesucht waren Startposition (und Geschwindigkeit) des Steins.
Ich habe den ganzen Tag lang versucht, das Problem analytisch zu lösen, ohne Erfolg. Ich bin einfach zu eingerostet. Nach ein paar Optimierungen hatte ich dann am nächsten Tag einen Brute-Force-Ansatz, der drei Sekunden lief und mir nach einigen Schmerzen auch die richtige Lösung lieferte (immerhin konnte ich hier den Beispielinput zur Verifikation verwenden).
Tag 25: Rotes Kabel oder blaues Kabel?
In Tag zwei musste man zwei Gruppen miteinander verbundender Komponenten lösen, indem man nur drei Kabel durchtrennt. Also eigentlich ein max-flow/min-cut-Problem. Nur halt vereinfacht, weil jede Kante nur eine Kapazität von 1 hat.
Ich hatte schnell eine Lösung, und hätte damit meinen persönlichen Rekord für 50 Sterne in einem Advent of Code gestellt, aber ich hatte ja Teil 2 vom vorherigen Tag nicht geschafft.
Advent of Code 2018
Irgendwann im Monat habe ich auch Teil 2 von Tag 23 aus 2018 gemacht. Das hatte vorher bei mir nicht funktioniert, obwohl ich letztes Jahr eine Optimierung eingebaut habe, die aber trotzdem noch explodiert ist.
Dieses Jahr fiel mir dann auf, dass ich den Suchraum zu klein definiert habe. Nun könnte man denken, dass eine Vergrößerung des Suchraums die Suche noch verlängert. Tatsächlich war aber das Gegenteil der Fall: Weil jetzt die optimale Lösung im Suchraum lag, konnte ich direkt mehr suboptimale Lösungen aussortieren, was verhinderte, dass mir das Teil um die Ohren flog.