Advent of Code 2015 Day 9

— Day 9: All in a Single Night —

Santa has some new locations to visit, and we need to find the shortest path.

What is the distance of the shortest route?

import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming

with open('data-2015-09.txt', 'r') as f:
    distances = f.read().splitlines()

Create lists which we might be able to iterate over

dist_list = [x.split(' ') for x in distances]

dist_arr = np.zeros((8,8))
k = 0

for i in range(8): 
    for j in range(8):
        if j > i: 
            dist_arr[i, j] = dist_list[k][4]
            dist_arr[j, i] = dist_list[k][4]
            k += 1

That looks good, now let’s use the solver

https://github.com/fillipe-gsm/python-tsp

dist_arr[:, 0] = 0
permutation, distance = solve_tsp_dynamic_programming(dist_arr)
permutation
distance

# 117

np.float64(117.0)

— Part Two —

What is the distance of the longest route?

# """Module with a brute force TSP solver"""
from itertools import permutations
from typing import Any, List, Optional, Tuple

from python_tsp.utils import compute_permutation_distance


def solve_tsp_brute_force(
    distance_matrix: np.ndarray,
) -> Tuple[Optional[List], Any]:

    # Exclude 0 from the range since it is fixed as starting point
    points = range(1, distance_matrix.shape[0])
    # set initial distance at zero not at np.inf
    best_distance = 0.0
    best_permutation = None
    for partial_permutation in permutations(points):
        # Remember to add the starting node before evaluating it
        permutation = [0] + list(partial_permutation)
        # compute from the array
        distance = compute_permutation_distance(distance_matrix, permutation)
        # add the starting point on the end
        perm = permutation + [0]
        # remove the shortest leg from the route
        adj_dist = distance - min([dist_arr[perm[x],perm[x+1]] for x in range(7)])
        # update our best distance based on the adjusted distance
        if adj_dist > best_distance:
            best_distance = adj_dist
            best_permutation = permutation
    # return
    return best_permutation, best_distance

Steal the code from python-tsp

permutation, distance = solve_tsp_brute_force(dist_arr)
permutation
distance

# 909

np.float64(765.0)

Original code assumes that the route starts from node 0 which is not necessarily the case. Calculating the longest TSP and removing the shortest out of that route may not necessarily be correct.

We need to set each node as the start node and then iterate to see which is the longest route? Or we can adjust the overall calculated distance to remove the shortest leg in the route and use that adjusted distance as our longest not-visit-every-house Santa route.