Added advent of code 2020 in haskell blog article

1 files changed, 160 insertions, 0 deletions

diff --git a/content/blog/haskell/advent-of-code-2020-in-haskell.md b/content/blog/haskell/advent-of-code-2020-in-haskell.md
new file mode 100644
index 0000000..0365a58
--- /dev/null
+++ b/content/blog/haskell/advent-of-code-2020-in-haskell.md
@@ -0,0 +1,160 @@
+---
+title: Advent of code 2020 in haskell
+description: My patterns for solving advent of code puzzles
+date: 2023-06-22
+tags:
+- haskell
+---
+
+## Introduction
+
+I did the [advent of code 2020](https://adventofcode.com/2020/) in haskell, I had a great time! I did it following [advent of code 2022 in zig]({{< ref "advent-of-code-2022-in-zig.md" >}}), while reading [Haskell Programming From First Principles]({{< ref "haskell-programming-from-first-principles.md" >}}) 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:
+```sh
+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:
+```haskell
+-- 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:
+```haskell
+-- 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!