Hola! We’re on Day 07 of our Advent of Code Journey 2020. With our trusty rust ferris by our side, we have been able to solve some puzzles in the past couple of days. Let’s look at how we can get through today’s puzzle.
Spoilers Ahead. The full solution the problem is available here.
** Problem - Part 01 **
Given a list of rules specifying the bags (color, count) a colored bag can contain inside it, find the number of bags that can hold a specified color (“shiny gold” in our case). Each bag inside a colored bag, can in-turn contain more bags, and the rules for all of it together forms our problem’s input.
The input is an exhaustive set of rules, some of which look like:
In the above rules, the following options are available to hold a shiny gold bag:
So, in this example, the number of bag colors that can eventually contain at least one shiny gold bag is 4. From the problem you might be able to make out a data-structure apt for storing this one-way relationship - Graphs. We can use a directed acyclic graph (DAG) to represent this data.
If DAG sounds complicated, its nothing but a graph wherein there’s a connection between a node A => B but NOT B => A, and there are no cycles.
In order to hold both the color and the count, let’s define a struct Bag.
Implementing a Graph
Now let’s implement a Graph Datastructure. Since this is a graph of bag colors, we call it a BaggyColorGraph :). Let’s discuss some key things about the graph we need to implement:
Graphs typically use an adjacency matrix or an adjacency list to keep track of nodes / vertexes. We will build an adjacency list, which will be a
HashMap<String, Vec<Bag>> wherein each value looks something like BagColor => ["Color1", "Color2"].
A vertex in our graph, represents a color Bag that may or may not have other bags inside it. An edge in our graph represents, a bag containing another bag of count (x).
To identify if two vertexes have an edge, we use a Depth First Search Approach, where in we traverse all the vertices connected to a given vertex, and then its neighbors and then its neighbors, and backtrack after there are no neighbors left. The Graph implements a dfs method to perform the same.
Alright, let’s see how this looks like in code:
Now that we have a Graph implementation in place, we need to create a graph from the given rules input. The algorithm to process the input and turn it into a graph would be as follows:
Collect the input lines into a vector, and then iterate over every line. Since we know from the input that every rule is separated clearly by the words “bags contain”, lets use that to split the rule into a color string, and a comma separated string specifying the count and color bags inside.
We can trim additional spaces off from color and count and colors inside and then further split it by comma into a new vector bags_inside. bags_inside needs to be further parsed (using regex), into count and the bag color. We can initialize the Bag struct, to hold these values.
Iterate through bags_inside, create a vertex in the graph, create the edges between color and every color bag inside it. Once we are done with all the iterations, our graph is built.
For colors which have the value “no colors inside”, we will add them as an empty value in the graph.
In our main function we can call create_graph followed by the count_edges_to function to solve Part 01.
Problem - Part 02
Since we have our graph built, part 02 would be pretty straightforward. Given a color, find the count of all the possible bags inside. This is essentially recursively going deep into a specified vertex, and counting the bags inside.
Let’s add a method to BaggyGraph for that:
As you can see the recursive function call returns the total possible bag counts inside a specified bag. Invoking this method from our main function will get the answer for Part 02.
Whew! Today was a looong one, but hopefully it was helpful to learn how to build a bare-bones DAG in Rust, and also solve Day 07. See you tomorrow!