Advent of Code 2023. Share your solutions

#1

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.

3 Likes
#2

Which day is this solution for?
Day 1

Link to your solution?
day-1.hs

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 :smile:

#3

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 :smile:

Yeah… Behold my “”“parser”""

Parser 
txtParser :: String -> [Int]
txtParser [] = [] 
txtParser ('o':'n':'e'        :r) = 1 : txtParser ('e':r)
txtParser ('t':'w':'o'        :r) = 2 : txtParser ('o':r)
txtParser ('t':'h':'r':'e':'e':r) = 3 : txtParser ('e':r)
txtParser ('f':'o':'u':'r'    :r) = 4 : txtParser r
txtParser ('f':'i':'v':'e'    :r) = 5 : txtParser ('e':r)
txtParser ('s':'i':'x'        :r) = 6 : txtParser r
txtParser ('s':'e':'v':'e':'n':r) = 7 : txtParser ('n':r)
txtParser ('e':'i':'g':'h':'t':r) = 8 : txtParser ('t':r)
txtParser ('n':'i':'n':'e'    :r) = 9 : txtParser ('e':r)
txtParser (c:r )
  | isNumber c = read (pure c) : txtParser r
  | otherwise  = txtParser r

Why be fancy when simple do trick?

3 Likes
#4

Which day is this solution for?
Day 1

Link to your solution?
Solve.hs

How did you parse the input?
String manipulation

How did you implement the algorithm?
Basic string manipulation

Any comment about today’s problem?
Easy as always, just maybe harder to parse in a clean way

Was Haskell a good choice for it?
Not particularly may it helps by being a bit more concise

1 Like
#5

Day 2 - Solution

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

Had great fun today!

1 Like
#6

I love this community.

1 Like
#7

Day 3 is hard… Has any one come to a solution to be proud of? Mine, so far is nasty.

#8

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.

https://paste.sr.ht/~probie/fa52876a073950bc218c020f4e3f6fa0bec3d921

1 Like
#9

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?

#10

bss is on lemmy/kbin: https://infosec.pub/u/bss03

(but not posting aoc as far as I can tell)

1 Like
#11

Bruteforce on day 5 part 2 :grinning_face_with_smiling_eyes:. It worked in around 10 minutes, even with sequential execution.

#12

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 :slight_smile:

1 Like
#13

Day 4 - Solution

By now, I have done 4-5 variations of this.

  • 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).

Great fun!

2 Likes
#14

Day 7 was nice in Haskell, the default Ord instance of Tuples made the two level sort a breeze.

1 Like
#15

While working on day7, I discovered that Ordering has a Semigroup instance that returns the first non-Eq result, which is also nice!

3 Likes
#16

… 0_o

…yeah, alright - so ST isn’t directly tied to the concept of state transformers; it’s merely implied. Having said that:

…which also describes the monadic State type - it’s probably best to avoid conflating the two, particularly as there’s nothing analogous to:

runST :: (forall s . ST s a) -> a

…for State expressions.

#17

This is where I’d TILed - the haddock for Control.Monad.ST:

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.

1 Like
#18

Which day is this solution for?
Day 12

Link to your solution?
Day 12 on GitHub

How did you parse the input?
String manipulation

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.

#19

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.

#20

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.

3 Likes