Advent of Code 2019 - Day 6Universal Orbit Map

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

The problem forms a tree because of the following observations:

1. Each object orbits exactly one other object (one parent).
2. There is a single object COM that does not orbit anything (unique root).
3. An object cannot indirectly orbit itself (no cycles). This is not explicitly stated, but I assumed this based on how orbits should work.

Part 1

"Direct orbits" are parent-child relationships; "indirect orbits" are ancestor-descendant relationships. Thus, for each node in the tree, we just count the number of ancestors. This is the depth of the node. Depths can be computed with either BFS or DFS; I prefer BFS.

Part 2

We want to find the shortest path from YOU to SAN. Since this is a tree, there is a unique path between any two nodes. Again this is a BFS, starting at YOU, searching for SAN. The result is depth - 2, since we want to exclude the starting and ending nodes.