Solution Explanation to Day 22 of Advent of Code 2019

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

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

Notice that all operations can be described in modulo arithmetic:

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

Let f1,f2,,fnf_1, f_2, \ldots, f_n be the instructions given in the input in the order they appear (for each jj, fj=r,cN,f_j = r, c_N, or iNi_N). Then part 1 can be described as the composition of all these functions:

f=fnfn1f2f1f = 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 xx is

f(x)=(fnfn1f2f1)(x)=fn(fn1((f2(f1(x))))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+bf(x) = ax+b

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

We can find a,ba,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 ff as an array or a tuple (a,b)(a,b) (starting with (1,0)(1,0)) and apply to it each instruction based on the formulas above. So:

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

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

f(2)(x)=f(f(x))=f(ax+b)=a(ax+b)+b=a2x+ab+bf^{(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(a2x+ab+b)+b=a3x+a2b+ab+bf^{(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 K1K \ge 1 is

f(K)(x)=aKx+(aK1+aK2++a+1)bf^{(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 bb is a geometric sum which has closed formula aK1a1\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)=aKx+b(aK1)(a1)1.(a)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=1a = 1 separately since there’s no inverse of 00.

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

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 f1(x)f^{-1}(x) instead of f(x)f(x). From the properties of function composition, this is

f1=(fnfn1f1)1=f11f21fn11fn1.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 fi(x)=yf_i(x)=y for xx and you’ll get the formula for fi1(y)=xf^{-1}_i(y) = x.

Here’s my Julia code.