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.
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 orbits = orbits[i] orbits[i] = temp # Sort the rest of the orbit pairs trail, inner, lead = (1, 1, 1) target = orbits.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
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.