Combo Breaker

Advent of Code 2020 Day 25

Task: Solve for X where...

X = an encryption key

Example puzzle input

5764801
17807724

It represents two public keys:

1. A card
2. A door's lock

A series of misunderstandings from not carefully reading the instructions

• I misunderstood the subject number transformation algorithm. I thought the second step was to calculate the remainder from dividing the magic number 20201227 by the value - the instructions clearly state it as the other way around.
• I misunderstood that the subject number is known for both card and door: 7. Again, the instructions clearly state this known value. Unfortunately, I spent most of my time attempting to solve this puzzle building an algorithm to discover a common subject number.
• I misunderstood how the numbers resulting from each transformation of the subject number actually fluctuate below and above the public keys. The example input is intentionally deceiving about this, in my opinion.

I built the wrong algorithm that only worked on the example input

• It's purpose is first to find the common subject number...which is already provided
• It works on the example input because coincidentally all remainders among the first ~12 transformations are less than the larger public key, and two of the remainders overlap with the two public keys

I built a simulator that only further confused me

• I was still incorrectly set on a quest to discover the correct subject number shared among both keys
• Using my puzzle input - and starting from a subject number of 2 - I blazed through 30-80 transformations for each subject number 2-50...then gave up assuming I had a bug in my code
• I updated the simulator to correctly determine the encryption key. Try it out with your input, and feel encouraged to inspect the code

Another solver's one-line solution to the rescue!

After confusion turned to frustration, I turned to my most trusted JavaScript solver's solution: NullDev

Unsurprisingly, he solved this challenge with one assignable and one command.

Extract both public keys from the input string
Set an array with two initial values, [1,1]
While the second number is not equal to the door's public key
  Do two operations:
    1. Update the second number to the result of the equation: (value * 7) % 20201227
    2. Update the first number to the result of the equation: (value * card's public key) % 20201227
Return the value now stored in the first number

What seeing this solution taught me

• The hard-coded 7 made me return to the instructions and realize I didn't need to find a subject number
• After changing this code to include a third number - to log the loop size of the door's public key - I realized its enormous size (in the millions) and how far off my algorithm was
• The second operation made me realize that this puzzle only required finding one public key's loop size
• The second operation made me return to the instructions and recognize the performance opportunity of NullDev's algorithm: simultaneously apply to one key each transform from the other key's correct loop size

Here are the values after each iteration of the edited while loop

Enc. key  Public key       Loop size
[1,              1,        0]
5764801          7         1
13239263        49         2
6286092        343         3
17588834      2401         4
8144799      16807         5
19339482    117649         6
16501187    823543         7
16669039   5764801         8
11273191  20152380         9
12070132  19859298         10
14897079  17807724         11

Another puzzle that reassures my intent for continuing this series

• I have to read the instructions closely to avoid solving the wrong puzzle
• I built simulators in order to better understand how my algorithm works - or doesn't
• There's no shame in looking at another solver's code - if it is eloquent enough, it will offer a rewarding A-ha! moment
• Documenting my experience in these articles is the best way I know to ensure I learn from my mistakes and, on occasion, celebrate each small but significant rewarding success