Advent of Code 2019 - Day 6

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.