Advent of Code 2020: Day 25 with Generators in Python
Tags: adventofcode, python
Published: 2020-12-25 06:45:11

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](https://adventofcode.com/2020/day/25)

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](https://en.wikipedia.org/wiki/Lehmer_random_number_generator), which is a special case of the [LCG](https://en.wikipedia.org/wiki/Linear_congruential_generator) 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:

```py
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.

```py
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:

```py
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:
```py
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](https://adventofcode.com/) to a close, many thanks to [Eric Wastl](https://twitter.com/ericwastl) 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](https://networkx.org/)** is a new library that I learned, to tackle the Day 7 challenge, which I continued to use wherever I could
* **[TensorFlow](https://www.tensorflow.org/)** is a library I've had a lot of contact with, but never really sat down to work out from scratch
* **[Parsimonious](https://github.com/erikrose/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](https://github.com/pytransitions/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](https://dev.to/meseta/lgtm-devlog-0-teaching-git-through-playing-a-game-381j) as the next project, let's see how things go!

Happy Holidays!