Blog

Advent of Code, Tag 22: Mischen von Karten bis in alle Ewigkeit

Jochem Schulenklopper

Aktualisiert Oktober 21, 2025

7 Minuten

Der Advent of Code-Kalender hat heute ein teuflisch schweres Rätsel freigeschaltet - eine der schwierigeren Herausforderungen in diesem Jahr, gemessen an der Zeit, die die ersten hundert Teilnehmer benötigten, um beide Teile zu lösen. Etwas mehr als zwei Stunden... während Teil 1 relativ einfach war, wie Sie in den Scatterplot-Visualisierungen der täglichen globalen Ranglisten sehen können.

Beachten Sie den großen Sprung zwischen den Lösungszeiten von Teil 1 und Teil 2.

Die Herausforderung bestand darin, ein Kartenspiel (bestehend aus 10007 Karten anstelle der normalen 52) nach einer Anleitung zu mischen. Kinderleicht, wie der Koch Jamie Oliver zu sagen pflegt. Definieren Sie einfach eine Lambda-Funktion für jede Anweisung in der Eingabe, wenden Sie alle Anweisungen seriell auf einen geordneten Kartensatz an und geben Sie schließlich die Position der Karte mit der Aufschrift "2019" zurück. (Das ist nicht von Jamie. Das Mischen von Zutaten erfordert ein anderes Rezept.)

Blick über den Tellerrand von Teil 1

Jeden Tag, während Sie an Teil 1 arbeiten, fragen Sie sich: "Wie wird Teil 2 aussehen?" und "Passt mein derzeitiger Ansatz zur Lösung von Teil 1 auch für Teil 2?" Die Antwort auf die zweite Frage lautet zum Glück oft "mmm, ja". Sicher, es kann sein, dass Sie einige Änderungen vornehmen müssen, dass Sie einen anderen Wert berücksichtigen müssen, dass Sie mit etwas komplizierteren Anweisungen arbeiten müssen, dass Sie einen Prozess nicht nur einmal, sondern viele Male durchführen müssen, dass Sie Teile Ihrer Logik umkehren müssen.

An manchen Tagen - und der 22. Dezember 2019 ist so ein Tag - erfordert Teil 2 eine völlig andere Zusammenstellung (die ich ehrlich gesagt für heute noch nicht abgeschlossen habe). Für den heutigen Teil 2 würde das Deck aus 119315717514047 Karten bestehen und muss 101741582076661 mal gemischt werden.

Ich bin mir noch nicht sicher, ob es relevant ist, dass die Anzahl der Karten eine Primzahl ist, genauso wie die Anzahl der Wiederholungen des Mischvorgangs. Es könnte durchaus sein, dass die Anweisungen nur die Logik eines fortgeschrittenen kryptographischen Algorithmus sind.

Was ich weiß, ist, dass die herkömmliche Art der Speicherung des Kartenspiels nicht machbar ist - die Erstellung eines Arrays von 119 Terakarten dauert ewig, genauso wie die Durchführung von 101 Terashuffles auf einem normalen Laptop. Rechnen Sie einfach die Kombination aus diesen beiden.

Wir müssen also die Anweisungen analysieren, herausfinden, wie sie sich auf das Kartenspiel auswirken - beachten Sie, dass wir nur an der Karte an einer bestimmten Position im Deck interessiert sind - und ein wenig intelligente Mathematik anwenden, um das heutige Rätsel zu lösen. Ich hoffe nur, dass wir SHA-3 nicht knacken werden.

Wer freut sich über eine Primzahl von Karten?

Kürzlich habe ich meine Kollegen befragt, welche Art von Advent of Code-Rätseln sie mögen und welche Arten sie nicht mögen. Das Fazit ist, dass wir Visualisierungen der Mathematik vorziehen.

