Advent of code

◂ 9 décembre 2015 ▸

  All in a Single Night :

1. code.py
2. optimisations

import itertools

def parse(filename):
    f = open(filename, 'r')
    linesOrig = list(map(str.strip, f.readlines()))

    distances = {}
    villes = []

    for line in linesOrig:
        tokens = line.split(' ')
        cityFrom = tokens[0]
        cityTo = tokens[2]
        dist = int(tokens[4])
        if not cityFrom in villes:
            distances[cityFrom] = {}
            villes.append(cityFrom)
        if not cityTo in villes:
            distances[cityTo] = {}
            villes.append(cityTo)
        distances[cityFrom][cityTo] = dist
        distances[cityTo][cityFrom] = dist
    return distances, villes

def gras(s):
    # codes pour le terminal
    return '\x1b[1m' + s + '\x1b[0m'

def calcDist(villes, distances):
    d = sum([distances[villes[i-1]][villes[i]] for i in range(1, len(villes))])
    return d


distances, villes = parse('input.txt')
print(gras("Villes:"), villes)
#print(gras("Distances:"), distances)


minDist = None
minParcours = None
maxDist = None
maxParcours = None

for parcours in itertools.permutations(villes):
    # parcourir les A -> ... -> B et pas les B -> ... -> A symétriques
    if parcours[0] > parcours[-1]:
        continue
    d = calcDist(parcours, distances)
    if minDist == None or d < minDist:
        minDist = d
        minParcours = parcours
    if maxDist == None or d > maxDist:
        maxDist = d
        maxParcours = parcours

print(gras("Dist minimale:"), minDist, "pour", minParcours)
print(gras("Dist maximale:"), maxDist, "pour", maxParcours)