11 January 2021 ; tagged in: advent of code , haskell

Advent of Code 2020 review

A look back on the event

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:

Runtimes. Data given in table below.
Program runtimes, with both log and linear scales.

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.

Program Total allocations Max memory Time
advent01 107029176 72440 0.04
advent02 35370072 72440 0.06
advent03 4017640 72504 0.02
advent04 60820368 72504 0.08
advent05 27810256 72440 0.08
advent06 11624856 72504 0.06
advent07 21605440 72444 0.04
advent08 74894192 72508 0.09
advent09 793279616 72508 0.31
advent10 924456 72444 0.01
advent11 35282262592 72504 16.4
advent12 2206400 72508 0.03
advent13 542152 72436 0.01
advent14 259113488 72508 0.26
advent15 6662932672 240372 1.80
advent16 17242880 72444 0.03
advent17 4808712520 72444 1.42
advent18 21509984 72444 0.04
advent19 44456496 72504 0.11
advent20 3860804096 72436 3.77
advent21 9561880 72508 0.04
advent22 3242847728 72500 1.67
advent23 10263690000 95500 1.56
advent24 4352105528 72504 3.13
advent25 39231576 72504 0.06

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.

Package Uses
containers 21
text 18
attoparsec 13
megaparsec 4
vector 4
linear 3
csp 2
monad-loops 2
arithmoi 1
array 1
hashable 1
lens 1
mtl 1
pointedlist 1

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.