Learnings from Solving Advent of Code 2020 in Haskell

After many years of trying unsuccessfully, I finally completed all 25 days of the Advent of Code 2020 in Haskell. Here is a summary of my learnings and solutions.

Learnings

• GHCi is a powerful REPL. We can do almost anything in it which we can do in a file. It is also fast and great to play with code.
• Zippers are an awesome technique to move around in a data structure. We can also think of them as focus points in spaces like lines, plains or 3D volumes. Many AoC problems are about moving around in space, doing things at the focus points. Zippers are quite suitable for such problems.
• Data.List.Split module is good enough for basic input parsing.
• It is trivially easy to write a simple but feature-rich parser framework in Haskell. Here is one in its entirety, with some example parsers, in just 24 lines.
• Data.Graph.Wrapper is a useful wrapper over Data.Graph.
• Haskell is good for writing interpreters.
• Graph traversal + Memoization = Dynamic programming.
• Use Data.Memotrie for side-effect-free memoization in Haskell.
• Sometimes it’s faster to recompute than to memoize because of the lazy nature of Haskell and the extra memory usage caused by memoization.
• Comonads are great to simulate Cellular automata. Zippers are comonads.
• Comonad based cellular automata do not mutate the state of the automata universe, neither do they compute and materialize the whole universe at every step of the automata. Rather, they just stack functions over functions to create new lazy views over the original universe. This means that we can have lazy infinite universes. This also means that simulating cellular automata using comonads tends to get slower with increasing number of neighbours/dimensions.
• Sometimes mutability is the only option if we want to implement a fast algorithm. Mutable vectors from the vector library are great for this.
• Writing the four-dimensional zipper comonad from scratch is complex and takes a really long time.
• There are no words similar to horizontal and vertical for three dimensions or more.
• ReadP is a good, minimal and easy to use parser framework which is included in the Haskell standard library.
• Try to use Bit arrays when they fit, for performant solutions.
• Some problems, when scaled up, cannot be solved with lazy lists in a reasonable time.
• We can simulate a linked list of integers over a vector.
• If a program generates a lot of garbage, turning on multithreading (-threaded) and parallel garbage collection (-qg0 -N) may make it run faster.
• Tweaking the heap size (-H) and the allocation area size (-A) may make a program run faster.
• Use the Strict extension cautiously. Sometimes it may unexpectedly make a program run slower.
• Hexagons are the bestagons.

Solutions

Here’s the index of all the solutions I wrote for AoC 2020:

Problem Solution Salient points Libraries/modules used 1 ↗ List comprehensions None 2 ↗ Validation None 3 ↗ Zippers None 4 ↗ Validation split 5 ↗ Decoding None 6 ↗ None None 7 ↗ Parsing, graphs mtl, graph-wrapper 8 ↗ Parsing, interpreter mtl 9 ↗ None None 10 ↗ Graphs, memoization None 11 ↗ Cellular automata, zippers comonad, Data.Sequence 12 ↗ Geometry None 13 ↗ Number theory None 14 ↗ Parsing, interpreter mtl 15 ↗ Number sequence Data.Vector.Unboxed.Mutable 16 ↗ Parsing, constraint satisfaction mtl 17 ↗ Cellular automata, zippers comonad, Data.List 18 ↗ Parsing, interpreter mtl 19 ↗ Parsing ReadP 20 ↗ Image manipulation Data.Array.BitArray 21 ↗ Parsing, constraint satisfaction ReadP 22 ↗ Recursion, game None 23 ↗ Linked list, game Data.Vector.Primitive.Mutable 24 ↗ Parsing, cellular automata ReadP, Map 25 ↗ Cryptography None Powered by Precis abhinavsarkar.net