# Advent of Code 2023. Share your solutions

**URL:** <https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246>\
**Category:** Uncategorized\
**Created:** [December 1, 2023, 6:56pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246 "2023-12-01T18:56:08Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lsmor](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lsmor/32/3302_2.png) [@Lsmor](https://discourse.haskell.org/u/Lsmor)\
**Post date:** [December 1, 2023, 6:56pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/1 "2023-12-01T18:56:08Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Lsmor](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lsmor/32/3302_2.png) [@Lsmor](https://discourse.haskell.org/u/Lsmor)\
**Post date:** [December 1, 2023, 7:03pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/2 "2023-12-01T19:03:48Z")

</div>

**Which day is this solution for?**  
Day 1

**Link to your solution?**  
[day-1.hs](https://github.com/lsmor/AoC-2023/blob/main/solutions/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 😄

---

<div class="post-metadata">

**Author:** ![haanss](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/haanss/32/3690_2.png) [@haanss](https://discourse.haskell.org/u/haanss)\
**Post date:** [December 1, 2023, 7:09pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/3 "2023-12-01T19:09:42Z")

</div>

> 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 😄

Yeah… Behold my “”“parser”“”

> **Parser**
>
> ```haskell
> 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?

---

<div class="post-metadata">

**Author:** ![AlecsFerra](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/alecsferra/32/3896_2.png) [@AlecsFerra](https://discourse.haskell.org/u/AlecsFerra)\
**Post date:** [December 1, 2023, 7:35pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/4 "2023-12-01T19:35:12Z")

</div>

**Which day is this solution for?**  
Day 1

**Link to your solution?**  
[Solve.hs](https://github.com/AlecsFerra/AoC23/blob/master/day01/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

---

<div class="post-metadata">

**Author:** ![mnvr](https://avatars.discourse-cdn.com/v4/letter/m/839c29/32.png) [@mnvr](https://discourse.haskell.org/u/mnvr)\
**Post date:** [December 3, 2023, 3:36am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/5 "2023-12-03T03:36:58Z")

</div>

[Day 2 - Solution](https://github.com/mnvr/advent-of-code-2023/blob/main/02.hs)

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

```haskell
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!

---

<div class="post-metadata">

**Author:** ![nemo](https://avatars.discourse-cdn.com/v4/letter/n/f07891/32.png) [@nemo](https://discourse.haskell.org/u/nemo)\
**Post date:** [December 3, 2023, 7:50pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/6 "2023-12-03T19:50:28Z")

</div>

> [@haanss](#):
>
> Yeah… Behold my “”“parser”“”

I love this community.

---

<div class="post-metadata">

**Author:** ![Lsmor](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/lsmor/32/3302_2.png) [@Lsmor](https://discourse.haskell.org/u/Lsmor)\
**Post date:** [December 3, 2023, 9:36pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/7 "2023-12-03T21:36:58Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Probie](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/probie/32/3232_2.png) [@Probie](https://discourse.haskell.org/u/Probie)\
**Post date:** [December 4, 2023, 3:24am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/8 "2023-12-04T03:24:12Z")

</div>

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](https://paste.sr.ht/~probie/fa52876a073950bc218c020f4e3f6fa0bec3d921)

---

<div class="post-metadata">

**Author:** ![ajbarber](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ajbarber/32/2648_2.png) [@ajbarber](https://discourse.haskell.org/u/ajbarber)\
**Post date:** [December 4, 2023, 4:36pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/9 "2023-12-04T16:36:17Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [December 4, 2023, 5:27pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/10 "2023-12-04T17:27:43Z")

</div>

bss is on lemmy/kbin: [https://infosec.pub/u/bss03](https://infosec.pub/u/bss03)

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

---

<div class="post-metadata">

**Author:** ![dschrempf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/dschrempf/32/1933_2.png) [@dschrempf](https://discourse.haskell.org/u/dschrempf)\
**Post date:** [December 5, 2023, 12:03pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/11 "2023-12-05T12:03:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![AlecsFerra](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/alecsferra/32/3896_2.png) [@AlecsFerra](https://discourse.haskell.org/u/AlecsFerra)\
**Post date:** [December 5, 2023, 6:05pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/12 "2023-12-05T18:05:07Z")

</div>

Day5: [Solve.hs](https://github.com/AlecsFerra/AoC23/blob/master/day05/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 🙂

---

<div class="post-metadata">

**Author:** ![mnvr](https://avatars.discourse-cdn.com/v4/letter/m/839c29/32.png) [@mnvr](https://discourse.haskell.org/u/mnvr)\
**Post date:** [December 7, 2023, 10:48am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/13 "2023-12-07T10:48:06Z")

</div>

[Day 4 - Solution](https://github.com/mnvr/advent-of-code-2023/blob/main/04.hs)

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](https://github.com/mnvr/advent-of-code-2023/blob/main/04.memo-manual.hs))

- 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](https://mrmr.io/memoization-in-haskell) 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](https://github.com/mnvr/advent-of-code-2023/blob/main/04.memo-map.hs), 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](https://github.com/mnvr/advent-of-code-2023/blob/main/04.memo-array.hs), and [one using the ST monad](https://github.com/mnvr/advent-of-code-2023/blob/main/04.memo-st.hs) (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](https://github.com/mnvr/advent-of-code-2023/blob/main/04.hs):

```haskell
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!

---

<div class="post-metadata">

**Author:** ![ajbarber](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ajbarber/32/2648_2.png) [@ajbarber](https://discourse.haskell.org/u/ajbarber)\
**Post date:** [December 8, 2023, 8:05am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/14 "2023-12-08T08:05:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![chreekat](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/chreekat/32/2669_2.png) [@chreekat](https://discourse.haskell.org/u/chreekat)\
**Post date:** [December 8, 2023, 8:46am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/15 "2023-12-08T08:46:02Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![atravers](https://avatars.discourse-cdn.com/v4/letter/a/45deac/32.png) [@atravers](https://discourse.haskell.org/u/atravers)\
**Post date:** [December 8, 2023, 9:13am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/16 "2023-12-08T09:13:14Z")

</div>

> [@mnvr](#):
>
> TIL: ST stands for “State Thread”

… 0\_o

> [@](#):
>
> (page 3 of 51)
> 
> **2.1 State transformers** …
> 
> A _state transformer_ of type `(ST s a)` is a computation which transforms a state indexed by type `s`, and delivers a value of type `a`.
> 
> [State in Haskell](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.3656&rep=rep1&type=pdf) (1995)

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

> [@](#):
>
> You can think of it as a pure function, taking a state as its argument, and delivering a state and a value as its result.

…which also describes the monadic [`State`](https://hackage.haskell.org/package/transformers/docs/Control-Monad-Trans-State.html) 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.

---

<div class="post-metadata">

**Author:** ![mnvr](https://avatars.discourse-cdn.com/v4/letter/m/839c29/32.png) [@mnvr](https://discourse.haskell.org/u/mnvr)\
**Post date:** [December 8, 2023, 3:27pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/17 "2023-12-08T15:27:10Z")

</div>

This is where I’d TILed - the haddock for [Control.Monad.ST](https://hackage.haskell.org/package/base-4.16.3.0/docs/Control-Monad-ST.html):

> 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`.

---

<div class="post-metadata">

**Author:** ![omeldar](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/omeldar/32/3928_2.png) [@omeldar](https://discourse.haskell.org/u/omeldar)\
**Post date:** [December 13, 2023, 2:44pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/18 "2023-12-13T14:44:44Z")

</div>

Which day is this solution for?  
Day 12

Link to your solution?  
[Day 12 on GitHub](https://github.com/omeldar/adventofcode/blob/main/2023/haskell/day12.hs)

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.

---

<div class="post-metadata">

**Author:** ![rhendric](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/rhendric/32/2689_2.png) [@rhendric](https://discourse.haskell.org/u/rhendric)\
**Post date:** [December 13, 2023, 10:17pm UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/19 "2023-12-13T22:17:26Z")

</div>

> [@omeldar](#):
>
> 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`](https://hackage.haskell.org/package/array-0.5.6.0/docs/Data-Array.html#t: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.

---

<div class="post-metadata">

**Author:** ![glguy](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/glguy/32/3359_2.png) [@glguy](https://discourse.haskell.org/u/glguy)\
**Post date:** [December 14, 2023, 3:52am UTC](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246/20 "2023-12-14T03:52:52Z")

</div>

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.

> <https://github.com/glguy/advent/tree/main/solutions/src/2023>
>
> //github.com/glguy/advent/tree/main/solutions/src/2023

[Next page](https://discourse.haskell.org/t/advent-of-code-2023-share-your-solutions/8246.md?page=2)