Thomas Ip

Advent of Code 2020 - Recap

Aoc2020

Advent of Code is an annual programming contest hosted during December, where participants solves a Christmas themed puzzle for each day of the month until the 25th. The puzzles themselves are fun and rewarding, but what makes it extra enjoyable is the community on reddit, be it the solution megathreads, the visualizations or the memes, you can always learn something new or have a good laugh.

I managed to solve pretty much every puzzle on the day of release, except the second part for day 20 and day 23. For the earlier problems I was able to complete them fairly quickly and have some mental energy left for refactoring and clean up. By day 20 though I was getting a little burnt out and decided to not push through finishing the second part. Good thing is I can always come back and revisit the puzzles after the event.

On using OCaml

The event does not restrict participants to any particular programming language or technology, all you need to do is submit the correct answer (usually an integer), heck you can do them using paper and pencils. I chose to use OCaml so as to get familiar with the language for a compiler project that I am working on, turns out it is actually not too shabby for AoC style problems. Given the functional style and static type system I can almost know my program will work before running it, assuming my logic is correct of course. Native compilation and quick compile times also allows for an iterative style of problem solving needed for more difficult puzzles. I was actually a bit surprised when some of my solutions are faster than similar C++/Rust submissions posted on Reddit.

The standard library itself is not as bad as some critic made it out to be, its documentation, although nothing to boast about, is not doubt much more complete than competing alternatives such as Jane Street's Core/Base. For most days I only pulled in Containers, which provides some convenient functionality over the standard library modules. I did tried out using a parser combinator for some of the puzzles, which I have been put off learning for some time now. The one included in Containers is basically unapproachable for the uninitiated so I ended up using Angstrom instead. My experience with these libraries so far has been quite positive.

My biggest gripe with the OCaml ecosystem is with its (lack of) documentation. Yes, type signatures are a form of documentation, but it is only one side of the story, it's equally important to include explanations and examples. A language that I found to be the polar opposite in this regard is Rust. I think having builtin tools for authoring and publishing docs, along with a high standard from the existing ecosystem, contributes to the fact that Rust as a whole has very nice documentations. (More discussion on this topic can be found here.)

The community

After solving the puzzles there are always more fun to be found on the subreddit. After a few days of strolling on the solution megathreads one can see a pattern emerge. The top guys all seem to follow an optimal strategy - solutions are usually written in Python, where input parsing can be done concisely using loop comprehension. Each parsed item are kept in strings as opposed to sum or product types, this rather odd methodology that I ended up adopting actually allows for great flexibility. The algorithmic part of their solutions are usually very straightforward, but not necessarily short, in fact code duplication is commonly seen. Writing simple code means less time to debug, which leads to getting on the leaderboard.

What I found enlightening, however, are solutions written in exotic or esoteric languages. There is always one submission in Dyalog APL, here is an example:

Credit: @jayfoad (https://github.com/jayfoad/aoc2020apl/blob/main/p13.dyalog)
⎕IO0
ap⎕NGET'p13.txt'1
d¨bc(,'x')¨b'\w+'⎕S'&'p
{()d×}d|-a part 1
⎕PP17 ⎕FR1287
gcd{=0: 1 0 g s t| g t(s-t×÷)}
crt{z÷m×/ m|+/×z×1¨z gcd¨}
(-c)crt d part 2
view raw aoc2020_day13.dyalog hosted with ❤ by GitHub

This solves day 13 by implementing the Chinese Remainder Theorem in eight lines of madness1. Apart from APL there are also emojicode, excel, brainfuck, etc, but my favorite solution comes in the form of solving day 13 using Wolfram Alpha. Looking at it now it is such an efficient way in approaching the problem, instead of spending hours implementing complicated mathematics theorem, you can just outsource it to a knowledge base!

Solutions are not all there is though, some users have created incredible visualizations and interactive demos based on the puzzles. Some of the best ones can be found here.


My solutions for AoC2020 can be found on Github.


  1. I like this operator .