If you are doing AoC this year, feel free to share your solutions here. I’d suggest to follow a little style questionary in order to keep information as clean as posible, so readers can easily find different approaches and solutions.
Given that an AoC day tipically consists in two parts each with a parsing phase an algorithmic phase
Questionary:
Which day is this solution for?
day XYZ
Link to your solution?
link here
How did you parse the input?
example: parsec-like library / String manipulation / dedicated library like aeson / no parsing, just build the solution as reading the string
How did you implement the algorithm?
examples: dedicated library like search-algorithms / Using the XXX Monad / manual implementation
Any comment about today’s problem? Was Haskell a good choice for it?
This is a more open question.
How did you parse the input?
Pure (byte)string manipulation. I just calculate the result folding/mapping the input
How did you implement the algorithm?
in Part 1 I just use bytestring and Char functions
in Part 2 I use a Data.Trie from bytestring-trie library. Makes the solution 4-lines long. Very convenient.
Any comment about today’s problem?
wasn’t it more difficult than other years? Day one, use to be very easy.
Was Haskell a good choice for it?
Part 1 is very easy and is just a few string transformations
I thougth Part 2 wouldn’t be a good fit because I was thinking an imperative approach. The I realise a trie would make the problem very easy… Now I think a simple pattern matching is probably a super easy and efective approach
I thougth Part 2 wouldn’t be a good fit because I was thinking an imperative approach. The I realise a trie would make the problem very easy… Now I think a simple pattern matching is probably a super easy and efective approach
I parsed this using Parsec. Then merged the individual draws using a Monoid instance that kept the maximum of a particular color seen so far in that game.
This day was quite great, because of how simple the conceptual thinking about a draw as a Monoid made the problem so fun for me. It maybe even made the code a bit nicer etc too of course, but I’m speaking more of how once we have a (Monoidal) hammer, everything looks like a (instance) nail.
Another nice part for me was that initially, I’d started with a Monoid instance that summed the corresponding colors - I’d used this to chain the RGB tuple during parsing when using the chainl combinator. Then, for the actual problem itself, I needed another binary operator, one that kept the maximum of the corresponding colors.
This felt unsatisfying - to have two binary operators around. But later I found that we don’t actually need to keep the full list of draws, the maximal one will do! So I was able to do everything with just one monoid instance
data Draw = Draw { red :: Int, green :: Int, blue :: Int }
instance Semigroup Draw where
(Draw a b c) <> (Draw x y z) = Draw (max a x) (max b y) (max c z)
instance Monoid Draw where
mempty = Draw 0 0 0
I’m not exactly proud of my solution to day 3, but I wouldn’t say it’s nasty (the method used is my original solution, but this has been cleaned slightly before posting). For extra time-wasting, I’m trying to stay entirely within base, so no containers.
I’m missing bss and Tarmean and others on reddit this year. Where did they all go to? I know about the whole reddit saga, just curious if there was an exodus of all the Advent of Code posters to some other platform?
Day5: Solve.hs
Not proud of this spaghetti-code but at least my solution is general enough to solve both the parts with a single function, open to suggestions
I came up with an okay-ish solution with hand-coded memoization for the recursive part 2 initially (Link)
Then I abstracted out the memoization using the State monad. When doing this, I ended up also writing a short tutorial, might be trivial stuff for most of you, but I wrote it from the angle of the State monad tutorial that I wished I’d seen when I was trying to first say hello to it. Anyways, the solution is similar to the hand-coded one in both speed etc, but doesn’t obfuscate the actual recursion with the details of the memoization. Here’s a link, but I’m still not happy with it. The abstraction of the memoization is not as transparent as I wished. I remember seeing some old stack overflow answers from Edward Kmett at some point that explained less intrusive generic memoization scheme, and I’ll try to look them up and understand them once I get some time.
I created two variations of this then - one using arrays, and one using the ST monad (TIL: ST stands for “State Thread”). I was hoping for some magical performance jumps, but nothing spectacular was acheived. That said, I’m just benchmarking using the standard time command and using the -O or -O2, and not even doing it very scientifically, so this is not a conclusive statement.
Meanwhile, in parallel, I’d re-done the problem in AWK and shell (the insight was that I should iterate over the input lines in the reverse direction), and had realized that I don’t need recursion or memoization. So then I rewrote a straightforward version of it in Haskell, with foldr serving the same role as reversal. This is what I ended up with:
type Card = ([String], [String])
parseCards :: String -> [Card]
parseCards = map (bimap tail tail . span (/= "|") . tail . words) . lines
p1 :: [Card] -> Int
p1 = sum . map points
matches :: Card -> Int
matches = length . uncurry intersect
points :: Card -> Int
points card = case matches card of 0 -> 0; n -> 2 ^ (n - 1)
p2 :: [Card] -> Int
p2 = sum . map (+1) . foldr f [] where
f card wins = w : wins where
m = matches card
w = m + sum (take m wins)
The code is nicer to read and understand, and it runs blazing fast (under 0.01s, the lowest threshold for time, when run in -O2). I guess it shows that no amount of language wizardry overcomes a sub-optimal approach (I mean, we already know that, just that I was trying to end this post on some sort of conclusion assuming you’ve read all the way through).
This library provides support for strict state threads, as described in the PLDI '94 paper by John Launchbury and Simon Peyton Jones Lazy Functional State Threads .
…
A computation of type ST s a returns a value of type a, and execute in “thread” s.
How did you implement the algorithm?
manual implementation
Any comment about today’s problem? Was Haskell a good choice for it?
I’m pretty new to Haskell. I actually just started with this years advent of code. And I know this solution isn’t really a clean one (especially the calcNewPerm function). I’m open to feedback. If you have any tipps and tricks feel free to tell me. And btw I know: The solution is really slow, and no, I do not know why yet.
My guess after a quick review: every time you call snd on the result of f, you’re throwing away the new DPMap value that f computed, so it can’t be reused. You’re therefore not really getting the benefit of memoization.
Advice: try using a lazy map (or an Array, which would be somewhat more appropriate) and define a single value of DPMap as the first thing you do for each input, using that single variable as a constant in the rest of your functions instead of returning modified maps. In a lazy map, values can refer to the entire map itself, because they’ll be thunks until they’re forced.
This is not the only way to solve the problem in Haskell; it isn’t even necessarily the most ‘Haskelly’ way. But it’s a really good opportunity to get familiar with a technique that is different from the patterns you’re likely to encounter in strict languages, and is very much worth your time as a Haskell learner.
I can start doing a break down of my solutions, but as far as getting caught up I keep all my solutions in GitHub and I try to keep them cleaned up and lightly commented.
So far this year I’ve only had to import basic container types from array and containers. I try my best to rely on simple stuff first before pulling in extra libraries.
I’m a big fan of using doctest to incorporate my expected outputs and the provided examples into my source files to ensure that I don’t break them as I fiddle with them.
When it comes to the day of I really appreciate having ghcid open. It has a -r flag that runs my solution every time I save. This is great for quickly observing the impacts of my changes and seeing updated error messages as I try to finish quickly.