advent of code 2020, day 7: droste and bourkeWritten: 2020-12-07 to 2020-12-07
by Norman Liu
The previous few days of Advent have been kinda boring - day 4 was regex, then binary search, then set intersections. We’re finally back to graph traversals, and so I felt like this was worth a post.
The problem goes as follows - you’ve sledded to the airport, made it past security, boarded your plane, and gotten through customs. Now that you’re out of the North Pole and at your layover, bizarre baggage rules are only the next obstacle on your trip.
Specifically, bags must be colour-coded and must contain specific quantities of other colour-coded bags. The input consists of several hundred lines that each describe the colour of a bag, and its required contents, like
5 muted pink bags, 1 faded green bag. shiny red bags contain . faded green bags contain no other bags2 muted black bags.bright white bags contain
That’s a ton of nested bags, and it’s starting to sound like a graph theory problem. We can label each node by its colour description, and assign a weight to each edge by bag quantity. Since logically, a bag can’t contain itself, and inner bags can’t contain outer bags (forming a cycle), we can look at this as a directed acyclic graph. Part 1 seems like it’s asking a lot at first. The prompt reads, “You have a shiny gold bag. If you wanted to carry it in at least one other bag, how many different bag colors would be valid for the outermost bag?”. My first thought was just to do a topological sort of our graph, count the number of nodes that occur before shiny gold, and call it a day. There’s a logical error, though - for a given node that has a path to shiny gold, we don’t necessarily know if all of its other edges also converge to shiny gold. If we had a graph that looked like
gold| Г── green ───┘ Г──────── red ─────── blue|
blue would come before gold in sorted topological order. We’ll just have to walk the graph normally, then.
Sounds simple enough. We’ll conjure up some Haskell as usual, and model our graph as a
Strings (bag colours) to lists,
[(String, Int)], denoting other bag colours and their respective counts.
I took some time this weekend and refactored my Advent of Code repo a little bit. It makes use of the advent-of-code-api library to automatically fetch inputs and submit solutions. I’ve also abstracted away a bunch of modules and useful functions into one monolithic file for faster imports. All in all, I save about 30 seconds now.
module Solutions.Day7 where import Helpers -- Control.Arrow, Control.Applicative, Control.Monad, Data.Maybe, Data.List.Split, Data.List
We also need a way to map keys to values.
Data.Map is comfy, although it uses trees instead of hash tables internally. That’s fine for our purposes.
import Data.Map (Map, (!)) import qualified Data.Map as M
Following my tradition of avoiding regex like the plague, we’ll spit out something naive to parse our input into the format we want. In my defense, even Parsec is an ordeal to debug and it was late.
It seems like every line has the term
bags contain separating the description of a bag and the description of its children, so we’ll use
Data.List.Split. Only matching a 2-element list like that is dangerous in the real world, because you’ll hit a parse error if you try to match a list of any other length.
If a description says
no other, we can (safely) assume that there won’t be any outgoing edges from this graph node. It also saves us from a potential edge case when trying to parse the descriptions of inner bags. We’ll focus on a single line at first.
parseBag :: String -> (String, [(String, Int)]) = splitOn " bags contain" >>> \[colour, inners] -> (colour, edges) parseBag where edges = ("no other" `isPrefixOf` inners ?  $ ((map parseDscrp . splitComma) inners))) -- we can optimize by using a shorter matching string, like "no o" -- no regex allowed
“But Haskell doesn’t have ternary operators???” you say, bound by the shackles of inflexible syntax.
(?) :: Bool -> a -> a -> a ?) True = const (?) False = const id ( -- splitComma is also defined in helpers splitComma :: [Char] -> [[Char]] = splitOn ","splitComma
We also need to parse the predicates of each sentence. We know that each description is separated by commas, so we can break the task down to parsing a single description at a time. The inputs for
parseDscrp will look like
<number> <adjective> <colour> (bag[s]) at this point. Wikipedia doesn’t list any colours that start with “bag”, and Eric isn’t evil, so we’ll filter out any “bag”-like word too.
Since every sequence starts with a number, we’ll just split by words, turn the
<number> into an
Int, and use the remainder as our colour. These colours should match up with the colour descriptions that preface each line, that we’ll use as keys in our eventual
parseDscrp :: String -> (String, Int) = words >>> filter (not . ("bag" `isPrefixOf`)) >>> (tail &&& head) >>> (unwords *** read) parseDscrp -- \(n:bs) -> (unwords bs, read n))
Let’s try these out now.
> parseDscrp "5 muted pink bags" 5, "muted pink") ( > parseBag "bright orange bags contain 5 muted pink bags, 1 dark black bag." "bright orange", [(5, "muted pink"), (1, "dark black")]) ( > parseBag "dark black bags contain no other bags." "dark black", )(
Way easier than writing regular expressions, right? At least it’s more fun this way. Let’s build our graph now -
Data.Map expects a list
[(key, value)], which matches up with the output type of
parseBag. All our types match up, so we’ll connect our functions into a neat little pipeline and build a dependency graph from our input.
type Graph = Map String [(String, Int)] fromInput :: String -> Graph = lines >>> map parseBag >>> M.fromListfromInput
To put the prompt into simpler terms, it’s asking how many nodes in our graph can reach “shiny gold”. We know that each bag doesn’t contain that many different bags, and that the result of searching for “shiny gold” in a bag’s path depends on whether we find it deeper down in our traversal. In any other languages, this is a dynamic programming problem. We have a lot of inputs, a (potentially expensive) recursive call, and a ton of sharing between values. Luckily, we’re working in a lazy language, and values only get computed once within a given closure. If we pass “matte beige” into
walk, find an answer, and encounter “matte beige” again during a later traversal, the answer will be returned immediately since the results will be cached by the GHC runtime.
walk is recursive, and we’re likely to encounter the same values many times, so having implicit memoization in the background saves us a ton of effort. To be honest, getting implicit memoization to kick in is a subtle thing, but my code took less than 60ms for both parts combined so I’ll count that as a win. I’ll have to come back and do some profiling at a later date to get a better insight of what’s going on underneath.
In the meantime, we’ve done it. Either a node has “shiny gold”, or one of its children does. We’ll traverse from every node in our graph, and count the number of successful starting points. Again, passing 3 functions
h, f, g into
liftA2 will apply functions
f, g to the same input, passing both results as arguments into
h. It’s incredibly useful for capturing the pattern of passing a single input into two computations, and combining their results.
walk :: Graph -> String -> Bool = "shiny gold" `elem` kids || any (walk g) kids walk g b where kids = map fst $ (g ! b) -- liftA2 (||) (elem "shiny gold") (any $ walk g)
That’s it. We can map
walk over the keys of our graph directly, saving us from having to convert it back down to a list.
day7Pt1 :: String -> Int = fromInput >>> (\graph -> M.filterWithKey (\k _ -> walk graph k) graph) >>> M.sizeday7Pt1
If you want to be even more clever, you can use the
Monad instance of the function type
((->) r) (lifting sequential function application with the same input into a monadic bind) to cut this down even more. Brevity is free in the lambda calculus.
instance Monad ((->) r) where (>>=) :: (r -> a) -> (a -> (r -> b)) -> (r -> b) >>= f = \x -> f (g x) x g day7Pt1' :: String -> Int = fromInput >>> ((walk >>> (const .)) >>= M.filterWithKey) >>> M.sizeday7Pt1'
instance Applicative ((->) r) where -- pure :: a -> ((->) r a) pure :: a -> (r -> a) pure = const -- (<*>) :: ((->) r) (a -> b) -> ((->) r a) -> r -> b (<*>) :: (r -> a -> b) -> (r -> a) -> r -> b <*>) f g x = f x (g x) (
Part 2 coming soon!
innerBags :: Graph -> String -> Int = succ (sum $ uncurry ((*) . innerBags g) <$> (g ! b)) innerBags g b day7Pt2 :: String -> Int = fromInput >>> (pred . flip innerBags "shiny gold") day7Pt2 -- pred because a shiny gold bag can't contain itself