Advent of Code 2020 - Day 7Handy Haversacks

Python | Problem statement | Source code | Tags: BFS/DFS

Part 1

We can model the rules as a directed graph, where each node is a bag color, and each edge points to a bag color that it can contain. We want to find all the bag colors that can eventually contain at least one "shiny gold" bag. This is equivalent to finding all nodes that can reach the "shiny gold" node, or equivalently, all nodes reachable from the "shiny gold" node in the reversed graph. Graph reversal looks like:

rev_graph: defaultdict[str, list[str]] = defaultdict(list)
for parent, children in graph.items():
    for _, child in children:
        rev_graph[child].append(parent)
python

As for traversal, I chose DFS because a stack is just a list.

Part 2

This is DFS in the other direction: starting from "shiny gold", count all the bags it must contain. If a bag contains no other bags, it contributes 1 (itself). Otherwise, it contributes 1 plus the sum of the counts of each child bag color multiplied by the color's number. This feels more recursive than iterative, but still DFS in nature.

def dfs(node: str) -> int:
    return sum(count * (1 + dfs(child)) for count, child in graph[node])
python