advent of code 2020, day 7: droste and bourke
Written: 2020-12-07 to 2020-12-07by Naomi Liu
Part 2 of 2 in this series.
[prev] [index] [next]
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 Map
of String
s (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 splitOn
from 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 Map
.
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 - fromList
from 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.fromList fromInput
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.size day7Pt1
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.size day7Pt1'
Really useful stuff. The Applicative
instance of the function type ((->) r)
additionally
corresponds to the S
combinator, which
encapsulates the flipped
version of this pattern,
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