Advent of Code 2020, Day 7
By Terrana
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?
