Advent of Code 2018

As I realised the 1st December is coming up this Sunday, I thought I would make a slight plug for the Advent of Code (AoC) project by sharing some of my experiences of it last year.

Overview

The AoC is a set of daily Christmas-themed coding puzzles throughout the month of December, of varying difficulty. It can be attempted in any programming language, thanks to each puzzle having a unique input data and corresponding answer for each user. It is (IMHO) best enjoyed as part of a group leaderboard; in my case, we had a small leaderboard for our friendship group and made a WhatsApp group to discuss different puzzle approaches and help each other when we were stuck. In addition, we made a GitHub repository to share our code.

I was keen to take part mainly because coding had been a fairly recent venture for me as an important aspect of my PhD, and not being from a CS background, I felt it was a good excuse to learn some handy coding practices that I may have missed out on. I chose to work with Python as it was the language I was learning at the time. Some others in our group who had been coding for a much longer time took it as a chance to learn a new language and worked with Go.

The difficulty of the puzzles ranged from being able to complete without much sweat over morning coffee, to ones which would generate lengths and lengths of discussion on the WhatsApp group. The source of difficulty varied from day to day; sometimes it would be difficult just to describe a procedure in the first place that would generate a solution to the problem (ignoring any time or complexity constraints), on other days it would be easy enough to write an algorithm that would eventually generate a solution but might take infeasibly long to do so unless you make some appropriate choice of data structures.

The main benefit I got from doing AoC was a hugely increased awareness of important data structures/routines, which can both make writing code much easier (not writing convoluted routines for something that there’s already a built-in one-liner for) and make said code run much faster/more efficiently. I should stress that I got this benefit by taking part in AoC socially – by discussing approaches with friends taking part in AoC and reading code that they shared, I became aware of all these structures and routines that I had previously no reason to look for. I also found it a lot of fun.

For the rest of this post I’ll share some of the cool structures/routines that I learnt as part of AoC and how they improved my general coding:

Dictionaries

The first (and possibly the most useful) structure I learnt of which has now become part of my standard toolkit, is the dictionary (dict) and default dictionary (defaultdict). The only difference between defaultdict and the usual dict is that if you look up the value for a key that has not yet been added to the dictionary, dict will throw a KeyError whilst defaultdict will return a default value lambda, which you choose when you initiate the dict.

I came across this data structure when part of a particular routine I had written early on in AoC, involving checking whether an item was part of a list somewhere else, and doing something with said item depending on the answer, was running far too slowly. The routine went something like this:

def is_thing_in_list(thing,list):
  for i in range(len(list)):
    if list[i]==thing:
      return True
  return False

It certainly did what it said on the tin and gave the right answer, but as both the size of the list grew, it was too slow (O(N) for the size of the list). Someone suggested that I try a different data structure, and I came across the dict and defaultdict. The dict uses a hash function to store the value for each key, so is designed for quick (O(1)) lookups.

This meant the above routine could be replaced with both a much shorter to write and quicker:

is_in_list = defaultdict(False)

This structure now appears very often in my work on graphs/networks, where routines like “if this node/edge already exists in the graph, do X, otherwise, do Y” often pop up.

Regular Expressions (regex)

Another skill I learnt which has been helpful for work I am doing now is regular expressions, or regex. Sometimes the input data for AoC (as in real life) had a natural structure, e.g. a list of numbers, a long string of characters or something that can happily be converted to a table. However, there were a few times where the data was only semi-structured, an example being a text log from last year’s Day 4:

[1518-06-12 23:57] Guard #2633 begins shift
[1518-04-11 00:09] falls asleep
[1518-04-10 00:56] falls asleep
[1518-10-22 00:36] wakes up
[1518-11-08 00:57] wakes up
[1518-03-28 00:00] Guard #2423 begins shift
[1518-11-02 00:02] Guard #727 begins shift
[1518-04-14 23:56] Guard #2777 begins shift
[1518-09-02 00:45] falls asleep

Each line consists of something that can be understood as a date+time with a text log message, some of which contain guard ids which need to be parsed, others not.

Regular expressions are used to look for specific patterns in text data and so are well primed for being able to take a line from a log like this and separate it into its important components. After looking at some online resources for regex writing, I eventually came up with something like:

regex = "\[(?P<yy>\d+)-(?P<mm>\d+)-(?P<dd>\d+) (?P<hh>\d+):(?P<min>\d+)\] (?P<event>.*)"

which looks slightly nasty but once used later in the code, says something along the lines of “I’m looking for something in format [yy-mm-dd hh:min] event” where yy, mm, dd, hh, min are integers, and event is anything left over at the end. This sort of technique was useful for reading in other files from AoC into some format with more structure, and is indeed something I’ve been able to use since for parsing data that is in the form of a text log of sorts.

Other things

Other things I learnt which have been since useful:

• Try to use something other than a for loop if it is a large loop!
• That being said, the Python generator statement is a nice way of abbreviating for loop syntax [do(this) for this in loop]
• The Python Counter method is very handy.
• Unit tests are important!!

Overall, as well as the practical aspects I took from the experience, I found it lots of fun and very much enjoyed the social aspect of it. I hope you enjoyed reading this and that if you participate this year you will enjoy it as much as I did. I’d also like to say thanks to Eric Wastl and all involved in developing AoC, Eder Fernandes who introduced me to it, and friends participating who were very generous with coding advice.