Fork me on GitHub

Reflections on Advent of Code 2022 in Futhark

Posted on December 25, 2022

Advent of Code is a website by Eric Wastl that since 2015 has published a daily programming puzzle from the 1st to 25th of December. It is also a contest, where people compete to see who can finish them first. I don’t like programming competitions myself, but I enjoy the social aspect of AoC where you can discuss solutions with your friends and colleagues, and most of the problems are simple and interesting enough that they don’t take too long. Futhark is not a good choice for solving these kinds of puzzles - there is no guarantee that any meaningful parallelism is present, and the dearth of libraries for basic data structures somethings make solutions more tedious than one would prefer. Still, I decided to give it a try.

I also did Advent of Code in Futhark in 2018. However, because Futhark is not a very good language for string processing, I wrote Python programs to parse the text input and generate values in Futhark’s native data format. But then in 2021, Snektron did Advent of Code in Futhark including parsing (probably because this was not nearly as difficult as implementing a compiler in Futhark). I decided I also had to do that.

And so I did! Here is Advent of Code 2022 fully implemented in Futhark. The puritan will note that there still is a tiny Python program that prepends a header so that Futhark will be able to recognise a file as a byte array. The input parsing was much less problematic than I expected, and for some problems were actual the only place where parallelism was possible! The main task is splitting the input into strings, and I just so happened to have recently written a word splitter that was easy to convert to a line splitter. Beyond that, ad-hoc parsing methods were quite sufficient.

The Advent of Code problems are not specifically designed for parallel execution, but I was amazed at how many of them actually permitted meaningful use of parallel algorithms this year - although the problem input sizes were usually much too small for parallelism to be beneficial.

Bottom line up front: I can definitely recommend designing your own programming language and then solve Advent of Code problems with it. Here follows a brief summary of my observations for each problem.

I am overall pleased with my implementations. Also, I encountered far fewer compiler bugs this year than in 2018, so it seems that Futhark is actually getting better. I think it is a shame that Day 16 (and probably 19) weeded out so many participants, because the following problems were much more tractable and fun.