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:
- A card
- 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
Top comments (0)