#!/usr/bin/python

from itertools import permutations



def parse_input(lines):
    edges = {}

    for line in lines:
        words = line.split()
        x = words[0]
        y = words[2]
        d = int(words[4])

        if x not in edges:
            edges[x] = {}
        if y not in edges:
            edges[y] = {}

        edges[x][y] = d
        edges[y][x] = d

    return edges



def solve_partn(partn, lines):
    edges = parse_input(lines)
    nodes = list(edges.keys())

    # This is simply the famous travelling salesman problem,
    # so exhaustively trying all routes is the only solution.
    routes = permutations(nodes)
    totals = []
    for r in routes:
        t = 0
        for i in range(len(r) - 1):
            t += edges[r[i]][r[i + 1]]
        totals.append(t)

    if partn == 1:
        return min(totals)
    else: # partn == 2
        return max(totals)



def main():
    # Read distances (graph edges) from input text file
    with open("input.txt", "r") as f:
        lines = f.read().splitlines()

    print("Part 1 solution:", solve_partn(1, lines)) # 207 for me
    print("Part 2 solution:", solve_partn(2, lines)) # 804 for me



if __name__ == "__main__":
    main()