Advent of Code, day 22: Shuffling Cards Until Eternity

Advent of Code‘s calendar unlocked a fiendishly hard puzzle today — one of the more difficult challenges this year as judged by the time the first hundred competitors needed to solve both parts. A little bit over two hours… while part 1 was relatively simple, as can be seen in the scatterplot visualizations of the daily global leaderboards.

The challenge was to shuffle a deck of cards (consisting of 10007 cards instead of the normal 52) according to some instructions. Easy-peasy, as chef Jamie Oliver likes to say. Just define a lambda function for each instruction in the input, serially apply all instructions to an ordered deck of cards, and ultimately return the position of the card labeled “2019”. (That’s not from Jamie. Mixing ingredients requires a different recipe.)

Looking beyond the horizon of part 1

Every day, during working on part 1, you wonder “what’s part 2 going to look like?” and “will my current approach for solving part 1 also fit for part 2?” Often, the answer to the second question is “mmm, yes”, luckily. Sure, it may require some changes, keeping score of some other value, dealing with a slightly more complicated set of instructions, performing some process not just once but many more times, reversing parts of your logic.

Some days — and December 22, 2019 is such a day — part 2 requires a completely different setup (that I honestly haven’t completed yet for today). For today’s part 2, the deck would consist of 119315717514047 cards and needs to be shuffled 101741582076661 times.

I’m not sure yet about the relevance of the number of cards being a prime number just as the number of shuffle repetitions is; multiplying two large primes is often used in cryptography. It could well be that the set of instructions is just the logic of some advanced cryptographic algorithm.

What I do know is that the traditional way of storing the deck of cards is unfeasible — creating an array of 119 teracards takes ages, just as performing 101 terashuffles on a normal laptop. Just figure the combination of those two.

So, I guess we need to analyze the instructions, discover how they affect the deck of cards — note that we’re only interested in the card at one specific position in the deck — and apply some smart mathematics to tackle today’s puzzle. I just hope that we’re not breaking SHA-3.

Who enjoys a prime number of cards?

Recently, I asked my colleagues about what kind of Advent of Code puzzles they liked, and which types they weren’t fond of. The summary is that we’re preferring visualizations over mathematics.

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

What, no Intcode today?

No, apparently not. The Intcode computer has been featured often this year – on December 2nd and every odd day after the 5th. For Advent of Code, this high number of occurrences is uncommon, as in previous years a challenge’s theme was not often repeated, or inspiration for another day.

If you’d ask me, it’s with mixed feelings. Puzzles in which the Intcode interpreter returns create dependencies between the days. Especially if people haven’t completed day 9, solving challenges of December 11th, 13th, 15th, 17th, 19th and 21st couldn’t be commenced. This amount of inter-puzzle-dependencies is unusually high this year.

On the other hand, it’s a nice display of Eric Wastl’s creativity, as the Intcode programs serve many different purposes on different days, and are used and even interacted with in many different ways. Instead of having some relatively hidden algorithms to generate the different inputs for participants, Advent of Code now has generated different Intcode programs that generate the input for participants.

It’s worth noting that the technique for Intcode obfuscation — as if the Intcode itself wasn’t obscure enough — differs per day as well. As Eric has stated, writing a Intcode transpiler to a higher-order language, or doing the transpilation manually, should take more time than just solving the puzzle directly. I think he has achieved that goal, as I haven’t seen many Intcode program analyses discovering “ah, that’s what this thing actually does!” There must be an advanced setup that generates the different Intcode programs.

It’s a kind of magic engineering creativity

While writing this post, I listened to “The Rocket”, by Wintergatan. It’s a song that starts simple and repetitive… until it breaks out into nice variations in the second part (!) of the song, using the voices of the accordion’s layered with a modulin’s high voice.

You might know Wintergatan from their epic Marble Machine, a fanastic piece of musically creative engineering. It makes you wonder how that machine was created, and worked (at least once, while taping that video).

Any sufficiently advanced technology is indistinguishable from magic.

Arthur C. Clarke