Advent of Code 2021 review

Now I've done the advent of code again, are there any lessons I can draw from the event? (You can find all the individual solutions via the Advent of Code tag, and you can read my review of Advent of Code 2020.)

Performance

The Advent of Code site says "every problem has a solution that completes in at most 15 seconds on ten-year-old hardware." My hardware's note quite that old (more like 8 years), but the claim was true for all but two of my solutions.

I profiled my code in two ways: using GHC's profiling tools, and the time command line tool. The GHC tools gave me the raw CPU effort (summed across all cores in use) and the amount of memory allocated (even though much of it was GCed during execution). The command line gave me wall-clock time of execution and maximum memory use.

These graphs show that day 23 and day 24 required vastly more work than all the other days to solve. Both of these challenges took about 25 seconds, with the next-longest time being day 19, which took just under 4 seconds. No problem took a lot of memory. The largest was day 20, and that only took about 200Mb. However, the range of work done means that logarithmic scales give a better view of the profiles.

I wasn't that surprised that day 24 took a long time to execute: I chose a deliberately convoluted way to solve it. I was a bit disappointed that day 23 took so long. Although it was a search problem, it wasn't that large a state space and there's no particular reason why it should have taken so long. Perhaps a better heuristic to guide the search would lead to improvements. One other thing to note is that days 23 and 24 took very different amount of "ticks" (internally monitored time) but similar clock times. I put this down to efficient parallel processing in day 24.

I was also a bit surprised that day 20 took so much space. The final grid was holding a 200×200 grid of elements, and that was represented sparsely as points in a set, and there were only about 18,000 points.

But apart from those outliers, all the performance requirements were tiny. And this year's problems didn't require the reservation of large amounts of space for large problems, before execution could begin.

Language features

I took a look at the packages and modules I used. (A module is something imported into a Haskell program; a package is a collection of modules downloaded and installed together. containers is a package, but Data.Set is a module.)

This shows that I used containers in most days, as it provided the Map and Set data structures. attoparsec and text went together for parsing the input files. linear was used to represent points, as quite a few problems were about places in a grid.

I can do a similar analysis of the modules imported into the programs. There are many more of them.

Showing that graphically gives a similar picture. Data.Attoparsec.Text and Data.Text are used in many programs. Data.List brings in some useful tools for handling lists. Monads are used rarely.

None of the packages and modules are "exotic": there's no use of rings or groups, no constraint solvers, no uses of number theory.

Programming concepts

The pattern of use of libraries reinforces my impression that again, Advent of Code doesn't require advanced programming skills, but did reward having some additional concepts on hand.

• I used were zippers in day 18 (to move around a data structure)
• I treated coordinate transforms as a monoid in day 19 (which allowed convenient ways of combining those transfroms).
• Sweep algorithms were new to me in day 22.

Apart from those, most of the concepts should be clear to most decent programmers. And that's a good thing for a programming challenge aimed at all comers!

Code

You can get the code from my locally-hosed Git repo, or from Gitlab.