Day 9: All in a Single Night

In [96]:

    

import csv
from collections import defaultdict

def parse(path_to_input):
    distances = defaultdict(lambda: defaultdict(int))
    with open(path_to_input, 'rt') as f_input:
        csv_reader = csv.reader(f_input, delimiter=' ')
        for line in csv_reader:
            distances[line[0]][line[2]] = int(line[4])
            distances[line[2]][line[0]] = int(line[4])
    return distances


    

In [115]:

    

from copy import copy

class Clique(object):
    
    def __init__(self, distances):
        self.cities = list(distances.keys())
        self.distances = distances
        self.spath = defaultdict(lambda: defaultdict(float))
    
    def get_distance(self, a, b):
        return self.distances[a][b]
    
    def all_paths(self, root):
        """simple depth-first search from root"""
        results = []
        cities = copy(self.cities)
        cities.remove(root)
        # head of path, pending vertices, length travelled
        queue = [{'head': [root], 'pending': cities, 'length': 0}] 
        while queue:
            s = queue.pop()
            if s['pending'] == []:
                results.append((s['head'], s['length']))
            else:
                for city in s['pending']:
                    length = s['length'] + self.get_distance(s['head'][-1], city)
                    head = copy(s['head'])
                    head.append(city)
                    pending = copy(s['pending'])
                    pending.remove(city)
                    queue.append({'head': head, 'pending': pending, 'length': length})
        return results
    
    def best_path(self, short=True):
        res = []
        for city in self.cities:
            res += self.all_paths(city)
        if short:
            return sorted(res, key=lambda x: x[1])[0]
        else:
            return sorted(res, key=lambda x: x[1], reverse=True)[0]

def best_path(path_to_input, **kwargs):
    d = parse(path_to_input)
    g = Clique(d)
    return g.best_path(**kwargs)


    

In [116]:

    

best_path('inputs/input9.test1.txt')


    

    
Out[116]:





(['Belfast', 'Dublin', 'London'], 605)

In [117]:

    

best_path('inputs/input9.txt')


    

    
Out[117]:





(['Straylight',
  'Arbre',
  'Tristram',
  'Norrath',
  'Snowdin',
  'Tambi',
  'AlphaCentauri',
  'Faerun'],
 117)

In [118]:

    

best_path('inputs/input9.txt', short=False)


    

    
Out[118]:





(['Tambi',
  'Arbre',
  'Faerun',
  'Norrath',
  'AlphaCentauri',
  'Straylight',
  'Tristram',
  'Snowdin'],
 909)