Advent of code

◂ 23 décembre 2024 ▸

  LAN Party : Trouver des cliques (sous-graphes complets) de taille 3, puis de taille maximale.

ri-uo

nv-of

hh-nb

ll-le

1. code.py

from itertools import combinations

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

edges = dict()

for line in lines:
    vertex1, vertex2 = line.split('-')
    edges.setdefault(vertex1, []).append(vertex2)
    edges.setdefault(vertex2, []).append(vertex1)


#### PART 1
nb1 = sum( 1
           for vertex in edges.keys() 
           if vertex.startswith('t')
               for v,w in combinations(edges[vertex], 2)
               if w in edges[v]
                  and not ((v.startswith('t') and v < vertex) or (w.startswith('t') and w < vertex)) # ne pas compter les choses à double
         )
print("Réponse partie 1:", nb1)


#### PART 2

def find_clique_of_size(clique_size, ids_by_degrees, edges):
    for id in ids_by_degrees:
        if len(edges[id]) < clique_size:     # optim pas utile avec l'input du problème
            return None
        for subset_voisins in combinations(edges[id], clique_size - 1):
            if all(subset_voisins[i2] in edges[subset_voisins[i1]]
                   for i1 in range(len(subset_voisins)-1)
                   for i2 in range(i1+1, len(subset_voisins))) :
                return (id,) + subset_voisins
    return None


ids_by_degrees = [id for _,id in sorted( ((len(edges[id]), id) for id in edges.keys()), reverse=True)]
max_degree = len(edges[ids_by_degrees[0]])

for clique_size in range(max_degree, 1, -1):
    clique = find_clique_of_size(clique_size, ids_by_degrees, edges)
    if clique:
        break
    else:
        print("No clique size", clique_size)

print("Réponse partie 2:", ','.join(sorted(clique)))