### re: Advent of Code 2019 Solution Megathread - Day 6: Universal Orbit Map VIEW POST

This was a fun and welcomed change to yesterday's problem.

Feeling like I duct-taped part 2 together, but here's my Python implementation that got the job done for me:

import fileinput

def construct_tree(data):
parents = {}
for line in data:
parent, node = line.strip().split(')')
parents[node] = parent
return parents

def num_orbits(node, parent, root, memo):
if node == root:
return 0
if node in memo:
return memo[node]

total = 0
p  = parent[node]
total = total + num_orbits(p, parent, root, memo) + 1
memo[node] = total

def get_ancestors(node, parent, root, ancestors):
if node == root:
return ancestors
ancestors.append(parent[node])
return get_ancestors(parent[node], parent, root, ancestors)

def get_common_ancestor(a, b):
for i in range(len(a)):
for j in range(len(b)):
if a[i] == b[j]:
return a[i]
return None

tree = construct_tree(fileinput.input())

# part 1
total, memo = 0, {}
for node in tree:
total += num_orbits(node, tree, 'COM', memo)
print(total)

#part 2
node_a, node_b = tree['YOU'], tree['SAN']
a = get_ancestors(node_a, tree, 'COM', [])
b = get_ancestors(node_b, tree, 'COM', [])

common_ancestor = get_common_ancestor(a, b)
res1 = num_orbits(node_a, tree, common_ancestor, {})
res2 = num_orbits(node_b, tree, common_ancestor, {})
print(res1 + res2)

code of conduct - report abuse