Advent of code 2021: Day 10
- 4 minutes read - 835 wordsDay 10 of Advent of Code 2021 was all about mismatched brackets. And I think Haskell did rather well on this as I found the expressiveness arrived at a really concise solution. We’re still in our Advent submarine and after mapping the floor on Day 9, we now discover lots of syntax errors in the submarine navigation system.
The problem
This puzzle was all about matching brackets, the input was like this:
[({(<(())[]>[[{[]{<()<>>
[(()[<>])]({[<{<<[]>>(
{([(<{}[<>[]}>{[]{[(<()>
(((({<>}<{<{<>}{[]{[]{}
And the task was to find mismatching brackets. So []
is valid, as is [<>{()}]
, but
[(}
is not.
More on the problem here
First task
My first thought was that this wanted a stack to add open brackets onto, and then match and remove them again for closing brackets and then processing each of the brackets. Having done a few of the Advent puzzles in Haskell now, to me this meant a recursive call to process the string of bracket characters individually.
But before I get to that, I’d like to take a detour about one of the neat things in Haskell, which is the idea of pattern matching functions. For example, one of the tasks was to score the mismatching brackets, and rather than an if-else or a switch-case statement, you can just pattern match like so:
|
|
This means that when the score
function is called with a )
it returns 3
, ‘]’ returns 57
etc.
Then I thought, I can use pattern matching to match the opening with closing brackets:
|
|
I’m using a String
as a stack (in Haskell a String
is just a list of characters) and use two lists.
The first list contains the input to process, the second list is the stack. When there’s an opening
bracket, it just puts it on the stack (cons ('(':ss
) adds the element at the front of the list) and when
I encounter a closing bracket, I try to match it with the top of the stack. If that fails (and there still is
input, then I return a Just c
to indicate what’s causing the error). The last line refers to when the input
list is empty (i.e. all the input has processed).
Once I had that Maybe Char
back, I could iterate over all the inputs and return the score:
|
|
The [c | Just c <- corruptChar]
is a list comprehension that filters out all the Nothing
. I’ve
since discovered that this could be done a bit neater via:
|
|
Second task
For the second part of the puzzle, instead of returning corrupt entries, the task was to finish the
incomplete ones. As it turned out, having the stack of brackets just was what was missing, so after
a slight adjustment to the scoring function and returning the remaining stack instead of a Maybe Char
made this easy:
|
|
For getting the final score, the instructions were a bit convoluted:
- multiply each previous score by 5 before adding the next one
- sort all the score
- take the mean
I was surprised that there was no mean
function in Haskell out of the box, but to be fair
it was easy enough to define:
|
|
Doing the calculation was a simple fold:
|
|
And then it was just a matter of sorting and applying functions:
|
|
(I also filtered out the invalid scores, which originated from an empty string ""
)
Rest of the solution on GitHub
Conclusion
I thought that applying pattern matching made for quite a neat and concise way of describing the issue. It’s this expressiveness that I really appreciate!
Tags functional haskell advent-of-codeIf you'd like to find more of my writing, why not follow me on Twitter or Mastodon?