Advent of Code 2020: Day 25 with Generators in Python

It's the last day! After a really long description, it turned out to be more straightforward than you'd expect.

The Challenge

Link to challenge on Advent of Code 2020 website

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.

The code

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 card and 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[1][1] because I didn't bother destructuring what is returned by zip and gen_loop

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[1][1])

And that draws this year's Advent Of Code to a close, many thanks to Eric Wastl for creating it

A retrospective

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 set.symmetric_difference_update() function?
• 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 readlines() and splitlines()
• 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

What's next?

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!

Happy Holidays!