#!/bin/python3
import sys, re
from pprint import pprint
from collections import Counter

input_f = 'input'
part = 2


#########################################
#                                       #
#              Part 1                   #
#                                       #
#########################################

def part1():
    children = []
    mains = []
    with open(input_f)as file:
        for line in file:
            l = line.rstrip()
            if '->' in l:
                x = l.split('->')
                for i in x[1].split(','):
                    children.append(i.strip())
                match = re.match(r"^(\S+)",x[0])
                if match:
                    mains.append(match.group(1))

    for x in mains:
        if x not in children:
            return x

if part == 1:
    print(part1())



#########################################
#                                       #
#              Part 2                   #
#                                       #
#########################################

def find_children(x,grid):
    # x will be a string like 'tknk'
    print('Testing ',x)
    found = []
    for i in grid:
        if i.startswith(x):
            
            match = re.search(r"-> (.+)", i)
            if match:
                found = [item.strip() for item in match.group(1).split(",")]
                print(found)
            else:
                print([i for i in grid if i.startswith(x)])
    if found != None:
        for j in found:
            find_children(j,grid)

def calculate_weights(node, tree, weights, total_weights):
    # Compute total weight for the current node
    total = weights[node]
    for child in tree[node]:
        total += calculate_weights(child, tree, weights, total_weights)
    total_weights[node] = total
    return total

def find_outlier(lst):
    count = Counter(lst)
    outlier = None
    reference = None
    for num, freq in count.items():
        if freq == 1 or freq < len(lst) - 1:
            outlier = num
        else:  
            reference = num
    return outlier,reference

def find_unbalanced(node, tree, weights, total_weights):
    child_weights = [total_weights[child] for child in tree[node]]
    if len(set(child_weights)) == 1: 
        return None

    weight_counts = {w: child_weights.count(w) for w in child_weights}
    incorrect_weight = next(w for w, count in weight_counts.items() if count == 1)
    correct_weight = next(w for w, count in weight_counts.items() if count > 1)
    unbalanced_child = tree[node][child_weights.index(incorrect_weight)]

    deeper_issue = find_unbalanced(unbalanced_child, tree, weights, total_weights)
    if deeper_issue:
        return deeper_issue
    else:
        return unbalanced_child, weights[unbalanced_child] + (correct_weight - incorrect_weight)

if part == 2:
    children = []
    mains = []
    grid = []
    with open(input_f)as file:
        for line in file:
            l = line.rstrip()
            grid.append(l)
    
    tree = {}
    weights = {}
    for line in grid:
        match = re.match(r"(\w+) \((\d+)\)(?: -> (.+))?", line)
        if match:
            name = match.group(1)
            weight = int(match.group(2))
            children = match.group(3).split(", ") if match.group(3) else []
            tree[name] = children
            weights[name] = weight

    total_weights = {}

    calculate_weights(part1(),tree,weights,total_weights)
    result = find_unbalanced(part1(), tree, weights, total_weights)
    print(result)
    #unbalanced_values = []
    #for key,value in tree.items():
    #    if value:
    #        t_values = []
    #        max_v = 0
    #        change = 0
    #        for i in value:
    #            t_values.append(int(total_weights[i]))
    #        if all(v == t_values[0] for v in t_values):
    #            continue
    #        else:
    #            print('STOP')
    #            print(t_values)
    #            input()
    #            unbalanced_values.append(t_values)


    #print(unbalanced_values)
    #unbalanced_values = list(reversed(unbalanced_values))
    #print(unbalanced_values)
    
    #for t_values in unbalanced_values:
    #    outlier,reference = find_outlier(t_values)
    #    change = max(outlier,reference) - min(outlier,reference)
    #    max_v = max(outlier,reference)

        #if t_values[0] == t_values[1]:
        #    if t_values[0] == t_values[2]:
        #        if t_values[1] == t_values[2]:
        #            change = t_values[1] - t_values[2]
        #            max_v = max(t_values[1],t_values[2])
        #    else:
        #        change = t_values[0]-t_values[2]
        #        max_v = max(t_values[0],t_values[2])
        #else:
        #    change = t_values[0] - t_values[1]
        #    max_v = max(t_values[0],t_values[1])

    #    print(change)
    #    print(max_v)

       
        
    #    new_val = max_v-change
    #    print(new_val)

    #    for odx,o in enumerate(t_values):
    #        if o == max_v:
    #            total_weights[value[odx]] = new_val

                    #for kx,x in total_weights.items():
                    #    if x == max_v:
                    #        print(weights[kx])
                    #        print(weights[kx]-change)