Categories
Advent of Code

Advent of Code 2020, Day 8

I liked day 8. It made me feel clever when I worked it out. Spoilers follow as usual, and my solution is here.

There are a few classes of puzzle that show up time and time again in Advent of Code. One of these is the virtual machine puzzle. That’s where it gives you some computer code, and the task is to make something that can run it.

Remember I mentioned Intcode from 2019? That was a virtual machine puzzle writ large. It was built up over multiple puzzle-days and ended up as a fully functional computer, capable of performing any computation and even able to talk to external hardware. It was a masterpiece of puzzle design.

This is not that complicated. Today, we’ve got a simple instruction set. There are three things our hypothetical computer can do: add a number to another number, jump forward or backward in its instruction list, or just do nothing and move on to the next step. It’s not really a proper computer, just a slightly convoluted adding machine.

(Maybe I should go into exactly what a universal computer and Turing-completeness mean some time. Be a fun writing exercise.)

Something this simple wouldn’t take me long at all in a language I already know, but as previously established, I’ve been learning Haskell this year. Haskell is a pure functional programming language. What this means is it doesn’t follow step-by-step instructions like another language like C or Python would. It feeds the results of various functions into each other in a long pipeline. This makes having it pretend to be a step-by-step computer… challenging.

A challenge I greatly enjoyed.

The thing with a pure functional programming language is that it doesn’t really have state. If you run the same function with the same inputs twice, you will get the same output both times, always. There are two ways around this.

The first of these you’ve already seen me use. It’s recursion – the function calls itself for the next step with slightly different input. That would have worked here, because the pretend adding machine only keeps track of two numbers internally – the results of its adding, and the instruction number it’s on. It’d be pretty easy to keep passing those to the next step.

That is insufficiently needlessly elaborate.

The second way, which is what I actually did, is to use something called a monad. It’s a way for a functional language like Haskell to pretend to have state. Behind the scenes, it’s still doing recursion for you. It’s just easier to write. My friend Emi did an excellent introduction to the topic on their own site, and I heartily encourage you to have a read.

To summarise: when working with monads, you have actions instead of functions. Those take the existing state, do something with it, and give back the resulting changed state. You step through various actions not unlike how you would in an imperative programming language.

Definitely hit a few pitfalls on the way, though! This is a new way of working in Haskell, with its own syntax and rules that are slightly different from non-monadic stuff.

I fell into the trap of thinking the return function does the same thing a return does in an imperative language – drops you out of the function with the value you give it. Nope, nope, nope, it’s just badly named. What it actually does is give you an action that will always produce the value you give it, regardless of the current state.

Categories
Advent of Code

Advent of Code 2020, Day 7

Day 7 was a bit more challenging than the last couple. As usual, spoilers for day 7 follow.

This time around, the subject of our airline-based adventures was the baggage restrictions. Each bag is given a certain colour coding, and must contain a selection of bags of other colour codings based on a simple set of rules. The rules are a mere six hundred lines long, so not that different from real baggage restrictions.

Two parts to it. For the first part, we have to work out which other bags can contain our bag (coded “shiny gold”) either directly or indirectly. For the second, follow the rules to their “topologically impractical” conclusion and work out how many bags our bag must contain to comply with the rules.

My solution is in the usual place.

Rather than copy-paste the common bits or do it all in one file this time, I decided to try writing my own Haskell module that the solution files could import. That’s Bag.hs in the repository.

The Bag module contains the functions for reading the ruleset from the text file it comes in and turning it into a form I can work with programmatically. It also includes the first time I’ve used a custom Haskell type. It’s defined as follows:

type Bag = (String, [(String, Int)])

If you’re not familiar with Haskell – and I’m assuming most folks reading this aren’t – what this means is that whenever I write the word Bag in a function, what I actually mean is a string paired with a list of values, each of which is a pair of a string and an integer.

This encodes rules like “drab indigo bags contain 4 pale bronze bags, 2 mirrored lavender bags.” In my Bag type, that’d look like ("drab indigo", [ ("pale bronze", 4), ("mirrored lavender", 2) ]). Much respect for anyone carrying around a pair of mirrored lavender bags, by the way.

There’s a reason I structured things this way. My solution hinges on a function called lookup which is a basic part of the Haskell language. It lets you treat a list of pairs like a dictionary – lookup “drab indigo” in the list of rules, and it’ll give you back that it has to contain pale bronze and mirrored lavender bags – the list that’s the second part of that pair.

In other languages you’d write something like rules["drab indigo"]. It’s exactly the same thing.

A bit of parsing later, with my list of rules in hand, I’m ready to actually do something with them. Weirdly, part 1 was actually harder than part 2.

Part 1 involved finding any bag that can hold “shiny gold” bags by filtering the list of rules based on whether there was a “shiny gold” part in the bag contents list. Then recursively doing the same for any bags that hold one of those and so on.

