Advent of Code 2020: Day 23 with linked lists in Python

This is the most interview-questiony of advent of code challenges. It's all about linked lists

The Challenge Part 1

Link to challenge on Advent of Code 2020 website

This part of the challenge involves a circular list of numbers, where each round of a game requires doing some operation to them: take the current pointer in the circular list, remove the next three numbers, find another number anywhere in the list that is the next value smaller (excluding the numbers removed). Then re-insert the numbers at that point.

Importing the data

The data is a string, which should be split into an arry, so simply:

raw = "389125467"
data = list(map(int, raw))

Linked List

There are many different methods to solve this problem, I'm going with a linked list as the question immediately elicited memories of past interviews, so it seemed fitting. But there's other optimizations possible, particularly since the circular list contains continuous numbers.

Here's a classic linked list, with a little goodie for later: a gen() function to help traverse the linked list.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def gen(self, count):
        cur = self
        for _ in range(count):
            yield cur
            cur = cur.next

The gen() function records the current node, and then yields each subsequent node in turn, so it's possible to traverse the list using:

for node in nodes.gen(10):

And this will traverse 10 steps of the nodes. This little utility is used later on.

Linking nodes together

Each cup (as the game describes it) is a node. We need to create and link these nodes together. However, there's a small additional thing we have to deal with - because at some point the algorithm requires us to find another node based on its value, we not only need a linked list, but also a lookup table of values to nodes. So let's generate that lookup table first:

cups = {value: Node(value) for value in data}

This generates a dictionary to serve as the lookup table, where the key is the value contained in the node. This also creates all our nodes at the same time.

Next, we link up the nodes. I'm going to use a reduce() (from functools import reduce) to achieve this:

def link(prev, cup):
    prev.next = cup
    return cup

last_cup = reduce(link, cups.values())

It should be noted that in Python, the dictionary maintains the insertion order, so cups.values() returns our nodes in the order they are set, which matches the order of values in data.

This is a sort of weird way of doing it, but effectively reduce() starts with the first two items in the iterator given to it (in our case, a generator of all the nodes in cups), runs the function (link()) on that pair, which in my case causes the first node's next to be set to the second node; and then the second nodeis returned. On every subsequent iteration, the link() function is passed this previous return value, and the subsequent item from the generator. In this way, each nodeis linked to the next. The return value is effectively the last node in the list, which we can link back around to the first one to complete our circle.

current = last_cup.next = cups[data[0]]

I also go ahead and set current to the same value since I want current to start off pointing to the first node.

Removing 3 cups

The game algorithm's first step is to pick up 3 cups after the current on. To do this with a linked list, we want to unlink the current node and attach the 4th node down the line to it, removing the 3 nodes between from the circle.

Since I've made it super-easy to generate successive nodes, I can do it like this:

*pickup, current.next = current.gen(5)

This actually does two steps in one. First, it creates a generator with 5 items in it: the current node, and the four that follows it. It sticks the four in pickup, and the final node gets assigned into current.next, which effectively removes the 3 nodes between them out of the circle, as the rules require.

The reason pickup contains 4 nodes (the current one plus the 3 we want to remove) is explained next:

Finding the target

The next step in the algorithm is to find a cup whose value is one below the current one from the nodes remaining in the circle. Also, if the current cup is already the lowest value of those that remain, wrap around to the maximum cup value.

try_value = current.value
while cups[try_value] in pickup:
    try_value -= 1
    if try_value < min(data):
        try_value = max(data)
destination = cups[try_value]

This loop starts try_value with the current node value, and then keeps looping while that cup is one that was picked up. This was why we needed pickup to contain the current node as well. If it didn't, we'd need some more lines of code to do this.

An if statement implements the wrap. Once the loop is done, try_value contains the distination cup's value, and we can get the node by looking it up in the cups Node lookup constructed earlier.

Placing 3 cups

Next, the algorithm wants the 3 cups to be replaced in the circle next to the destination node. This again, is easily done by inserting the first picked up cup as the next property of the destination node; and making the former next node of the destination the next node of the last cup picked up.

pickup[-1].next = destination.next
destination.next = pickup[1]

Note, we use pickup[1] here because pickup[0] was the current node, and the only reason that node is in the pickup list was to allow us to save a few lines of code in the while loop earlier.

Finally, to end the round, we advance the current pointer to the next node:

self.current = self.current.next

That's the whole algorithm for one round of the game. The first part of the challeng wants us to run this 100 times, so the whole of the above goes into a simple loop.

Getting the output

The output needs to be all the successive values to the cup labelled 1. Since we have that nice gen() function, we can just find the cup with value 1, and use gen() to give us the next 8 cups needed by the output:

result = (cup.value for cup in cups[1].next.gen(8))
print("output", "".join(map(str, result)))

This produces the stringified output that the challenge wants.

The full code, with the above turned into functions:

from functools import reduce

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def gen(self, count):
        cur = self
        for _ in range(count):
            yield cur
            cur = cur.next

class CupsGame:
    def __init__(self, data):
        self.min_cup = min(data)
        self.max_cup = max(data)
        self.cups = {value: Node(value) for value in data}

        def link(prev, cup):
            prev.next = cup
            return cup

        last_cup = reduce(link, self.cups.values())
        self.current = last_cup.next = self.cups[data[0]]

    def run(self, count):
        for _ in range(count):
            *pickup, self.current.next = self.current.gen(5)

            try_value = self.current.value
            while self.cups[try_value] in pickup:
                try_value -= 1
                if try_value < self.min_cup:
                    try_value = self.max_cup

            destination = self.cups[try_value]
            pickup[-1].next = destination.next
            destination.next = pickup[1]

            self.current = self.current.next

    def output(self, value, count):
        return (cup.value for cup in self.cups[value].next.gen(count))

raw = "872495136"
data = list(map(int, raw))

game = CupsGame(data)
game.run(100)
print("output", "".join(map(str, game.output(1, 8))))

The Challenge Part 2

The second part of the challenge wants us to use a linked list that's a million items long, and run the game ten million times. And multiply together the two numbers next to the 1 node.

Ok, sure, let's do that:

data = list(map(int, raw)) + list(range(10, 1000001))
game = CupsGame(data)
game.run(10000000)
cup_a, cup_b = game.output(1, 2)
print("prod", cup_a*cup_b)

The code is reasonably efficient already, so running the algorithm ten million times still only takes about 20 seconds. To speed this up more, we would need to eliminate the dictionary lookup, and use an array instead of a dictionary of nodes.

Onward!