Day 22: Slam Shuffle

---

Links:

• Puzzle on adventofcode.com
• Source Code

I didn’t have time yesterday (on the 22nd) to finish this post, so I’m writing it retroactively. I’m going to keep this short for I’d rather start with day 23.

I’m not even gonna go over all the details of the first part. I just solved it by applying the shuffles to a list representing the deck and then getting the final index of the value 2019. Even after solving the second part I left the first part untouched. Not only because I didn’t have the time to change it but because I feel like this is another one of those “break the puzzle lore to solve it” puzzles. It’s (probably) physically impossible to perform the actual work to solve the second part before the year ends. Some maths magic is needed instead. You already know how I feel about this but hey, at least I got to revisit modular arithmetic, so there’s that.

My approach for the second part was to find out what shuffling the deck once does to any particular card and expressing that as a function $f(n)$ which determines the position of the card at position n after the shuffle. To determine this function we can look at the three types of shuffles:
All of them can be expressed as changes to the offset of the first card and the “step” we take to get to the next card (the increment).

deal into new stack only reverses the deck. This changes the sign of the increment but also moves the offset to the “other end”.

cut n cards shifts the deck to the left or right. That is because the deck behaves like a circular buffer. Add n to the offset and the increment remains unchanged.

deal with increment n is the hardest one. We know that the ith card moves to the position $i * n \bmod DECK SIZE$. The first card remains at the same position so the offset doesn’t change. The increment changes by the modular inverse of n.

If you want to know more, there are far more qualified people (with more time) explaining it over at the subreddit.

After running through all shuffles we know the offset and increment changes. Now we just need to scale this to the gazillionth iteration. Thankfully the increment is independent and just multiplies with the original increment for every additional iteration. In other words it’s just $incr^n \bmod DECK SIZE$. The offset depends on the increment at that iteration though. Luckily it behaves just like a geometric series and so we can use $offset * \frac {(1 - incr^n)} {(1 - incr)}$ (use the modular inverse for the division instead).

Now that we have the total offset and increment we can finally calculate the final position of the 2020 card.

The real challenge for me was to stop the multiplications from overflowing all the time. I was too tired to implement modular multiplication $a * b \bmod c$ so I switched to 128 bit integers instead.

---

Overview
Previous day Next day