Hacker News Reader

Comment by Mathiciann | Hacker News Reader

I know the author was only trying to show some benefits of FP but choosing such a trivial example gives a bit of a one-sided view of FP. Try solving the harder AoC problems and you will probably need mutable state (at least I do). Also I am not sure if for example recursion is always the best option when performance becomes a factor.

View on HN

YMMV but each year I use Haskell to solve AoC and I've never needed mutation or any particularly intensive `IO/State` Monad trickery to get any day completed regardless of how far into the challenge it goes.

Part of the charm of purely functional solutions for me (and why I'm hooked) is that it forces you to think about the representation of the data that you would need in order to have a "clean" solution without mutation. E.g. IntMap for index of arrays and folding with Set/Map operations to build state without accruing algorithmic complexity. I've found that I do a lot more "deep thinking" when forced into using (or creating) the right data-structures and this is something I enjoy a lot more than purely iterative debugging/hacking, and it's more satisfying (to me) at the end of it all.

My go-to for AoC is almost always Attoparsec + Containers with a recursive "solve" function and the complexity seemingly always stays manageable. I'm no savant but feel free to give examples of a tricky task to solve functionally I can share a specific solution.

I suspected my novice-ness could be the reason. Still, I could probably solve them without mutable state but I wasnt satisfied with the readability of my code. For example day 12 day 13 were a mess for me when trying for purely functional.

Would love to see your solution for one of these problems!

Day 12 was a little hacky because of my foolhardy reluctance to ever use the obvious Dijkstra's Algorithm solution and always rolling my own organic recursive "flood fill" on the fly instead.

    -- ((start, end), heightMap)
    type Input = ((Coordinate, Coordinate), BoundedHeightMap)

    -- (length remaining, next coordinate)
    type DirectionsMap = M.Map Coordinate (Int, Coordinate)

I built up a map of "where to go next and how far left" and flood-filled it starting from the end and calculating for neighbours of those that just changed value for each step until convergence, which ended up being super useful for Part 2 since I got it "for free":

https://github.com/cronin101/AdventOfCode/blob/master/2022/D...

Day 13 on the other hand is something I'm far less ashamed of and really lets Haskell shine, it basically didn't need any code at all. I just defined how to parse an equivalent data representation, how it was sorted via Eq/Ord typeclass (following the brief), and used `compare` to do the lifting.

    instance Eq PacketData where
      (L l) == (P p) = P [L l] == P p
      (P p) == (L l) = L l == P p
      P p == P p' = p == p'
      L l == L l' = l == l'

    instance Ord PacketData where
      compare (L l) (P p) = compare (P [L l]) (P p)
      compare (P p) (L l) = compare (P p) (P [L l])
      compare (P p) (P p') = compare p p'
      compare (L l) (L l') = compare l l'

https://github.com/cronin101/AdventOfCode/blob/master/2022/D...

Thanks for sharing! Especially day 13 is really compact and elegant. Do I understand correctly that you define parser combinators to parse the packages? (I'm not really familiar with Haskell nor parser combinators)

For me the parsing was the hardest part when trying without mutable state so this helps a lot.

Yup! Parser combinators are incredibly useful once you learn the basics well. They compose predictably and you can test the individual parts pretty succinctly (I usually use an inline eval'd comment in vscode to smoke test, as you can see) and allow you to build an arbitrarily complicated data structure at parse time.

I'll admit first few times were a bit of a headache learning the library (https://hackage.haskell.org/package/attoparsec-0.14.4/docs/D...) and idiomatic patterns, plus how to test/troubleshoot. But now Haskell is my go-to language for parsing and I can parse pretty much any AoC input into a suitable representation, with the forethought taking no longer than reading the brief, by composing parsers for the different parts of the input string into a larger parser.

Also, disclaimer, since I'm the only one reading my code I often make oneliner "pointfree" parsers using dense syntax/tricks (as a little extra mental puzzle) instead of vastly more readable "do notation", so don't let the special character soup put you off.

I solved the first 13 days mostly in functional ways [1]. The 2 not functional things I used were arrays and hash tables. OK and outputting things ... .

For arrays I wrote a functional map function, since my language did not have a functional one and I only used it for transforming input, while preserving the original input under a different binding.

For hash tables I could have used functional sets, which I only bothered with in later puzzles, because I wanted to parallelize things.

I did parallelize quite a few things in later puzzles, just because it is so easy to do when you have pure functions.

So at least 26 of 50 puzzles are perfectly possible in functional style.

[1]: https://notabug.org/ZelphirKaltstahl/advent-of-code-2022

Reply on news.ycombinator.com