Advent of Code Day 6

testinput = """COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L"""

from collections import defaultdict
def process(input_text):
    orbits = input_text.split("\n")
    connections = [orbit.split(")") for orbit in orbits]
    graph = defaultdict(lambda: set())
    roots = set()
    for connection in connections:
        roots.add(connection[0])
        graph[connection[0]].add(connection[1])
    for connection in connections:
        if connection[1] in roots:
            roots.remove(connection[1])
        
    return roots, graph

process(testinput)

({'COM'},
 defaultdict(<function __main__.process.<locals>.<lambda>()>,
             {'COM': {'B'},
              'B': {'C', 'G'},
              'C': {'D'},
              'D': {'E', 'I'},
              'E': {'F', 'J'},
              'G': {'H'},
              'J': {'K'},
              'K': {'L'}}))

total = 0
visited = set()

def count_paths(roots, graph, depth = 0):
    global total
    for root in roots:
        if root in visited:
            continue
            
        visited.add(root)
        
        total += depth
        
        if root in graph:
            count_paths(graph[root], graph, depth + 1)

count_paths(*process(testinput))

total

42

total = 0
with open("AoC/input6.txt") as inputfile:
    count_paths(*process(inputfile.read().strip()))

total

251208

roots, graph, bigraph = None, None, defaultdict(lambda: set())
with open("AoC/input6.txt") as inputfile:
    roots, graph = process(inputfile.read().strip())
    for root in graph:
        bigraph[root].update(graph[root])
        for pt in graph[root]:
            bigraph[pt].add(root)

[(x, y) for (x, y) in graph.items() if "SAN" in y or "YOU" in y] 

[('Z48', {'YOU'}), ('87T', {'SAN'})]

distances = dict()
def bfs(start, graph, dist=0):
    if start in distances:
        return
    
    distances[start] = dist
    for node in graph.get(start, set()):
        bfs(node, graph, dist + 1)

bfs('Z48', bigraph)

distances['Z48']

0

distances['87T']

397