Sean McLemon | Advent of Code

2017-12-24 - Electromagnetic Mat

(original .ipynb)

import math
from collections import defaultdict

puzzle_input_str = open("puzzle_input/day24.txt").read()
test_input_str = """0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10"""


def parse_input(input_str):
    input_lines = input_str.split("\n")
    graph = defaultdict(dict)
    
    for line in input_lines:
        a_str, b_str = line.split("/")
        a, b = int(a_str), int(b_str)
        graph[a][b] = line
        graph[b][a] = line
                    
    return graph


def calculate_path_strength(path):
    strength = 0
    for component in path:
        port_a, port_b = component.split("/")
        strength += int(port_a) + int(port_b)
    return strength


def strongest_path(current, graph, path):
    candidates = [
        component
        for component
        in graph[current]
        if not (graph[current][component] in path)
    ]
    
    if len(candidates) == 0:
        return calculate_path_strength(path)
    
    return max(
        strongest_path(component, graph, path.union([graph[current][component]]))
        for component
        in candidates
    )


def part_one(input_str):
    return strongest_path(0, parse_input(input_str), set())


assert 31 == part_one(test_input_str)

print("part one:", part_one(puzzle_input_str))

part one: 1906

def longest_path(current, graph, path):
    candidates = [
        component
        for component
        in graph[current]
        if not (graph[current][component] in path)
    ]
    
    if len(candidates) == 0:
        return len(path), calculate_path_strength(path)
    
    return max(
        longest_path(component, graph, path.union([graph[current][component]]))
        for component
        in candidates
    )


def part_two(input_str):
    length, strength = longest_path(0, parse_input(input_str), set())
    return strength


assert 19 == part_two(test_input_str)

print("part two:", part_two(puzzle_input_str))

part two: 1824