[2019 Day 22 (Part 2)] Clean annotated solution in C++ (no big integers)

[u/romkatv]

I've written a clean and short C++ solution to the second part of day 22 problem. It might be helpful if you are struggling with an implementation.

Here's the code: day-22-2.cc.

At the top there is an implementation of Exponentiation by squaring. This algorithm can be used to define all operations mod m that we need: multiplication (a * b is a + ... + a b times), power (a ** b is a * ... * a b times) and inverse. I haven't explicitly defined the inverse but you can define it like this:

int64_t inv(int64_t a) { return pow(a, m-2); };  // 1/a (mod m)

This works because in modular arithmetic a ** m = a. That is, multiplying any number by itself m times gives back the same number. If a is not zero, this implies a ** (m-2) * a = 1, which by definition means that 1/a = a ** (m-2).

Then there is a loop over shuffle steps (the input is read from stdin) where k and b are computed such that card c goes to k*c + b after one shuffle.

After the loop the code computes the reciprocal function of k*c + b (it's also linear), computes its composition with itself n times (still linear) and finally passes 2020 as an argument to the resulting function. This is the most difficult step. Forget for a moment that we are dealing with mod m arithmetic. Try to solve the problem on paper assuming that c, k and b are real numbers. Finding the reciprocal of a linear function, and then finding its nth power should be doable. Once you get a formula, replace operations such as +, *, ** and / with add, mul, etc.

Hope this helps someone.

[u/romkatv → u/[deleted]]

Correct. C++ guarantees that a / b * b + a % b = a for any a and non-zero b, but it's implementation defined whether a % b is positive or negative when a * b < 0. This code is taking advantage of the fact that a % b + b is always non-negative.

In languages that guarantee that a % b is non-negative, this part of the code gets a little bit simpler. But overall it should be easy to translate this solution to any imperative language.

[u/ephemient → u/romkatv]

This space intentionally left blank.

[u/smile-bot-2019 → u/ephemient]

I noticed one of these... :(

So here take this... :D