Day 7. Handy Haversacks

Problem statement

https://adventofcode.com/2020/day/7 (mirror)

My solution

Day 7 brings a simple graph problem.

Each line of the input describes a relationship between a parent bag, and zero or more child bags, that are inside the parent bag:

dull coral bags contain 1 dim olive bag, 5 muted violet bags, 2 dark gray bags.

This is equivalent to a description of a directed graph, where each color correspond to a node, and the “containment” relationship is a directed edge between two nodes (parent bag having multiple childs of the same color can be conisidered either as a weighted edge or multiple edges, it does not really matter).

Since the graph is directed, we can describe it equivalently in two ways:

for each child node, we can create a dictionary of all parents that have this child inside it,
for each parent node, we can create a dictionary of all child nodes that the parent have inside.

The first approach is used in Part A, the second one – in Part B.

We make a silent assumption that the graph does not have any circular paths. This is not explicitly stated in problem description – but a recursive path containing a shiny gold path would mean that the answer to Part B diverges to infinity.

Parsing each rule is easily done with regular expressions. We will use two patterns:

The “outer” pattern ^(\w+ \w+) bags contain (.+)\.$. The first group catches the color of the parent bag, the second group catches a raw list of all child bags or the special sentence no other bags, which signifies that a parent bag does not have any children.
The “inner” pattern (\d+) (\w+ \w+) bag, where the first group catches the count, and the second group catches the color for each child bag.

We will apply those rules sequentially – first to split the rule into parent and children, and the second to separate the children. Depending on the part, we create two different dictionaries.

Part A: To each child we map its parents.

string[] parentAndChildren = Regex.Split(rule, rulePattern);

string parent = parentAndChildren[1];

if (parentAndChildren[2] != "no other bags")
{
    var children = Regex.Matches(parentAndChildren[2], childPattern);

    // If we use anonymous var here, then match will be of type `object`!
    foreach (Match child in children) 
    {
        var childColor = child.Groups[2].Value;
        if (!parentsOfChild.ContainsKey(childColor))
        {
            parentsOfChild[childColor] = new HashSet<string>();
        }
        parentsOfChild[childColor].Add(parent);
    }
}

Part B: To each parent we map its children. Note that this time, contatry to Part A, we are also interested in the count of each color.

string[] parentAndChildren = Regex.Split(rule, rulePattern);

string parent = parentAndChildren[1];
childrenOfParent[parent] = new HashSet<(string bag, int count)>();

if (parentAndChildren[2] != "no other bags")
{
    var children = Regex.Matches(parentAndChildren[2], childPattern);

    // If we use anonymous var here, then match will be of type `object`!
    foreach (Match child in children)
    {
        var childColor = child.Groups[2].Value;
        var childCount = Int32.Parse(child.Groups[1].Value);
        childrenOfParent[parent].Add((childColor, childCount));
    }
}

Note that there will be some colors that don’t have any children (“no other bags”), and there will be some colors that don’t have any parents (this is not as easily visible).

Having created the dictionaries, we just need to traverse them fully, starting each time from a shiny gold bag.

In Part A, in graph terms, we want to count the number of nodes that can be parents, “grandparents”, etc., of a shiny gold bag. So we create a queue which initially includes only a shiny gold, and then create a loop that dequeues a bag and enqueues all its parents. We will store all valid nodes in a hashset to correctly handle a case when there are multiple paths leading to the same node; consider example:

color A bags contain color B bags, color C bags.
color B bags contain color D bags.
color C bags contain color D bags.

We only care if there exists a path from D to A, we don’t care if there are multiple such paths.

In Part B, we also start from a shiny gold bag, but this time we traverse graph in the opposite direction. This time we are also interested in the specific number of bags of each color. The simplest way to do it is to use recursion – method BagsInside will return 0, if a bag holds “no other bags”, or call itself recursively for each child bag:

foreach (var child in childrenOfParent[parentBag])
{
    answer += child.count * (1 + BagsInside(child.bag, childrenOfParent));
}