Advent of Code 2020 - Day 23

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 exercise requires tracking the positions of numbers 1 through nine in a circular buffer, starting in the sequence given in the input, and performing 100 moves like this:

• Take the three number following the current one out.
• Select the destination as current number minus one, keep going down if it is not in the buffer (i.e. if it has been taken out), and wrap around to the highest value if you go below the lowest one.
• Insert the three numbers you took out next to the destination number.
• The new current number is the one next to the current one

Part1

We will represent the circular buffer as a deque. We will keep the current number at position 0 as a way to easily track it.

The step function performs one move. We start by looking at which is the current number, then rotate the buffer one place to the left, both updating the current position for the next step and setting the numbers that have to be taken at the beginning of the buffer so we can take them out using popleft. We next find the destination number (keep subtracting one as long as the destination is not in the buffer, i.e. while it is in the taken out triplet, with wraparound), and the corresponding position (index), and insert the numbers right after it. We insert them in reverse order at the same position, but we could also insert them in order incrementing the position with each step.

Part 2

For this part we will take 1,000,000 numbers. The initial ones are scrambled as given in the input, and after that in order. And also we perform 10,000,000 moves.

With these numbers, the approach from part 1 is too slow, it requires too many memory reorganizations when performing the moves.

To solve this we will build a data structure that doesn't require moving the data around: a linked list, where only the references of which number follows which need to be updated, and it can be done locally (in our previous version, taking out the initial numbers requires moving close to the full million numbers, and then all numbers after the destination for each insertion). Although I have to admit that I spent some time looking for a more mathematical approach.

We will create a CircularList class for this specific problem. It will keep a list of nodes, so that the node content (the number) matches the position in the list. Each node contains a value (the number) and a reference to the next node in the list. It will also have a head, a reference to the current number.

Since Python lists are 0-indexed, we will shift all numbers by -1 (it does not change the behaviour), and undo the change afterwards. There is no significant performance penalty: the subtraction need only be made for the initial 9 numbers, as the rest is generated already shifted; and only two numbers of the output need to be converted back.

A different option would be representing the linked list as a dictionary with the numbers as keys, and the successors as values. The way we have it is more explicit on the linked list concept, but the dictionary would be more efficient.

As we are making the class specific to the problem, we will give the initial sequence and the total size as inputs. We generate all the nodes, without connections, and then set the connections. For the first nine we need to follow the initial sequence (modified by the -1), and then they go in order, until the last one which connects back to the first number (not necessarily the first node!).

We build extract and insert methods to make the intent clearer. Inserting is relatively easy: we get the destination node, take its successor for later (the restart), and connect it instead to the head of the list to insert. Then we take the last node of the list we are inserting, and connect it to the restart.

Extraction is a little bit more complicated, but not much. We take the head, and move four steps through the links to record where it will restart. Then we build the extracted list by taking the three nodes following the head, and disconnecting the last of them from its successor. Finally we connect the head to the restart.

With this operations, the step is trivial, and now the problem is solved efficiently enough.