Advent of Code: Day 7

For Day 7, the challenge is to build a graph of running programs and dependencies and then adjust the weighting. My Python code is below:

import Queue
from collections import Counter
class Program:
    def __init__(self, line):
        self.parent = None
        line = line.split(" -> ")
        if len(line) > 1:
            self.children = [l.strip() for l in line[1].split(",")]
        else:
            self.children = []
        self.name, self.weight = line[0].split(" ")
        self.weight = int(self.weight.strip()[1:-1])

    @property
    def total_weight(self):
        self.total_weight = self.weight + sum(programs[c].total_weight for c in self.children)
        return self.total_weight

programs = {}

with open("input.txt", "r") as i:
    for line in i:
        program = Program(line.strip())
        programs[program.name] = program

# Set up parents
for key, program in programs.items():
    for child in program.children:
        programs[child].parent = program

program = programs.values()[0]
while program.parent:
    program = program.parent
print program.name

def find_incorrect_weight_parent(program):
    child_weights = [programs[c].total_weight for c in program.children]
    child_weights_counter = Counter(child_weights)
    if len(child_weights_counter.keys()) > 1:
        lst = child_weights_counter.most_common(2)
        weight_difference = lst[0][0] - lst[1][0]
        for c in program.children:
            if not programs[c].total_weight == lst[0][0]:
                return programs[c].weight + weight_difference
    return None

lst = []
queue = Queue.Queue()
queue.put(program)

while not queue.empty():
    program = queue.get()
    lst.append(program)
    for c in program.children:
        queue.put(programs[c])

lst.reverse()

for program in lst:
    weight = find_incorrect_weight_parent(program)
    if weight:
        print weight
        break

For the first part, I create a graph - loop through every program once to set up references to parents, and then just pick the first program and continue finding the parent until I find the root.

For the second part, the only tricky bit is that we need to start searching from the bottom. For this I use a breadth first search to build a list of programs ordered from top to bottom. I then reverse the list, and loop through until I find the first one with the incorrect weight.

Advent of Code runs every day up to Christmas, you should join in!.

Show Comments

Get the latest posts delivered right to your inbox.