# Advent of Code 2019: Day 6

This was a fun challenge, because it seemed really hard at first, but once I figured out how to think about it, it was quite simple. I’m given a set of pairings, each of which contains two objects, the second orbits around the first. I’ll play with counting the number of orbits going on, as well as working a path through the orbits. This was the first time I brought out recurrisive programming this year, and it really fit well.

## Challenge

The puzzle can be found here. The idea is that something orbits around it’s parent, and all parents of the parent. For part one, I’m simply asked to count the orbits. So if A orbits B, and B orbits C, then there are 3: A around B, B around C, and A around C. For part two, I’m given a start and an end, and asked to figure out how many hops between the two spots.

## Solution

### Part 1

This looked at first like a spatial problem, but it’s really not. The picture they give for an example really just shows a tree:

```
G - H J - K - L
/ /
COM - B - C - D - E - F
\
I
```

I’ll notice that each time I add a node, the number of orbits added is just the depth of the node on the tree. Addin a child to COM just adds one. Adding a child to B adds two, B and COM.

So if I can just track each node’s children, I can walk the three and sum each node’s depth to get the total number of nodes. that code looks like this:

```
#!/usr/bin/env python3
import sys
from collections import defaultdict
def count_orbits(orbit, depth):
return depth + sum([count_orbits(o, depth + 1) for o in orbits[orbit]])
with open(sys.argv[1], "r") as f:
orbit_input = [l.strip().split(")") for l in f.readlines()]
orbits = defaultdict(list)
for orbit in orbit_input:
orbits[orbit[0]].append(orbit[1])
print(f"Part 1: {count_orbits('COM', 0)}")
```

First, I walk through my input list and convert it into dictionary of lists, such that for each node as a key, the value is the child nodes.

Then I use this `count_orbits`

function to add the depth of the current node, plus the sum of the depths of all the child nodes. If a node has no children, it just returns its depth.

This works nicely:

```
$ time ./day6.py 06-puzzle_input.txt
Part 1: 130681
real 0m0.022s
user 0m0.015s
sys 0m0.007s
```

### Part 2

In part two, I’ll no longer just need to track from parent to child to walk the tree. Now I need to be able to explore from a child back to a parent. I’ll create a second structure for this, `orbits2`

, this time which is a `defaultdict`

of sets (because I don’t need duplicates and will have them). For each pairing of A orbits B, I’ll add A to B’s list, and B to A’s list. That way each node knows of all it’s neighbors. I’ll also track the `YOU`

node that gives me the starting spot:

```
orbits = defaultdict(list)
orbits2 = defaultdict(set)
for orbit in orbit_input:
orbits[orbit[0]].append(orbit[1])
orbits2[orbit[1]].add(orbit[0])
orbits2[orbit[0]].add(orbit[1])
if orbit[1] == "YOU":
start = orbit[0]
```

I’ll use a similar recursive strategy, this time walking both directions in search of the end, `SAN`

. I’ll also track the previous nodes visited on that walk. It doesn’t seem there are loops, but I’ll track the entire path to be sure. If a node is a neighbor of the current node, but also in the previous list, I don’t need to head back that way.

```
def find_path(orbit, prev, count):
if "SAN" in orbits[orbit]:
print(f"Part 2: {count}")
sys.exit()
for o in orbits2[orbit]:
if o in prev:
continue
find_path(o, prev + [o], count + 1)
```

Putting that together, it still runs fast:

```
$ time ./day6.py 06-puzzle_input.txt
Part 1: 130681
Part 2: 313
real 0m0.028s
user 0m0.024s
sys 0m0.004s
```

## Final Code

```
#!/usr/bin/env python3
import sys
from collections import defaultdict
def count_orbits(orbit, depth):
return depth + sum([count_orbits(o, depth + 1) for o in orbits[orbit]])
def find_path(orbit, prev, count):
if "SAN" in orbits[orbit]:
print(f"Part 2: {count}")
sys.exit()
for o in orbits2[orbit]:
if o in prev:
continue
find_path(o, prev + [o], count + 1)
with open(sys.argv[1], "r") as f:
orbit_input = [l.strip().split(")") for l in f.readlines()]
orbits = defaultdict(list)
orbits2 = defaultdict(set)
for orbit in orbit_input:
orbits[orbit[0]].append(orbit[1])
orbits2[orbit[1]].add(orbit[0])
orbits2[orbit[0]].add(orbit[1])
if orbit[1] == "YOU":
start = orbit[0]
print(f"Part 1: {count_orbits('COM', 0)}")
find_path(start, ["YOU"], 0)
```