Sean McLemon | Advent of Code

Home | Czech | Blog | GitHub | Advent Of Code | Notes


2019-12-06 - Universal Orbit Map

(original .ipynb)

Day 6 puzzle input is a number of string pairs, which represent objects which orbit each other (mine is here). Part 1 involves figuring out how many objects are directly or indirectly orbiting each other in total. Part 2 involves treating this as a graph and finding the shortest path from/to a given object.

raw_test_orbits = [ "COM)B", "B)C", "C)D", "D)E", "E)F", "B)G", "G)H", "D)I", "E)J", "J)K", "K)L" ]


def build_orbit_tree(raw_orbits, invert=False):
    orbits = [ s.split(")") for s in raw_orbits ]
    orbit_tree = {}

    for mass, orbiter in orbits:
        
        if invert:
            if orbiter in orbit_tree:
                orbit_tree[orbiter].append(mass)
            else:
                orbit_tree[orbiter] = [ mass ]
        else:
            if mass in orbit_tree:
                orbit_tree[mass].append(orbiter)
            else:
                orbit_tree[mass] = [ orbiter ]
            
    return orbit_tree

def count_orbits(mass, orbit_lookup):
    if mass in orbit_lookup:
        return len(orbit_lookup[mass]) + sum([ count_orbits(orbiter, orbit_lookup) for orbiter in orbit_lookup[mass]])
    
    return 0

def total_orbits(raw_orbits):
    orbit_tree = build_orbit_tree(raw_orbits)
    return sum([count_orbits(mass, orbit_tree) for mass in orbit_tree])

assert 42 == total_orbits(raw_test_orbits)
puzzle_input_data = [ l.strip() for l in open("puzzle_input/day6.txt", "r").readlines() ]

print(total_orbits(puzzle_input_data))
150150
import math

def find_route(from_mass, to_mass, orbits_raw):
    orbit_tree = build_orbit_tree(orbits_raw, True)
    
    assert from_mass in orbit_tree
    assert to_mass in orbit_tree
        
    # first walk the to node back to COM
    node = to_mass
    distance_from_destination = {}
    distance = -1
    while node != "COM":
        for child in orbit_tree[node]:
            if child != node:
                break              
        distance_from_destination[node] = distance
        distance += 1        
        node = child
        
    # now walk from node back until it's seen something in "to"
    
    node = from_mass
    distance = -1
    while node not in distance_from_destination:
        for child in orbit_tree[node]:
            if child != node:
                break
        distance += 1
        node = child
        
    # subtract 2 since we were counting the h
    return distance + distance_from_destination[node]

test_input_str = """COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
K)YOU
I)SAN"""
test_input = [l.strip() for l in test_input_str.split("\n")]

assert 4 == find_route("YOU", "SAN", test_input)
print(find_route("YOU", "SAN", puzzle_input_data))
352