Advent of Code 2020 - Day 15

This is a running series of posts on the Advent of Code 2020. The introductory post has the details, including the accompanying GitHub repo, in case you reached this directly.

This puzzle asks us to run a game for a number of turns. From the problem description:

In this game, the players take turns saying numbers. They begin by taking turns reading from a list of starting numbers (your puzzle input). Then, each turn consists of considering the most recently spoken number:

• If that was the first time the number has been spoken, the current player says 0.
• Otherwise, the number had been spoken before; the current player announces how many turns apart the number is from when it was previously spoken.

Part 1

We will start by directly simulating an infinite game like this. We will use a generator (defined in the game function), and then just take as many turns as needed, as the question is the number said on the 2020th turn. To make it easier, we will use itertools.islice to run the desired number of turns.

We set up a memory using a dictionary which will keep track for each number the turn when it was last said. If it hasn't been said, it's not in the memory.

The start of the game consists of saying the seed numbers. We can just go through them, add them to the memory with the corresponding turn, and yield them. But we need to stop before the last one. This we need to treat slightly differently to jumpstart the game logic.

We increment the turn and say (yield) the last seed number, and keep it as last_number, then we enter the loop that is repeated indefinitely. First we decide what's the next number to say: zero if last_number is not in the memory, or the difference between the current turn and the turn when it was last said, taken from the memory (this is why we still haven't updated the turn, otherwise we would overcount the difference by one). We store the turn in which last_number was said, and then we can update the turn and say the new number. Note that the order of deciding the new number and storing the old one is interchangeable. Finally we just set the new number to be the last one in the next run of the loop.

Part 2

For this part, we need to go to the 30,000,000th turn. Since part 1 was almost instantaneous, we can try to just run the game for that long. It takes only a few seconds, which is good enough, so no additional work for this second part, except to change the target turn.