Advent of Code 2020 review

Now the Advent of Code has come to an end, time to take stock of how it went and what I learnt.

I look forward to Advent of Code each year. It's the one real time I have to get some decent programming done in Haskell. I like Haskell. I seem to think quite naturally in the way that Haskell wants you to. And it seems to be working: I'm more proficient at programming in Haskell than I was in 2016.

And please look at the posts for the individual problems this year, and last year.

Performance

I was asked about the performance of my solutions. I knew they were reasonably quick, but it's good to get some numbers on them.

For an overview, here's the runtimes shown graphically:

It's clear that day 11 is the only program that takes appreciable time (16 seconds), with the next longest being day 20 at 3.8 seconds.

Here's the detail on times and memory use.

These are for a PC with an i7-4930K CPU @ 3.40GHz (6 cores, 12 threads), 64Gb RAM, and still running everything else on my desktop PC. GHC automatically spreads tasks across CPU cores, so the runtimes reflect that parallelism. Note that stack seems to take 0.35 seconds to start up, so that time has been removed from the reported times.

Similarly, stack seems to require that all programs take about 72kb of memory; the only exceptions to this are days 15 and 23, where I allocated structures with tens of millions of slots. The "allocations" figure is the amount of memory allocated at some point: most of it is released and garbage-collected during the run. Even for day 11, the vast numbers of allocations are kept within a small total space.

Generally, I was impressed with the performance of these solutions, especially as I rarely did any form of optimisation: in day 11, I cached the seat neighbourhoods, and in day 22 I used a bespoke hash function to speed checking of repeated states. I only used mutable storage in day 15 and day 23; everything else was Haskell's normal immutable data structures, though most of them were strict.

Haskell features

I don't know if the challenges this year were better-suited to base Haskell, or I was being less adventurous, but I think I only used a small range of features. These are the packages I used, and how often each was used.

text, attoparsec and megaparsec were used most days, to parse the input. (I still like how parser combinators work, giving robust and readable parsers. Much, much nicer than the line noise that regexps often become.) I used containers a lot for either Sets or Maps (or both), and once for Sequence. Beyond those, I didn't use a great deal special.

I'll consider that a compliment for the AoC team, who were able to put together a wide range of challenging problems that could be solved with just a few basic building blocks. Well done, folks!

Some other bits of Haskell that could be good to know, but didn't get much use this time.

Typeclasses

I used these a few times in 2019, but only twice in 2020.

Once was in day 17 where the overall logic of the task remained the same, but the underlying data structure changed. In day 17, that was moving from a 3-dimensional grid to a 4-dimensional grid. In that case, only a couple of low-level operations depended on the structure. I picked them out into a typeclass and made the rest of program polymorphic over that class.

The other use was in day 25 where I used a newtype to redefine the integers to combine with modular multiplication.

Lenses

Lenses are a great feature for dealing with complexly-nested structures, with many layers of structure. These things weren't needed this year, so the need for lenses didn't arise. The one use of them was when I used pointed lists, as the implementation suggested use of a lens to manipulate the focus element.

Monads and monad stacks

Ah, monads. That scary word. Again, not much used because there wasn't a need for them. I used a Reader monad in day 11 to pass around a pre-computed neighbourhood for each seat. I used lists as a monad in day 20 to implement a depth-first search of tile arrangements. I used the ST monad for mutable storage in day 15 and day 23. But nothing seemed to require the use of a State monad or an RWS stack, unlike the heavy use of both in many Intcode puzzles last year (both the Intcode interpreter, and in how sequences of them were put together).

Things to look forward to

There are still some techniques in Haskell that I see used, but haven't mastered yet. The things on my to-do list are

• type-level programing
• GADTs
• arrows
• free monads, comonads, algegras, and coalgegras

Perhaps next year!

Code

Just in case you've missed it, you can find the posts, the code, and the code on Gitlab.