It's the last day! After a really long description, it turned out to be more straightforward than you'd expect.
The challenge description is extremely long, but it boils down to brute-forcing a pseudorandom number generator, in a way that's somewhat reminiscent of public key cryptography, but you don't actually need to know this.
The algorithm is simply:
- Using a sequence generator starting from 1, and subject of 7, find out how many iterations are needed until the output is one of the numbers given in the input
- Then re-run the sequence generator this many loops using the other number as the subject
The "sequence generator" is of the form:
value = (value * subject) % 20201227
This is actually a Lehmer pseudorandom number generator, which is a special case of the LCG which is commonly the function behind the most basic
rand() function in some programming languages. The thing to know about PRNGs is that they're actually sequence generators that have a very large pattern before it repeats, though none of these facts are particularly pertinent to the challenge.
Since the brute-force operation requires us to run this sequence generator one iteration at a time to check its value, it's best that we use a generator to do this, as we don't need or want to re-calculate the loop every single time:
def gen_loop(subject): value = 1 loop = 0 while True: loop += 1 value = (value * subject) % 20201227 yield loop, value
The generator returns the loop number as well, for our convenience.
Then, we write a loop to run this generator multiple times until the output is the value we want. The
door values are given to us by the challenge.
card = 5764801 door = 17807724 for loops, val in gen_loop(7): if val == card: break
At the point at which this loop breaks, the value
loops will contain the number of loops of the generator. This completes the first step. The next step is to use these numbers with the generator again.
I wanted to re-use the generator function, so ended up writing the code a little weirdly, but the below is essentially running the generator for
loops many times, and returning the value:
for val in zip(range(loops), gen_loop(door)): pass
When this is done,
val contains our answer. (actually it's in
val because I didn't bother destructuring what is returned by
The full code is therefore:
card = 5764801 door = 17807724 def gen_loop(subject=7): value = 1 loop = 0 while True: loop += 1 value = (value * subject) % 20201227 yield loop, value for loops, val in gen_loop(7): if val == card: break for val in zip(range(loops), gen_loop(door)): pass print("val", val)
This is the first time I've done Advent Of Code, I'm usually not a fan of coding puzzles, as they always felt dry and pointless to do. However, Advent Of Code is written with interesting narrative, which keeps things interesting, but more importantly, the private leaderboards feature that makes it easy to have a friendly competition (or collaboration) between a group of friends, while discussing different ways to solve the puzzle or giving each other clues. In my opinion, this is the best way to do the puzzles.
I think the difficulty level of Advent Of Code is targeted at those with a couple years programming experience. But even those with much more experience can further challenge themselves to find more optimum solutions to the problems.
Doing these puzzles, I've learned a lot of new things, as well as refreshed my knowledge of python and its libraries. In particular:
- Python sets. I hardly get to use these regularly, AoC gave me a good workout, and lead to me understanding much more about how python's sets work under the hood. Also, who knew about Python's
- Python complex numbers. I literally only found out that Python supported these on the Day 24 challenge
- A lot about python file reading. Particularly the difference in how newlines are treated by
- NetworkX is a new library that I learned, to tackle the Day 7 challenge, which I continued to use wherever I could
- TensorFlow is a library I've had a lot of contact with, but never really sat down to work out from scratch
- Parsimonious is a library I've used before, but having used it on multiple challenges, I now feel much more confident in it and writing PEG grammar to solve particular challenges
- Transitions is another library I've used before, but again, having used it more in the challenges, I've become more familiar with it
I'll definitely consider doing more AoC next year, though perhaps I won't be blogging it, as it's a real timesink. We'll see what life's like in December 2021.
In the mean time, now that AoC is over, it's time for a new side-project. I'm thinking of Making a game that teaches Git as the next project, let's see how things go!