Advent of code 2020 in haskell
2023-06-22 - My patterns for solving advent of code puzzles
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
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!
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
I had no memory problems and laziness was not an issue either. Haskell really is a fantastic language.
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
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
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!