advent_of_code_2019_day6

import re


class GraphNode:
    '''a Node class for representing nodes in a graph'''
    def __init__(self, name=None, jumps=0, children=set(), path=[]):
        self.name = name
        self.jumps = jumps # jumps represents the number of jumps/'links' from the root node
        self.children = children # this is a set with pointers to child nodes
        self.path = path # this is a list with the names of all nodes leading from the root node to the self node

    def __str__(self):
        return str(self.name)

    def add_connection(self, connect_node):
        '''adds a Node instance to the set of children'''
        self.children.add(connect_node)


class QueueNode:
    '''a Node class for representing nodes in a queue (that can only have one child node)'''
    def __init__(self, cargo=None):
        self.cargo = cargo
        self.next = None

    def __str__(self):
        return str(self.cargo)


class Queue:
    '''a Queue class that uses QueueNodes for implementing a FIFO data structure'''
    def __init__(self):
        self.head = None
        self.tail = None

    def insert(self, cargo):
        '''inserts a QueueNode instance with the specified cargo (i. e. GraphNode instance) to the end of the queue'''
        node = QueueNode(cargo)
        if self.head is None:
            self.tail = self.head = node
        else:
            self.tail.next = node
            self.tail = node

    def remove(self):
        '''removes the QueueNode instance at the front of the queue and returns its cargo (i. e. GraphNode instance)'''
        rmcargo = self.head.cargo
        if self.head.next:
            self.head = self.head.next
        else:
            self.head = None
        return rmcargo


with open('/Users/lowe/Documents/Programmering/Python/Python projects/advent_of_code/day6/input', 'r') as f:
    instr = f.read()

orb_str_ls = instr.split('\n')
orb_str_ls = orb_str_ls[:len(orb_str_ls)-1] # creates a list of all children (removing the empty string in the last list pos)

# dir_orb = len(orb_str_ls) # number of direct orbits is number of children (not actually needed I think)

orb_dict = {} # creates a dictionary object for orbits, where keys are center objects and values are sets of objects orbiting the center obj

for i in orb_str_ls:
    cent_obj, orb_obj = re.search("^(.+)\)(.+)", i).groups()
    if orb_dict.get(cent_obj):
        orb_dict[cent_obj].add(orb_obj)
    else:
        orb_dict[cent_obj] = {orb_obj}

gnod1 = GraphNode(name="COM", jumps=0, children=set())
orb_q = Queue()
orb_q.insert(gnod1)
tot_jumps = 0
targ_dict = {} # target dictionary for 'SAN' and 'YOU'

while orb_q.head: # while queue isn't empty
    par_nod = orb_q.remove() # remove the node first in line from the queue and refer to it by 'par_nod'
    tot_jumps += par_nod.jumps
    if not orb_dict.get(par_nod.name):
        continue
    for i in orb_dict[par_nod.name]: # for each orbit name connected to the parent node name key in orb_dict
        child_nod = GraphNode(name=i, jumps=par_nod.jumps+1, children = set(), path = par_nod.path + [par_nod.name]) # create a graph node with the orbit name, and 1 more jump than the par_node
        if i in ['SAN', 'YOU']:
            targ_dict[i] = child_nod # add direct references to the 'SAN' and 'YOU' nodes
        par_nod.children.add(child_nod) # add the new graph node to the parent node's children
        orb_q.insert(child_nod) # add the child node to the queue so its children will be added to it in a later iteration

san_path = targ_dict['SAN'].path # get full path to 'SAN'
you_path = targ_dict['YOU'].path
total_dist = 0
for i in range(len(you_path)-1, -1, -1):
    for j in range(len(san_path)):
        if you_path[i] == san_path[j]:
            total_dist = len(you_path) - i + len(san_path) - j - 2 # len(you_path) - i gives the number of nodes from the common path node (inclusive) to the 'YOU' node. 2 has to be subtracted to make sure that 1) the common node isn't counted twice, and 2) to count the number of 'orbital transfers', see the homepage for explanation
            break
    if total_dist:
        break

print("The total distance is: {}".format(total_dist))