Part 2 was the same thing in reverse, more or less. Check what a shiny gold bag has to hold. Then check what those bags have to hold, and so on, until we get all the way down to bags that are empty. As it turns out, with the particular set of rules I was given, I need to bring 158730 other bags to put in my shiny gold one.

Could’ve been worse, I guess. If I had decided to be cool and bring a pair of mirrored lavender bags, I’d have needed over 22 million bags total. Ever feel like you might have overpacked a bit?

Both parts of this puzzle are complete! They provide two gold stars: **

Categories
Advent of Code

Advent of Code 2020, Day 6

Not much to write about for day 6, though the premise is again very relatable. It’s nice to help people out when you’re the only one that can make sense of a system, though I believe more in teaching them how to understand the system than doing the work for them. I’d far rather have someone say to me, “let me show you how to do it,” than, “let me do it for you.”

The puzzle was pretty simple, though, as you can see from my solution. For part 1, take several groups of answers and count how many answers in each group were given by at least one person.

So I just borrowed my dnlsplit function from day 4 to break up the groups, and took the union of all the lists in each group. From there, the answer is just the length of each list. Easy.

Part 2, it turns out that, oh no, we misread the instructions! It’s answers that everyone in the group gave, not anyone. Well, it’s a one-word change to the code, too! Instead of the union of the lists, we just take their intersection.

I should probably have done something clever to just spit out both answers in one go, but I’m sleepy today so I just copy-pasted the part 1 code to part 2. It’s not like I’ve got code quality metrics to meet, just having a bit of fun.


EDIT: Okay, so you know I said I wasn’t going to make it do both answers in one go? I made it do both answers in one go.

I changed my groups function from just finding the union or intersection as it was before to finding both and spitting them out as a two-element list. Easy enough, but now I can’t just do sum . map length to get the total number of answers any more.

What to do about that? Well, the Data.List module I was already using for union and intersection also has a function called transpose. That takes a table in the form of a two-dimensional list, like the one I just made, and flips its rows and columns.

So now, instead of a long list of sets of two answers, I’ve got two long lists of answers. That is something I can sum, just doing map (sum . map length) to apply the same calculation I was doing before to both lists of answers. That gives me the answers to both parts at once!


EDIT 2: Despite how simple today’s puzzle was, I just can’t seem to leave this one alone. After talking to Emi, I realised I could do away with that transpose by using a recursive function to just construct the two lists in one go rather than building pairs and then switching them around.

The result actually isn’t any more complicated. Have a look.

Categories
Advent of Code

Advent of Code 2020, Day 5

Curiously, day 5 was actually simpler than day 4. My solution is over on my git repo, and as always, this post contains spoilers for day 5 and earlier.

First of all, I’m continuing to love the writing introducing the problems. Let me just quote the first paragraph verbatim:

You board your plane only to discover a new problem: you dropped your boarding pass! You aren’t sure which seat is yours, and all of the flight attendants are busy with the flood of people that suddenly made it through passport control.

This is just brilliant, I think. Yep, the current issue is the obvious solution to the avoidable problem is unavailable because of the solution to the last avoidable problem. Our protagonist is actually a lot like me: forgetful, accident-prone, and tends towards the most complicated possible solution to a given problem. It’s like Eric Wastl knows his audience.

The puzzle itself wasn’t actually anything special, its introduction and framing aside. It’s a simple binary space partition, which is once again the sort of problem Haskell excels at. Read the encoded instructions character by character, and move the upper or lower bound of the search space depending on which character it is until you get one answer. Trivially easy with a recursive function.

Part 2 didn’t add much. Find the seat number that’s missing from the list. My solution to that was just to sort the list (it’s only got 800 elements or so) and look for two elements that aren’t numerically adjacent. Since I figured out how to deal with comparing two adjacent list elements yesterday, also pretty easy.

My seat’s in row 69, column 5, by the way. Come over and say hi if you’re on the flight once the seat belt lights go off.

Both parts of this puzzle are complete! They provide two gold stars: **

I’m a little disappointed that there hasn’t been some sort of ongoing thread like there was with 2019’s Intcode interpreter. Throughout the month, you were slowly building up a more and more capable interpreter for some made-up machine code, each day’s solution building on the last one. There hasn’t been anything like that here so far, and the fact that we’ve got to day 5 without seeing any sign of one isn’t promising.

I’m also starting to feel like using Haskell for Advent of Code might be cheating a bit. It seems perfectly geared towards exactly the sorts of puzzles that have been coming up… though just watch when day 19 comes along, the really hard puzzles kick in, and I have to eat those words.

Categories
Advent of Code

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.

-- Split a string into two across the first double newline found
dlfsplitonce :: String -> (String, String)
dlfsplitonce [] = ([], [])
dlfsplitonce (ca:cb:rest)
    | ca == '\n' && cb == '\n' = ([], rest)
    | otherwise                = (ca:before, after)
        where (before, after) = dlfsplitonce (cb : rest)
dlfsplitonce c = (c, [])

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!

Both parts of this puzzle are complete! They provide two gold stars: **