Advent of Code is a website that releases programming puzzles every December from the 1st to the 25th. The puzzles have two parts, and the second part isn't revealed until you solve the first part.

This year, there have been many questions regarding part 2 of day 22, as it involves modular arithmetic in a way that hasn't been seen in previous puzzles there. I have been asked for a tutorial for it on Reddit, but I'm posting it here due to better support for mathematical notation.

First off, if you are unfamiliar with modular arithmetic, I encourage you to read my other blog post, Modular Arithmetic for Beginners. The most important thing to understand from there is how the four basic operations (addition, subtraction, multiplication, division) can be redefined to work in modular ($$$\mathbb Z / p \mathbb Z$$$ field) arithmetic. I also recommend you try some of the puzzles linked (This one is appropriately Christmas-themed too). The terminology and notations I'll use will also be similar.

It is possible to solve this without explicitly invoking modular arithmetic (see this post for an example) but they basically amount to rediscovering certain properties of modular arithmetic anyway, as such that's the "language" I'll use for this tutorial.

The first thing to notice is that each of the given instructions amount to a transformation on the position of each card. Let $$$m$$$ represent the number of cards in the deck.

• "deal into new stack" moves cards from position $$$x$$$ to position $$$m - x - 1$$$. We can write this as $$$f(x) = m - x - 1$$$.
• "cut $$$n$$$" moves cards from position $$$x$$$ to position $$$x - n\ \text{ mod } m$$$ (note how indices "wrap around" to the other side), Thus $$$f(x) = x - n\ \text{ mod } m$$$. Note this also works for the version with negative $$$n$$$.
• "deal with increment $$$n$$$" moves cards from position $$$x$$$ to position $$$n \cdot x\ \text{ mod } m$$$. Thus, $$$f(x) = n \cdot x\ \text{ mod } m$$$

The next thing to notice is that each transformation can be rewritten in the form of $$$f(x) = ax + b\ \text{ mod } m$$$. This is called a linear congruential function, and forms the basis for linear congruential generators, a simple type of pseudorandom number generator.

• "deal into new stack": $$$f(x) = -x - 1\ \text{ mod } m$$$, so $$$a = -1, b = -1$$$
• "cut $$$n$$$": $$$f(x) = x - n\ \text{ mod } m$$$, so $$$a = 1, b = -n$$$
• "deal with increment $$$n$$$": $$$f(x) = n \cdot x\ \text{ mod } m$$$, so $$$a = n, b = 0$$$

The next step is to see what happens when you compose two arbitrary linear congruential functions $$$f(x) = ax + b\ \text{ mod } m$$$ and $$$g(x) = cx + d\ \text{ mod } m$$$. So what do you get if you evaluate $$$g(f(x))$$$? By substitution:

$$$g(f(x)) = c(ax + b) + d\ \text{ mod } m$$$

As I established in Modular Arithmetic for Beginners, algebra works with modular residues similarly to real numbers, so let's expand:

$$$g(f(x)) = acx + bc + d\ \text{ mod } m$$$

An alternate notation for $$$g(f(x))$$$ is $$$f\ ;g(x)$$$ ("first apply $$$f$$$, then apply $$$g$$$"). Further more, we can abstract all linear congruential functions (LCF) as its own data type, consisting of a tuple $$$(a, b)$$$. Thus we can implement a compose operation between two LCFs:

$$$(a, b)\ ; (c, d) = (ac \text{ mod } m, bc + d\ \text{ mod } m)$$$

We store all LCF coefficients modulo $$$m$$$, to avoid them growing too big and slowing down our program or taking all available memory. Also note the possible pitfall: when multiplying two residue values, it's possible to overflow even the 64-bit data type, as our modulus for part 2 exceeds $$$2^{32}$$$. If you use a language with an arbitrary-size number type (e.g. Java's BigInteger), that'd do. If you don't, you might consider either importing a third-party library, or you can implement "multiplication by doubling" via a process similar to "exponentiation by squaring" described on the Modular Arithmetic for Beginners page. It's not the most efficient way to get around this problem, but for our purposes it'd work fine.

With these methods, you can translate all the steps in your puzzle input into LCFs, then compose them successively ($$$f_1\ ; f_2\ ; f_3\ ;...$$$) into a single LCF. Let's call it $$$F$$$. Recall that we've stored it as a tuple $$$(a, b)$$$ representing the equation $$$F(x) = ax + b\ \text{ mod } m$$$.

$$$F$$$ now represents a single shuffle as directed by your input. You can test your implementation by re-solving part 1 with it. (note that you have to re-compose it with a different modulus for each part.)

However, we require over a hundred trillion shuffles (we'll call this number $$$k$$$), so we can't just compose $$$F$$$ into itself naively. There are two approaches to solving this problem:

Method 1:

Compose $$$F$$$ into itself $$$k$$$ times algebraically. Do a few rounds by hand on paper and you'll notice a pattern emerge:

$$$F^k(x) = a^k x + (a^{k-1} + a^{k-2} + ... + a^1 + 1) b\ \text{ mod } m$$$. The more-formal notation would be $$$\displaystyle F^k(x) = a^k x + \sum_{i=0}^{k-1} ba^i\ \text{ mod } m$$$.

The summation forms a geometric series. According to that Wikipedia page, we can thus transform the expression to: $$$\displaystyle F^k(x) = a^k x + \frac{ b(1 - a^k) } { 1 - a } \ \text{ mod } m$$$

Exponentiation by squaring is required to perform the exponentiations, and modular multiplicative inverse to perform the division.

Method 2:

Notice that composing LCFs are associative, i.e. $$$(f\ ; g)\ ; h = f\ ; (g\ ; h)$$$.

Proof: $$$h(g(f(x))) = h(f\ ; g(x)) = g\ ; h(f(x)) = f\ ; g\ ; h(x)$$$

Note that this doesn't uniquely apply to LCFs; composition of any "pure functions" (i.e. always returns the same output for a given input) is associative. This is computationally useful for any function that can be composed in a similar manner to what we do here with LCFs before invoking them with actual parameters.

The "exponentiation by squaring" method works on all associative operations, so it can be adapted to the compose operation as well. We can thus obtain $$$F^k$$$, $$$F$$$ composed into itself $$$k$$$ times.

For example, we could adapt the pseudocode for exponentiation by squaring (from Modular Arithmetic for Beginners) like this:

function pow_compose(f: lcf, k: int64) → lcf:
    g := lcf(1, 0)
    while k > 0:
        if k is odd:
            g := compose(g, f)
        k := ⌊k/2⌋
        f := compose(f, f)
    return g

Notice how multiplication is replaced with the compose function we used to compose the steps in the input, and the initial multiplicative identity of 1 is replaced with the "identity LCF" $$$f(x) = x \text{ mod } m$$$, i.e. $$$(1, 0)$$$

Continued:

Now for the last step. Notice that we're not asked for where card $$$x$$$ ends up, but rather what card is in position $$$x$$$. To do that, we need to invert the function $$$F^k$$$. Let $$$F^k(x) = Ax + B\ \text{ mod } m$$$.

We invert it by substitution: $$$x = A \cdot F^{-k}(x) + B\ \text{ mod } m$$$, therefore $$$F^{-k}(x) = \dfrac {x - B} A\ \text{ mod } m$$$. Again this requires an application of modular multiplicative inverse.

Plug in $$$2020$$$ for $$$x$$$, and we should finally get our solution. Whew.