Advent of Code 2020, Day 4

I've been doing Advent of Code again this year, and this time I'm using it to learn Haskell. You can see my adventures with the first three days over in this thread on fedi, but my day 4 writeup ran a bit long, so I'm posting here instead.

If you're doing Advent of Code yourself this year, then be aware that this post contains a detailed discussion of my solution to day 4, so consider this your spoiler warning.

My solution here: https://git.ninetailed.net/terrana/advent-of-code/src/branch/master/2020/day04/

First of all, I just want to say I love the premise behind this one, the puzzle aside. "This line is taking ages. I'm going to hack their system to still work properly but do it better to speed it up." To borrow a popular fediverse idiom, that's strong white hat energy.

After that, we get into some heavier string processing than has shown up so far this year. The input is a set of sets of key:value pairs. Individual sets of pairs are separated with either spaces or new lines, while the groups are separated by a blank line.

All my string processing in Haskell so far has been character-by-character, which is easy enough because Haskell treats strings as lists of characters. Looking for a specific pair of characters that appear together, however, is a bit harder. There's a library that can do this for you easily enough, but I wanted to roll my own, because... well, that's just what I'm like. Learn more this way, have more fun.

To do that, I had to learn about guards. This is a second level of pattern matching in Haskell's function definitions that let you specify a predicate for which branch to go down. In a procedural language, this would be a set of if-else blocks. Here, it's baked into the definition of the function itself.

Isn't that neat? That set of definitions handles four distinct cases, which combine to, as the comment says, split a string across the first double newline it finds. For an empty string, it just spits out two empty strings, easy enough.

For a string at least 2 characters long, if the first two are newlines, it spits out an empty string and the rest of the original string after those two newlines. That sounds like it'd only work if the newlines are at the very start, but bear with me.

If those first two characters aren't newlines, then it gets recursive. It chops the first character off the original string, feeds the rest back into itself, then sticks the first character on the front of the result. Sticking something on the front of a list is very cheap and efficient in Haskell, so what it does here is effectively jump ahead to where it finds its pattern, then rebuild the first part of the string character by character until it has the two chunks again.

That last case? Just a special handler for when it reaches the end of the string with no match. Then it just spits out the entire original string in the first part, and nothing in the second.

Wow. That was actually harder to explain than it was to write in the first place.

From there, we have to check that seven required fields are present in a given set (my solution would break if there were duplicate keys, but there aren't any in the test data), and that each of those has a valid value according to a set of rules.

Most of those were easy enough. Check if a number is in a given range, check if the value is all hex digits, and so on. Only one really gave me much trouble, and that was a height field, which could be specified in inches or cm, with the unit as a suffix, and the number having a different allowable range for each unit.

That might have been really hard... except I already taught myself how to look for a specific two-character sequence in a string and split on that earlier. So that actually paid off!