Sean McLemon | Advent of Code

2017-12-07 - Recursive Circus

(original .ipynb)

test_puzzle_input = """pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)"""


real_puzzle_input = open("puzzle_input/day7.txt").read()


def parse_weight_str(weight_str):
    return int(weight_str[1:][:-1])

def parse_line(line):
    line_parts = line.split(" -> ")
    
    name_and_weight = line_parts[0]
    name, weight_str = name_and_weight.split(" ")
    weight = parse_weight_str(weight_str)
    
    children = None
    if len(line_parts) == 2:
        children = [ child.strip() for child in line_parts[1].split(",") ]
    
    return (name, weight, children)

def build_parents_tree(puzzle):
    parent_of = {}
    for node, weight, children in puzzle:
        if children:
            for child in children:
                parent_of[child] = node
    return parent_of

def find_root(start_node, parent_of):
    current = start_node
    while current != None:
        if not (current in parent_of):
            return current
        
        current = parent_of[current]
    raise Exception("Something has gone seriously wrong")

def part_one(puzzle_input):
    puzzle = [parse_line(line_str) for line_str in puzzle_input.split("\n")]
    parent_of = build_parents_tree(puzzle)
    start_node = list(parent_of.keys())[0]
    
    return find_root(start_node, parent_of)
    
# parse_line("fwft (72) -> ktlj, cntj, xhth")
# parse_line("gyxo (61)")
print("part one:", part_one(real_puzzle_input))

part one: eqgvf

def build_main_tree(puzzle):
    children_of = {}
    for node, _, children in puzzle:
        children_of[node] = children
    return children_of

def build_weight_tree(puzzle):
    weight_of = {}
    for node, weight, _ in puzzle:
        weight_of[node] = weight
    return weight_of        

def build_total_weights(node, total_weights, children_of, weight_of):
    total = weight_of[node]
    
    if children_of[node]:
        for child in children_of[node]:
            total += build_total_weights(child, total_weights, children_of, weight_of)
    
    total_weights[node] = total
    return total


def odd_one_out(node, total_weight_of, children_of):
    
    children = children_of[node]
    
    if not children:
        return node
    
    if len(set([total_weight_of[child] for child in children])) == 1:
        return node      
    
    children_and_weights = list(
        sorted([ (child, total_weight_of[child]) for child in children ], key=lambda x:x[1])
    )
    
    if children_and_weights[0][1] != children_and_weights[1][1]:
        # if first is different from second, it's the odd one out
        return odd_one_out(children_and_weights[0][0], total_weight_of, children_of)
    else:
        # otherwise the last one will be
        return odd_one_out(children_and_weights[-1][0], total_weight_of, children_of)


def part_two(puzzle_input):
    puzzle = [parse_line(line_str) for line_str in puzzle_input.split("\n")]
    parent_of = build_parents_tree(puzzle)
    children_of = build_main_tree(puzzle)
    weight_of = build_weight_tree(puzzle)
    
    start_node = list(parent_of.keys())[0]
    root = find_root(start_node, parent_of)    
    
    total_weight_of = {}
    build_total_weights(root, total_weight_of, children_of, weight_of)
    
    weirdo = odd_one_out(root, total_weight_of, children_of)
    target_weight = [total_weight_of[child] for child in children_of[parent_of[weirdo]] if total_weight_of[child] != total_weight_of[weirdo]][0]
    
    return weight_of[weirdo] + (target_weight - total_weight_of[weirdo])
    
print("part two:", part_two(real_puzzle_input))

part two: 757