Solution for Advent of Code 2015 - Day 9: All in a Single Night

Link to the puzzle text

Part 1

For this part, we need to solve the traveling salesman problem. A list of distances between cities are given and we need to find the shortest path containing all cities. To help with the algorithm later, I build up a matrix for all city-pairs and a list of all cities.

The number of cities is small, so I just brute-force it. Every possible path contatining all cities are generated by itertools.permutations(all_cities). For each path the total length is calculated and the shortest total length is saved and return later.

lowest_distance_yet = math.inf
for path in itertools.permutations(all_cities):
    total_distance = 0
    for i in range(len(path) - 1):
        a = path[i]
        b = path[i + 1]
        total_distance += distances[(a, b)]
    lowest_distance_yet = min(total_distance, lowest_distance_yet)

 

Part 2

For part 2, we need to find the longest path instead. The algorithm is the same, we just included saving the longest path length until now.

Link to my solutions