Sean McLemon | Advent of Code

2015-12-09 - All in a Single Night

(original .ipynb)

Puzzle input is a description of routes between destinations and their costs. Part one requires you to find the shortest path that touches every destination exactly once. Part two requires you to find the longest path that touches every destination exactly once.

from collections import defaultdict 
from math import inf

puzzle_input_str = open("./puzzle_input/day9.txt").read()

total_routes = 0

def parse_edge(edge_str):
    tokens = edge_str.split(" ")
    return (tokens[0], tokens[2], int(tokens[4]))


def shortest_path_from(src, nodes, routes, visited, cost, func=min):
    if len(nodes) == 0:
        return cost
        
    return func(
        shortest_path_from(neighbour, nodes.symmetric_difference({neighbour}), routes, visited.union({src}), cost + edge_cost, func)
        for (neighbour, edge_cost)
        in routes[src]
        if not (neighbour in visited)
    )


def part_one(input_str, func=min):
    routes = defaultdict(list)
    nodes = set()
    for line in input_str.split("\n"):
        src, dest, cost = parse_edge(line)
        routes[src].append((dest, cost))
        routes[dest].append((src, cost))
        nodes.add(src)
        nodes.add(dest)
    
    return func(
            shortest_path_from(src, nodes.symmetric_difference({src}), routes, {src}, 0, func)
            for src
            in nodes
    )


test_input_str = """London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141"""

assert 605 == part_one(test_input_str)

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

part one: 207

def part_two(input_str):
    return part_one(input_str, max)


assert 982 == part_two(test_input_str)


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

part two: 804