Advent of Code 2018

02 Jan 2019

Although I first heard of Advent of Code last year, this is the first year I participated. Advent of Code is a set of Christmas-themed puzzles arranged as an Advent Calendar, with a new programming puzzle released daily starting December 1st, leading up until Christmas.

I wanted to brush up on Python 3 syntax, having been using Python 2 for awhile and I decided to start this year’s exercises using a Juypter notebook. I thought that this would be a good way to share my code with others. Unfortunately, after completing a few exercises, I noted the process of developing a solution was fairly difficult. I wanted to run unit tests as a part of developing solutions since I was using Test-driven Development (TDD). However, as you can see if you take a look at the Jupyter notebooks for the initial solutions 1, 2, 3, this wound up being cumbersome. Specifically, the cycle of rerunning the tests was tedious. When I use TDD, I really want to rerun the tests often, and even run them automatically when files change. In a Jupyter notebook, to rerun the code, you re-execute blocks or cells of code manually.

I think that where a Jupyter notebook would be more useful is with something more exploratory, trying to capture a stream of consciousness as one explores a problem space. With these puzzles, especially since there are test cases, there was little of that type of exploration. Having only completed half the puzzles, there may be more problems requiring this type of exploration in the latter half.

Another problem that I had with using a Jupyter notebook is code reuse. There seem to be three straightforward paths to take. Either write the common code as a regular python file and import it into two notebooks, import a Jupyter notebook as a module, or use a single notebook for all of the puzzles. I might’ve tried importing another notebook as a module, but the previous problem with running tests forced me away from using Jupyter.

I wound up switching to use plain Python files, and running unit tests on file changes using the entr command. It accepts a list of files from stdin, and will run a given command when one of those files is changed. I used it like:

find day8* | entr python

which would pipe all the files beginning with day8 to entr. When any of the files changed, entre would run In this way, I could continually evaluate the status of tests and use a red-green-refactor cycle to implement the required features.

As of this writing, I have completed 12 of this year’s puzzles. The code can be found on GitHub. My favorite puzzle was Day 10, which asks you to find the message spelled out by stars. To do this, one had to read input star velocities, then figure out when the stars would converge into an alphabetic passphrase. This turned out to be the moment in time when the bounding box of the starfield reached its smallest size. I also wound up creating a video of the transition by streaming dynamic images created using Pillow to ffmpeg.

I found Day 8’s puzzle to be one of the easiest. It was basically parsing input into a tree, and was easily solved recursively. Day 9 gave me some trouble initially. The puzzle involved a game using a ring of marbles. Each turn involves inserting a marble somewhere in the ring. While a performant solution used a doubly-linked list, I started with a regular list, and when insertions became an obvious issue (it seems the default list implementation has linear time insertions), used blist. While I was happy enough with my solution, I saw on reddit that someone used a deque and its rotate function to great purpose. This is a certainly a case where knowing the right data-structure made the problem simple.

I found Day 6 to be the hardest puzzle of those I’ve done. It asks you to find the areas of influence of each coordinate in a set. The difficulty I had was figuring out what to do with coordinates with infinite areas of influence. I eventually figured out that any coordinates on the border of the bounding box of all coordinates would have infinite areas, and hence should be ignored. This was a very simple solution that just took a bit of thought.

Advent of Code is a great resource if you are interested in programming puzzles. I’m very interested in puzzles and games with programming elements such as SpaceChem and Factorio but these games sometimes are too far removed from actual programming to be of practical use (they are are fun though). The nice thing about programming puzzles and challenges like Advent of Code or Project Euler is that you can actually practice or learn a language that you can use to work on real projects.

Looking for more content? Check out other posts with the same tags: