The description of the problem can be found on the Advent of Code website. I usually post my solutions on the subreddit but this time it’ll use so much math notation I think it’ll be more readable here since equations can be rendered with MathJax.

Part 1 doesn’t require any smart tricks or math. Part 2 on the other hand…

I’ll firstly show a less naive approach for part 1 which can then be slightly modified to get us an answer for part 2. Let

• $L$ be the number of cards,
• $K$ the number of repetitions,
• $n$ the number of instructions.

We’ll consider functions $f: \{0,\ldots,L-1\} \to \{0,\ldots,L-1\}$, where $f(x) = y$ means that the card at position $x$ after applying $f$ to the deck will be at position $y$. For factory ordered deck it means $x$ is the card.

Notice that all operations can be described in modulo arithmetic:

• Reverse: $r(x) = (L - x - 1) \mod L$
• Cut: $c_N(x) = (x - N) \mod L$
• Increments: $i_N(x) = (N x) \mod L$

Hence, we’ll be working in a field $\mathbb{Z}/L\mathbb{Z}$ of integers modulo $L$. It sounds scary but what it practically means is that we do each operation modulo, so, for example, $a +_L b = (a + b) \mod L.$ We need to be careful though:

• Make sure your language/your functions handle negative numbers correctly. For example, in C/C++ % is not a modulo operator for negative integers.
• Division requires two steps: $a/b = a\cdot b^{-1}$ – find the inverse of $b$ modulo $L$ and then multiply it and take modulo. (Note: inverse can only be found if $\gcd(b,L)=1$, but the numbers in the puzzle are prime so we can inverse any number other than $0$). How to calculate the inverse? I’ll let you search for that one.
• The numbers are big, multiplication is the most probable to overflow, so a big numbers library or a language which has BigInts by default is recommended.
• You’ll have to calculate some big powers but it can be done efficiently with exponentiation by squaring.

Let $f_1, f_2, \ldots, f_n$ be the instructions given in the input in the order they appear (for each $j$, $f_j = r, c_N,$ or $i_N$). Then part 1 can be described as the composition of all these functions:

$$f = f_n \circ f_{n-1} \circ \cdots \circ f_2 \circ f_1$$

If you’re not familiar with the notation it means that the final position of card $x$ is

$$f(x) = (f_n \circ f_{n-1} \circ \ldots \circ f_2 \circ f_1)(x) = f_n(f_{n-1}(\ldots(f_2(f_1(x)))\ldots)$$

Notice that all the functions are affine, so their composition is also affine, therefore

$$f(x) = ax+b$$

for some $a,b \in \mathbb{Z}$.

We can find $a,b$ with a program by using the formulas above. SymPy, Mathematica, or other CAS can calculate it easily. In an imperative language like Python or Julia, one way is to store $f$ as an array or a tuple $(a,b)$ (starting with $(1,0)$) and apply to it each instruction based on the formulas above. So:

• Reverse: $(a,b) \to ((-a) \mod L, (-b + L - 1) \mod L)$
• Cut: $(a,b) \to (a, (b - N) \mod L)$
• Increments: $(a,b) \to ((N a) \mod L, (N b) \mod L)$

We need to apply $f$ $K$ times. In other words, we want to calculate $f^{(K)}(x)=y$. For example:

$$f^{(1)}(x) = f(x) = ax+b$$

$$f^{(2)}(x)=f(f(x)) = f(ax+b) = a(ax+b)+b = a^2 x + ab + b$$

$$f^{(3)}(x)=f(f^{(2)}(x)) = a(a^2 x + ab + b) + b = a^3 x + a^2 b + a b + b$$

We can see the inductive pattern, so the formula for an arbitrary $K \ge 1$ is

$$f^{(K)}(x) = a^K x + (a^{K-1} + a^{K-2} + \ldots + a + 1) b$$

We can simplify it even further by noticing that the coefficient of $b$ is a geometric sum which has closed formula $\frac{a^K - 1}{a-1}$ (amazingly, it works for any field, so the formula works with modulo operations too).

Hence, the final formula is

$$f^{(K)}(x) = a^K x + b(a^K - 1) (a-1)^{-1}. \tag{a}$$

Note: if you want your solution to be more general you should handle the case when $a = 1$ separately since there’s no inverse of $0$.

The final algorithm for part 1 is thus: find $f(x) = ax+b$ by applying the given instructions in order, then use formula $\text{(a)}$. Remember to do all operations modulo $L$.

For part 2, we ask the opposite: the position is now the input and the card is the output. This means the problem now asks us for the inverse $f^{-1}(x)$ instead of $f(x)$. From the properties of function composition, this is

$$f^{-1} = (f_n \circ f_{n-1} \circ \ldots \circ f_1)^{-1} = f^{-1}_1 \circ f^{-1}_2 \circ \ldots \circ f^{-1}_{n-1} \circ f^{-1}_n.$$

So only the first part (before the formula) changes in our algorithm: we apply the inverse of each instruction in reverse order. The inverses of the instructions can be found with simple algebra: solve the equation $f_i(x)=y$ for $x$ and you’ll get the formula for $f^{-1}_i(y) = x$.

Here’s my Julia code.