Advent of Code 2020 - Day 25

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

Part 1

After going through the problem description, we get the following cryptographic process:

• A transformation starts with value 1 and multiplies it modulo 20201227 by the input number a certain number of times (the loop size)
• For the handshake:
• Each side transforms the number 7 using their (secret) loop size; the result is each side's public key
• Each side transforms the other's public key, and the result is the encryption key, which is the same in both cases

We get both public keys and we are asked to find the encryption key.

There is probably a fancy, clever way to do this (or maybe not), but we will start by trying brute forcing it, to see if it finishes in a reasonable time (spoiler alert: it does).

The first step is finding the loop sizes. Given the input number (7) and the public key, we can run one loop of the transformation at a time and check if we have obtained the public key. Once we do, that iteration sets the loop size.

If we want to scrape a bit more of performance, we can check both public keys in the same loop until we find both, instead of restarting the search for each.

Once we have that, it's just a matter of applying the transformation with the corresponding loop size.

Part 2

There is no part 2 on day 25! We get our last star for free.

This finishes the Advent of Code 2020 series. See you for Advent of Code 2021.