Things I learned through Advent of Code 2022
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.
Classic algorithms and data structures
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 or a list where I could’ve used a set. 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 an int can be annotated number: float | int rather than number: Union[float, int] (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.
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
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.