I favor puzzles describing a concrete situation, a situation that I can visualize mentally (or on paper). Puzzles about navigating through real and solid stuff, like rooms, mazes, trees, and forested areas. Challenges about moving physical things, like packages, elves, trees (again) and elevators. Problems on manipulating strings or numbers, stacks, trees (again) and lists.
That leaves out the kind of problems that are more of the abstract kind. Puzzles in which an imaginary situation or device is being described, and needs to be simulated. Things that are harder to make a mental image of. Yes, those assembunny programs, communicating Elfcode devices, programmable wrist things and Intcode interpreters clearly fall into this category.

I fear high math. If I can solve it with a dumb-but-working idea I'm generally good to go, but at some point it goes beyond me.
I love puzzles that have a cool visual at the end of it. One of my favorites was… last year? Where there were these basins that filled with water and you saw this awesome picture with lakes and flows. It's what inspired me to really go for visualization this year…

I love graph-related puzzles, they give me the feeling my study in computer science wasn't a complete waste of time. I sincerely dislike puzzles that cost a lot of effort (i.e., lots of code) to solve (as I only have a very limited time budget with a baby around the home). My particular weakness in puzzles is stuff with angles and rotations. For some reason I always screw those up a couple of times before finally ending up with the right implementation

Was, heute kein Intcode?

Nein, offensichtlich nicht. Der Intcode-Computer wurde in diesem Jahr häufig vorgestellt - am 2. Dezember und an jedem ungeraden Tag nach dem 5. Dezember. Für Advent of Code ist diese Häufigkeit ungewöhnlich, denn in den vergangenen Jahren wurde das Thema einer Herausforderung nicht oft wiederholt oder für einen anderen Tag inspiriert.

Wenn Sie mich fragen, dann mit gemischten Gefühlen. Rätsel, bei denen der Intcode-Interpreter zurückkehrt, schaffen Abhängigkeiten zwischen den Tagen. Vor allem, wenn Sie Tag 9 noch nicht abgeschlossen haben, könnten Sie die Aufgaben vom 11., 13., 15., 17., 19. und 21. Dezember nicht lösen. Diese Anzahl von Abhängigkeiten zwischen den Rätseln ist in diesem Jahr ungewöhnlich hoch.

Andererseits ist es eine schöne Darstellung der Kreativität von Eric Wastl, da die Intcode-Programme an verschiedenen Tagen vielen verschiedenen Zwecken dienen und auf viele verschiedene Arten verwendet und sogar mit ihnen interagiert wird. Statt einiger relativ versteckter Algorithmen, die die verschiedenen Eingaben für die Teilnehmer generieren, hat Advent of Code nun verschiedene Intcode-Programme generiert, die die Eingaben für die Teilnehmer erzeugen.

Es ist erwähnenswert, dass die Technik der Intcode-Verschleierung - als ob der Intcode selbst nicht schon obskur genug wäre - ebenfalls von Tag zu Tag variiert. Wie Eric erklärt hat, sollte das Schreiben eines Intcode-Transpilers in eine Sprache höherer Ordnung oder die manuelle Transpilierung mehr Zeit in Anspruch nehmen als das direkte Lösen des Rätsels. Ich glaube, er hat dieses Ziel erreicht, denn ich habe noch nicht viele Intcode-Programmanalysen gesehen, bei denen man feststellt: "Ah, das ist es, was dieses Ding tatsächlich tut!" Es muss eine fortgeschrittene Einrichtung geben, die die verschiedenen Intcode-Programme erzeugt.

Es ist eine Art magische technische Kreativität

Während ich diesen Beitrag schrieb, hörte ich mir "The Rocket" von Wintergatan an. Es ist ein Lied, das einfach und repetitiv beginnt... bis es im zweiten Teil (!) des Liedes in schöne Variationen ausbricht, bei denen die Stimmen des Akkordeons mit der hohen Stimme einer Modulin überlagert werden.

Sie kennen Wintergatan vielleicht von ihrem Epos Marble Machine, einem phantastischen Stück musikalisch kreativer Technik. Man fragt sich, wie diese Maschine erschaffen wurde und wie sie funktioniert (zumindest einmal, während man das Video aufnahm).