1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
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!
|
