Advent of code 2020 in haskell

2023-06-22 - My patterns for solving advent of code puzzles
Tag: haskell

Introduction

I did the advent of code 2020 in haskell, I had a great time! I did it following advent of code 2022 in zig, while reading Haskell Programming From First Principles a few months ago.

Haskell for puzzles

Parsing

I used megaparsec extensively, it felt like a cheat code to be able to process the input so easily! This holds especially true for day 4 where you need to parse something like:

ecl:gry pid:860033327 eyr:2020 hcl:#fffffd
byr:1937 iyr:2017 cid:147 hgt:183cm

iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884
hcl:#cfa07d byr:1929

hcl:#ae17e1 iyr:2013
eyr:2024
ecl:brn pid:760753108 byr:1931
hgt:179cm

hcl:#cfa07d eyr:2025 pid:166559648
iyr:2011 ecl:brn hgt:59in

The keys can be in any order so you need to account for permutations. Furthermore, entries each have their own set of rules in order to be valid. For example a height needs to have a unit in cm on inches and be in a certain range, while colors need to start with a hash sign and be composed of 6 hexadecimal digits.

All this could be done at parsing time, haskell made this almost easy: I kid you not!

The type system

I used and abused the type system in order to have straightforward algorithms where if it compile then it works. A very notable example comes from day 25 where I used the Data.Mod library to have modulus integers enforced by the type system. That’s right, in haskell that is possible!

Performance

Only one puzzle had me reach for optimizations in order to run in less than a second. All the others ran successfully with a simple runghc <solution>.hs! For this slow one, I sped it up by reaching for:

ghc --make -O3 first.hs && time ./first

Memory

I had no memory problems and laziness was not an issue either. Haskell really is a fantastic language.

Solution Templates

Simple parsing

Not all days called for advanced parsing. Some just made me look for a concise way of doing things. Here is (spoiler alert) my solution for the first part of day 6 as an example:

-- requires cabal install --lib split Unique
module Main (main) where
import Control.Monad (void, when)
import Data.List.Split (splitOn)
import Data.List.Unique (sortUniq)
import Data.Monoid (mconcat)
import System.Exit (die)

exampleExpectedOutput = 11

parseInput :: String -> IO [String]
parseInput filename = do
  input <- readFile filename
  return $ map (sortUniq . mconcat . lines) $ splitOn "\n\n" input

compute :: [String] -> Int
compute = sum . map length

main :: IO ()
main = do
  example <- parseInput "example"
  let exampleOutput = compute example
  when  (exampleOutput /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
  input <- parseInput "input"
  print $ compute input

Advanced parsing

Here is (spoiler alert) my solution for the first part of day 24 as an example:

-- requires cabal install --lib megaparsec parser-combinators
module Main (main) where
import Control.Monad (void, when)
import Data.List qualified as L
import Data.Map qualified as M
import Data.Maybe (fromJust)
import Data.Set qualified as S
import Data.Void (Void)
import Text.Megaparsec
import Text.Megaparsec.Char
import System.Exit (die)

exampleExpectedOutput = 10

data Direction = E | W | NE | NW | SE | SW
type Directions = [Direction]
type Coordinates = (Int, Int, Int)
type Floor = M.Map Coordinates Bool
type Input = [Directions]
type Parser = Parsec Void String

parseDirection :: Parser Direction
parseDirection = (string "se" *> return SE)
  <|> (string "sw" *> return SW)
  <|> (string "ne" *> return NE)
  <|> (string "nw" *> return NW)
  <|> (char 'e' *> return E)
  <|> (char 'w' *> return W)

parseInput' :: Parser Input
parseInput' = some (some parseDirection <* optional (char '\n')) <* eof

parseInput :: String -> IO Input
parseInput filename = do
  input <- readFile filename
  case runParser parseInput' filename input of
    Left bundle -> die $ errorBundlePretty bundle
    Right input' -> return input'

compute :: Input -> Int
compute input = M.size . M.filter id $ L.foldl' compute' M.empty input
  where
    compute' :: Floor -> Directions -> Floor
    compute' floor directions = case M.lookup destination floor of
      Just f -> M.insert destination (not f) floor
      Nothing -> M.insert destination True floor
      where
        destination :: Coordinates
        destination = L.foldl' run (0, 0, 0) directions
    run :: Coordinates -> Direction -> Coordinates
    run (x, y, z) E = (x+1,y-1,z)
    run (x, y, z) W = (x-1,y+1,z)
    run (x, y, z) NE = (x+1,y,z-1)
    run (x, y, z) SW = (x-1,y,z+1)
    run (x, y, z) NW = (x,y+1,z-1)
    run (x, y, z) SE = (x,y-1,z+1)

main :: IO ()
main = do
  example <- parseInput "example"
  let exampleOutput = compute example
  when  (exampleOutput /= exampleExpectedOutput)  (die $ "example failed: got " ++ show exampleOutput ++ " instead of " ++ show exampleExpectedOutput)
  input <- parseInput "input"
  print $ compute input

Conclusion

Learning haskell is worthwhile, it is really a great language with so many qualities. Puzzle solving is a use case where it shines so bright, thanks to its excellent parsing capabilities and its incredible type system.

A great thing that should speak of haskell’s qualities is that it is the first year of advent of code that I completed all 25 days. I should revisit the years 2021 and 2022 that I did with golang and zig respectively and maybe finish those!