Recursive Circus

Part 1



In [74]:

    
import csv
import copy

def parse_list():
    
    weights = {}
    parents = {}
    children = {}

    with open('input.txt', 'rt') as f_input:
        csv_reader = csv.reader(f_input, delimiter=' ')
        for line in csv_reader:
            prog = line[0]
            weights[prog] = int(line[1][1: -1]) 
            if '->' in line:
                ind = line.index('->')
                offspring = [a.rstrip(',') for a in line[ind + 1:]]
                children[prog] = offspring
                for child in offspring:
                    parents[child] = prog
            else:
                children[prog] = []
    return weights, parents, children

weights, parents, children = parse_list()



In [76]:

    
def has_bottom(prog):
    for k, v in children.items():
        if prog in children[k]:
            return True
    return False

def bottomest():
    for prog in children:
        if not has_bottom(prog):
            return prog

bottomest()









    Out[76]:





'dgoocsw'

Part 2



In [184]:

    
weights, parents, children = parse_list()



In [185]:

    
# we shall not assume all the children are leaves

def pick_cherry(leaves):
    while leaves:
        leaf = leaves.pop()
        parent = parents[leaf]
        offspring = children[parent]
        try:
            for child in offspring:
                assert(children[child] == [])
            return parent
        except AssertionError:
            pass



In [186]:

    
import copy

def scan_tower():
    weights_to_prune = copy.copy(weights)
    leaves = [prog for prog in children if children[prog] == []]
    while leaves:
        parent = pick_cherry(leaves)
        offspring = children[parent]
        offspring_weights = [weights_to_prune[child] for child in offspring]
        if offspring_weights[1:] == offspring_weights[:-1]:
            # update weight of parent
            weights_to_prune[parent] += sum(offspring_weights)
            # prune balanced
            for child in offspring:
                del parents[child]
                del weights_to_prune[child]
                if child in leaves:
                    leaves.remove(child)
            children[parent] = []
            leaves.append(parent)
        else:
            print('weights of the cherry: ', [weights[child] for child in offspring])
            print('total weights supported by the cherry: ', offspring_weights)
            print('parent of the cherry: ', parent)
            break



In [187]:

    
scan_tower()









    



weights of the cherry:  [1283, 184, 987, 15, 1284]
total weights supported by the cherry:  [1823, 1815, 1815, 1815, 1815]
parent of the cherry:  jfdck



In [164]:

    
1283 - (1823 - 1815)









    Out[164]:





1275