Advent of code

◂ 25 décembre 2023 

  Snowverload : Trouver les trois pseudo-isthmes d'un graphe (trois arêtes qui séparent le graphe en deux parties connexes si on les enlève)

ssr: mkc zdr

ccn: hpf drf dnr

bpf: krh stt

lhf: zpv

1. code.py

import itertools, math
from collections import defaultdict   # pratique, mais on risque de ne pas voir qu'une valeur qui aurait dû être initialisée ne l'a pas été

Sommet = str
Aretes = dict[Sommet,set[Sommet]]
Arete = tuple[Sommet,Sommet]

f = open("input.txt", 'r', encoding='utf-8')
lines = [line[:-1] for line in f.readlines()]

MAX_DIST = len(lines) ** 2

aretes:Aretes  = defaultdict(set)
for line in lines:
    sommet, *voisins = line.split()
    sommet = sommet[:-1]
    aretes[sommet].update(voisins)
    for v in voisins:
        aretes[v].add(sommet)

sommets = list(aretes.keys())


""" Statistiquement, les isthmes d'un graphe suffisamment grand doivent être les plus utilisés quand on passe d'un sommet à un autre
    par le chemin le plus court. On gardera les 5 passages les plus usités"""

### Il aurait été plus propre d'utiliser dist:dict[Arete,int] et dist[u,v] au lieu de dist[u][v]
### mais c'était 4 fois plus lent.

### Calculer les chemins entre toutes les paires de points (prend du temps, mais heureusement en O(n³) avec Floyd-Warshall
def floyd_warshall() -> tuple[dict[Sommet,dict[Sommet,int]], dict[Sommet,dict[Sommet,Sommet]]]:
    dist: dict[Sommet,dict[Sommet,int]] = defaultdict(lambda:defaultdict(lambda:MAX_DIST))
    prev: dict[Sommet,dict[Sommet,Sommet]] = defaultdict(defaultdict)
    for u,t in aretes.items():
        for v in t:
            dist[u][v] = 1   # The weight of the edge (u, v)
            dist[v][u] = 1   # The weight of the edge (u, v)
            prev[u][v] = u
            prev[v][u] = v
    for v in sommets:
        dist[v][v] = 0
        prev[v][v] = v
    n = 0
    for k in sommets:
        n += 1
        print(f"    {n}/{len(sommets)}...")
        for i in sommets:
            for j in sommets:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    prev[i][j] = prev[k][j]
    return dist,prev

def get_path(u:Sommet, v:Sommet, prev:dict[Sommet,dict[Sommet,Sommet]]) -> list[Sommet]:
    if prev[u][v] is None:
        return []
    path = [v]
    while not u == v:
        v = prev[u][v]
        path.append(v)
    return path[::-1]

_, calcul_origines = floyd_warshall()


### Calculer les passages les plus fréquentés
nb_passages: dict[Arete,int] = defaultdict(int)
for u,v in itertools.combinations(sommets, 2):
    for s1,s2 in itertools.pairwise(get_path(u, v, calcul_origines)):
        if s1>s2:
            nb_passages[(s2,s1)] += 1
        else:
            nb_passages[(s1,s2)] += 1
nb_passages = sorted(list(nb_passages.items()), key=lambda x:x[1], reverse=True)
print("Nb d'utilisations des passages les plus fréquentés:", [v for _,v in nb_passages[:10]])

        

### Vérifier si les passages fréquentés coupent bien en deux parties distinctes
def nb_comp_connexes(sommets:list[Sommet], aretes:Aretes, interdits:tuple[Arete,...]) -> list[int]:
    sommets = set(sommets)
    nb_cc: list[int] = []
    while sommets:
        a_traiter = set([sommets.pop()])
        done = set()
        while a_traiter:
            s = a_traiter.pop()
            done.add(s)
            for voisin in aretes[s]:
                if (s,voisin) in interdits or (voisin,s) in interdits:
                    continue
                if voisin not in done:
                    a_traiter.add(voisin)
                    sommets -= set([voisin])
        nb_cc.append(len(done))
    return nb_cc


### ...quitte à utiliser après d'autres passages un peu moins fréquentés que les trois premiers.
interdits: tuple[Arete,...]
for interdits in itertools.combinations([arete for arete,_ in nb_passages[:10]], 3):
    nb_cc = nb_comp_connexes(sommets, aretes, interdits)
    if len(nb_cc) > 1:
        texte_nb_cc = list(map(str, nb_cc))
        texte_nb_cc[-2] += " et " + texte_nb_cc[-1]
        texte_nb_cc = ', '.join(texte_nb_cc[:-1])
        print("Trouvé parties connexes de taille:", texte_nb_cc)
        print("Réponse partie 1:", math.prod(nb_cc))
        # Pas besoin d'un break, c'est rapide et on termine pour vérifier l'unicité de la réponse