<jupyter_start><jupyter_text>Day 9: All in a Single Night Day 9.1We will implement a simple DFS algorithm<jupyter_code>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
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)<jupyter_output><empty_output><jupyter_text>Test<jupyter_code>best_path('inputs/input9.test1.txt')<jupyter_output><empty_output><jupyter_text>Solution<jupyter_code>best_path('inputs/input9.txt')<jupyter_output><empty_output><jupyter_text>Day 9.2<jupyter_code>best_path('inputs/input9.txt', short=False)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13427268959801078, 'fraction_numerical': 0.00870285951098218, 'mean_word_length': 2.6246246246246248, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '446189', 'license': 'MIT', 'n_tokens_mistral': 774, 'n_tokens_neox': 756, 'n_words': 157, 'path': '2015/ferran/day9.ipynb', 'repo_name': 'bbglab/adventofcode', 'size': '2413'}