problem6.py

import aoc
from collections import deque

class ProblemA(aoc.ProblemBase):
	def solveAll(self):
		lines = []
		with open(self.getInput()) as f:
			for line in f:
				lines.append(line)
		return self.compareOutput(self.solveInstance(lines))
	
	def transform(self, vals):
		return vals
	
	def solveInstance(self, input):
		orbits = {}
		for orbit in input:
			a, b = orbit.rstrip().split(")")
			if a not in orbits:
				orbits[a] = {"indirect": 0, "planets": []}
			orbits[a]["planets"].append(b)
		direct = len(orbits) - 1
		indirect = 0
		queue = deque(["COM"])
		while len(queue) > 0:
			obj = queue.popleft()
			indirect += orbits[obj]["indirect"]
			for planet in orbits[obj]["planets"]:
				if planet not in orbits:
					indirect += orbits[obj]["indirect"] + 1
					continue
				orbits[planet]["indirect"] = orbits[obj]["indirect"] + 1
				queue.append(planet)
		return indirect # ignore direct because direct and indirect are counted twice otherwise
		

class ProblemB(ProblemA):
	def getpath(self, orbits, obj):
		path = []
		while obj != "COM":
			obj = orbits[obj]
			path.append(obj)
		path.reverse()
		return path
	
	def solveInstance(self, input):
		orbits = {}
		for orbit in input:
			a, b = orbit.rstrip().split(")")
			orbits[b] = a
		san = self.getpath(orbits, "SAN")
		you = self.getpath(orbits, "YOU")
		for i in range(min(len(san), len(you))):
			#print(f"{i} {san[i]} {you[i]}")
			if san[i] != you[i]:
				return len(san) + len(you) - 2 * i