## Intro

I just finished day 6 right before (*checks watch*) the day 16 puzzle comes
out. Who’s counting? As always, you can find my full solutions repo
here.

## Solution

I knew that this was a tree problem but wanted to avoid building one for as long as I could. I solved the first part of the puzzle by with only a sorted list of orbit pairs. Here’s the sort code:

```
def sortOrbits(orbits):
if len(orbits) <= 1:
return
# Put "COM" first
for i in range(0, len(orbits)):
if orbits[i].orbitee == "COM":
temp = orbits[0]
orbits[0] = orbits[i]
orbits[i] = temp
# Sort the rest of the orbit pairs
trail, inner, lead = (1, 1, 1)
target = orbits[0].orbiter
while trail < len(orbits):
while lead < len(orbits):
if orbits[lead].orbitee == target:
temp = orbits[inner]
orbits[inner] = orbits[lead]
orbits[lead] = temp
inner += 1
lead += 1
target = orbits[trail].orbiter
trail += 1
lead = inner
```

It sorts the list in place in a breadth-first order by keeping each group of horizontal children next to each other. This way, I can build the tree without having to worry about whether or not I need to swap the node order.

I initially solved part 1 using only this sorted list. I deleted the code, but it was basically going backward through the list and tracing each node chain back to the COM object. Since the list was sorted, going backward ensured that nothing would get double-counted.

This was way easier after I finally caved and built a tree of orbit pairs. Then, all it took was a simple recursive function to count the total number of links.

```
# If this wasn't just a puzzle, I would wrap this so you wouldn't need to pass
# in `depth` since that doesn't really make sense from user's standpoint.
def countOrbits(head, depth):
if not head.children:
return depth
subtotal = depth
for child in head.children:
subtotal += countOrbits(child, depth + 1)
return subtotal
countOrbits(head, 0)
```

To find the shortest path to Santa’s orbit, I pass the two references to “Santa”
and “You” objects (found with a search function) to `findDistance()`

. This
function first finds the distance to the common ancestor node and then counts
the depth to the destination node. Adding those two counts (and subtracting one,
since you’re really trying to count orbit switches and not overall depth) gives
you the shortest number of orbit swaps required to get you orbiting the same
body as Santa. Incredible.

```
def findDistance(src, dest):
distance = 0
cur = src.parent
while cur.id != dest.parent:
curtemp = searchChildNodes(dest.id, cur)
if curtemp:
return distance + countNodeDepth(dest.id, cur) - 1
cur = cur.parent
distance += 1
```

As always, you can find my full solutions repo here.