From 36d53994f45c0412b9e811f82c6135352a8db6cb Mon Sep 17 00:00:00 2001 From: Julien Dessaux Date: Fri, 23 Jun 2023 00:27:51 +0200 Subject: Added advent of code 2020 in haskell blog article --- .../blog/haskell/advent-of-code-2020-in-haskell.md | 160 +++++++++++++++++++++ 1 file changed, 160 insertions(+) create mode 100644 content/blog/haskell/advent-of-code-2020-in-haskell.md 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 .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! -- cgit v1.2.3