Dan Turkel

What I learned through Advent of Code 2022

December 27, 2022 | #programming #python

Landscape with Stars (c. 1905–1908) by Henri-Edmond Cross, via The Met.

December is a time for bringing out the winter jacket, curling up by the fire with a book, and—for many—participating in Advent of Code, an annual set of 25 daily two-part programming puzzles.

The puzzles are in roughly ascending order of difficulty. In 2020, I gave up after 18 days. Last year I did 15. This year (though I skipped a few along the way) I made it all the way to the end, completing 43 of the 50 total puzzles.

Some people like to do AoC in a language that’s fairly new to them, learning as they go. Others try to do every day in a different language, or to ensure that all solutions run in under a second. The guy who finished in first place on the leaderboard this year did the puzzles in a programming language he invented…so there’s that too.

I did the puzzles in Python, the language I know best, but I still managed to learn and try out quite a few new things along the way.

All my solutions are on Github, for the curious reader’s perusal.

Warning: If you’re planning on doing the challenges this year and you haven’t already, a) what are you waiting for?, and b) this post contains some mild spoilers.

The power of friendship

The first 5 or so days of AoC are pretty simple, the next five are reasonable, and after that they start to take a little time. I got a ton of value out of chatting with others about the problems and our approaches, whether that was in my work’s #advent_of_code Slack channel, the NormConf Slack daily puzzle threads, or on Reddit.

I did my best to finish or substantially attempt all the puzzles before resorting to discussion and hints, but there were a few cases where I couldn’t have done it without the wisdom of others (or, in one case, basically just stealing a few lines after banging my head against the wall for too long). It’s really fun to see the sometimes wildly different approaches that people take, whether it’s based on their level of experience, their background, or their choice of language.

Classic algorithms and data structures

Speaking of background knowledge and experience: I only ever took intro to computer science in undergrad, and most of my programming skills are self-taught, so I have a lot of gaps around things you learn college CS courses that you might not pick up in day-to-day programming, namely around algorithms and data structures.

Day 12 involved some pathfinding, and I was able to reuse what I wrote for Day 15 of last year, which I believe is an acceptable attempt at the A* algorithm (though I didn’t know that at the time) that I cobbled together.

Several other problems this year were well-suited to breadth-first search, which is just not something I’ve ever formally learned. I managed to make my way through the problems without a real BFS implementation until day 24 when I was faced with a more complex path-finding problem. I took the Wikipedia pseudocode and turned it into a reasonable solution in Python.

En route, I learned a bit more about queues, a data structure I’d never had much use for before. The advantage of a queue over a list comes when we frequently need to a) add to the end and b) take from the front. Adding to the end of a Python list is fast, but removing an item from the front is O(n). Queues, on the other hand, can give you O(1) insertion and removal from the ends.

You’d think that the best way to implement a queue in Python would be the built-in class called queue.Queue, but this is actually quite slow. It turns out that Queue is better suited to general-purpose communication between threads and incurs overhead to insure thread-safety with locks. On the other hand, collections.deque implements a double-ended queue without the locks needed for fancy multithreading, and serves our purposes at a much faster clip. In my solution, swapping Queue out for deque took the solution from 2.5 to 1.5 seconds.

Match/case statements

New in Python 3.10 is structural pattern-matching, aka the match/case statement. On the surface, it might seem like a fancy way of rewriting if/else statements, and it basically is. However, the syntax allows for substantially more legible code when dealing with complex sets of conditions.

I gave pattern-matching a shot and ended up using it in three puzzles, to great success.

On Day 7, you have to parse a set of faux command line commands and output that look something like this:

$ cd a
$ ls
dir e
29116 f
2557 g
62596 h.lst
$ cd e
$ ls
584 i
$ cd ..

Using pattern-matching made writing my parsing code much neater than writing a bunch of awkward if/elif statements (gratuitously commented here for exposition):

# for each line, we split the line into separate words
match line.split():

    # if we've got 3 words where the second is "cd" and the third is ".."
    case [_, "cd", ".."]:
        # deal with the "go up a directory" case
        folder_sizes.append(node.get_size())
        node = node.parent # type: ignore

    # if we've got 3 words where the second is "cd" and the third is something else
    case [_, "cd", dir_name]:
        # deal with the "go down a directory" case
        node.children[dir_name] = Node(name=dir_name, parent=node)
        node = node.children[dir_name]

    # if we've got 2 words and the second is "ls" *or* the first is "dir"
    case [_, "ls"] | ["dir", _]:
        # deal with those cases (which actually don't require anything)
        pass

    # if we've got any other case of 2 words, it's a filesize and a file
    case [size, name]:
        node.children[name] = Node(name=name, parent=node, size=int(size))

A line like case [_, "cd", dir_name] simultaneously checks that line.split() is three values long, and that the second one is the string "cd", and then lets us use the variable dir_name to capture the third value for the contents of the clause. This is great syntactic sugar for a fancy if statement and, in my opinion, very readable.

On Day 11, we’re once again parsing a predictable series of inputs with different semantics, and this time I used the wildcard pattern to capture an indeterminate number of values:

case ["Starting", "items:", *nums]:
    items_str = f"[{' '.join(nums)}]"

And on Day 13, I had the chance to use type-based pattern-matching to distinguish between cases based on the types of the values:

match left[i], right[i]:
    case [int(), int()]:
        # do int comparisons
        if left[i] != right[i]:
            this_comparison = left[i] < right[i]
        else:
            this_comparison = None
    case [int(), list()]:
        this_comparison = compare([left[i]], right[i])
    case [list(), int()]:
        this_comparison = compare(left[i], [right[i]])
    case [list(), list()]:
        this_comparison = compare(left[i], right[i])

All in all, I was impressed with the flexibility and power of the syntax and I’m looking forward to using this in the future for making complex conditionals more human-readable.

Swifts: Paths of Movement + Dynamic Sequences (1913) by Giacomo Balla, via MoMA.

Python’s built-in profilers

Python is somewhat infamous for prioritizing ergonomics and dynamism over raw performance (though it’s getting faster), but that doesn’t mean it has to be slow. There were a number of problems this year where your approach, choice of data structures, and implementation decisions could make the difference between the code completing in less than a second or maybe not at all.

I got a ton of value out of Python’s cProfile. For my purposes, a simple python -m cProfile my_script.py was all it took to get a bunch of output on which functions or operations were taking the longest. Even if you kill the script before it finishes (because maybe it won’t finish…), you still get the profiler output to figure out what your program is stuck on. It was a great way to find the bottlenecks in my solutions, like an inefficient loop, a list where I could’ve used a set, or a class where I could’ve just used a tuple. In fact, it was the profiler that showed me that the aforementioned Queue was spending lots of time on functions imported from threading.py and revealed that it wasn’t the right data structure I needed.

A quick-and-dirty cache

A common source of grief for beginning Python developers is mutable default arguments. It can be surprising to find that your function has become stateful and the results are changing with each call.

However, this same behavior also lets us easily add a cache to a function. For instance, on Day 24, you have to deal with a 2D grid and you’ll frequently want to generate a list of the points which neighbor a given point without going out of bounds. This is a fairly simple operation, but caching it gives us a nice performance boost:

class Grid:
    def __init(self, lines: list[str]):
        # omitted for brevity

    def neighbors(self, point: Point, cache: dict = {}) -> list[Point]:
        if point in cache:
            return cache[point]

        x, y = point
        candidates = [point, (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
        result = [
            (x, y)
            for x, y in candidates
            if ((0 <= x < self.width) and (0 <= y < self.height))
            or ((x, y) == self.start)
            or ((x, y) == self.end)
        ]
        cache[point] = result

        return result

That cache: dict = {} in the function signature is where the magic happens. An empty dictionary is created when the neighbors function is defined, and that same dictionary (along with anything that gets added to it inside the function) is reused on every subsequent call, allowing us to skip the function body for a dictionary lookup if we’ve already computed the result we need.

With the cache, the script solves the puzzle in about 1.5 seconds (admittedly, one of my slower solutions for all of AoC). Without the cache, it finishes in 3.1 seconds. Removing the cache from another more expensive function in the same solution brings the runtime to 382.0 seconds. Caching matters, and this is a very low-lift way to add one.¹

Type hinting is getting better all the time

Since version 3.5, Python has supported optional type hints: annotations in source code that indicate the type of a variable. This is somewhat tricky business in a language as dynamic as Python, but when combined with type-checking tools like mypy and clever IDE integrations, it can surface bugs early and also serve as great documentation for your future readers.

But typing was a late addition to Python, and the original implementation was a bit less-than-ergonomic, requiring frequent imports from the typing library for anything beyond the most basic annotation. Language enhancements in recent Python versions have made the process much more seamless, and I took advantage of some of those features to add annotations to all my solutions and ensure they all passed mypy checks.

Python 3.9 added “type hinting generics in standard collections,” which is a fancy way of saying that if you want to annotate a list of ints, you can just write numbers: list[int] rather than needing to import List from the typing module to annotate List[int]. It’s a small thing, but it goes a long way in making typing feel more like a first-class feature of the language rather than this odd thing that you can do with an extra module.

Along the same lines, Python 3.10 added the union operator, so a variable that could be a float or a list of floats can be annotated foo: float | list[float] rather than number: Union[float, list[float]] (after importing Union from typing). This also lets you avoid importing Optional: instead you just write foo: float | None.

I also heavily used type aliases, which have apparently been around for a while but which I seem to have missed. It was pretty common to be dealing with tuples of two ints representing coordinates on a grid, and maybe a function returns a list of these coordinates. Without type aliases, we’d annotate the return type as list[tuple[int, int]]. However, with a simple Point = tuple[int, int], we can annotate this as list[Point] instead. Much better!

…but it still has some rough edges

The above notwithstanding, all is still not perfect in Python type world. For one thing, forward references (annotations referring to types not yet defined) still have to be annotated as strings, as was the case in a graph node class I implemented for day 7:

class Node:
    def __init__(self, name: str, parent: "Node | None", size: int | None = None):
        ...

The "Node | None" annotation is the forward reference and it feels hacky. Arguably it should at least be "Node" | None, which seems to be under discussion but isn’t yet supported. Edit: Joel Grus pointed out that this can be fixed with from __future__ import annotations, after which the Node | None annotation works fine. This fixed behavior will be added to a future version of Python. Thanks, Joel!

Worse yet, at least twice I had to cast mypy asside witih a # type: ignore comment to dismiss some nagging edge case I couldn’t fix. In that same puzzle, there is a case where I’m dealing with that same troublesome Node.parent attribute, which is either a Node or None. In the context, I know it’s a real Node and I happily assign its value to a variable which is also a Node, but the type-checker still thinks it could be None (it has no way of knowing it’s not) and throws an error. I believe the canonical solution is to add an if foo is not None: clause in there so that mypy is sure the attribute is non-null in this case, but it feels wrong to add logic to the code just to satisfy the type-checker.

I also found that the value of adding type hints to my puzzle solutions was fairly low. In production code, I’ve had mypy detect sneaky bugs where I was unknowingly relying on behind-the-scenes type coercion rather than being careful about what I pass around. But in Advent of Code the annotations mostly end up being overkill—at best they helped me with rapid refactorings as I rewrote a solution-in-progress.

Walrus Hunt (1801) by Elizabeth Fitzgerald, via the Art Institute of Chicago

Classes as a last resort

It’s easy to make a habit of reaching for a class whenever you start dealing with instances of structured data. I resisted the instinct to class-ify everything during AoC. In one instance, I refactored a solution to remove a class, replacing it with a tuple: the profiler showed me that the overhead of millions of __init__ calls were slowing my solution down and I wasn’t even getting much value out of the class.²

I ended up writing custom classes for 7 of the 25 days, 5 of which were Grid or Board classes that I used to manage movement, storage, and display of points around 2D/3D spaces. The presence of structured data alone is not enough to warrant a class, but when you start to accumulate functions to act on that data and have state that you need to keep track of, a class comes in handy to keep things tidy.

Some people are big fans of Python’s dataclasses, which allow you to easily define classes for structured data with less boilerplate, but I’m not sure I count myself among them just yet. I originally had a dataclass in one or two of my solutions, but I must have refactored them out before finishing. I found that if I only needed a dataclass, I likely didn’t need a full class at all and could replace it with a tuple. In the instances where I did need a class, I had enough initialization logic that I needed to write my own __init__ function, and the dataclass didn’t offer me much.

The walrus operator: Still not for me

Python 3.8 introduced assignment expressions or, as they’re more commonly known, the “walrus operator”. It looks like := and if you squint it kinda looks like a sideways walrus. It’s proposal was the source of near-infinite controversy and drama and the whole affair contributed to Python’s creator Guido van Rossum stepping down from his role as the language’s Benevolent Dictator for Life.

The walrus operator lets you assign a value mid-expression. It’s best demonstrated with an example (adapted from the docs):

# Without walrus operator
# a) separate line for assigning a variable that we will reuse
n = len(a)
if n > 10:
    print(f"List is too long ({n} elements, expected <= 10)")

# b) calculate the length twice
if len(a) > 10:
    print(f"List is too long ({len(a)} elements, expected <= 10)")

# With the walrus operator
if (n := len(a)) > 10:
    print(f"List is too long ({n} elements, expected <= 10)")

Option (b) is potentially bad for performance if you’re doing something more intense than calculating a length. Option (a), however, suits me perfectly fine and all the walrus operator really does is save us a line.

I wanted to keep an open mind and give it a shot if a reasonable use case came up, but I never saw the occasion to use it and even while going back through my solutions I couldn’t find a place where it would make sense to swap it in. I have no strong feelings one way or another about the feature, but my code remains walrus-free, maybe because of my last point…

Verbose is better than terse

Okay, so this isn’t something I learned this time around, but its importance was apparent again and again, especially as I was writing this post and rereading solutions from weeks ago but also as I was debugging almost-working solutions. Your colleagues and future you will appreciate and better understand code that is written clearly, not code that is golfed to a minimum number of lines or characters.

To be fair, for some people a big part of the fun is writing their solutions in as few lines as possible, and that’s okay too! I often checked out r/adventofcode after completing a puzzle and was shocked to find that someone else had written a Python solution in a dozen lines that I’d finished in 100, and I invariably learned something new from those solutions—if I could make sense of them. But as someone who was using AoC to practice and enhance my better programming practices, I found it valuable to take the long road. More verbose code makes code comprehension and debugging easier.

This is arguably captured by few of the lines of the Zen of Python: “Beautiful is better than ugly,” “Explicit is better than implicit,” “Simple is better than complex,” and especially “Readability counts.”

I hope that I stayed true enough to this principle that others can learn something from my solutions if they’d like.

Of course, there’s a limit to just how verbose one needs to be, and so I think I’ll end this post here. See you all again next Advent of Code.

Special thanks to Tim Hochberg and Peter Baumgartner who gave this post an early read.