Retour à l’index

Puzzle: https://adventofcode.com/2025/day/8

J’ai directement un peu peur de l’explosion combinatoire qu’on aura dans la seconde partie, en lisant le début de l’énoncé. Je ne vais tout de même pas trop essayer d’anticiper: la partie deux peut toujours aller dans des directions très différentes, et ma stratégie en général consiste simplement à avancer pas à pas dans la partie un, pour récupérer un maximum ce qui est toujours utilisable.

On a une série de coordonnées en trois dimensions:

162,817,812
57,618,57
906,360,560
592,479,940
352,342,300
466,668,158
542,29,236
431,825,988
739,650,466
52,470,668
216,146,977
819,987,18
117,168,530
805,96,715
346,949,466
970,615,88
941,993,340
862,61,35
984,92,344
425,690,689

Ces coordonnées représentent des lampes qu’il faut connecter. Dans un premier temps, on nous demande de systématiquement connecter les lampes les plus proches. Chaque fois des lampes sont connectées, elles commencent à former un circuit. Les lampes appartiennent au même circuit si elles sont connectées, directement ou indirectement via d’autres lampes.

Préparation des données

Une vérification rapide des données réelles à résoudre me montre qu’on a 1000 points en tout. Suffisamment peu pour se permettre de calculer une matrice des distances, dans laquelle on va pouvoir piocher par ordre croissant. Dans un premier temps, récupérons simplement les coordonnées. Je vais créer un type pour faciliter la notation (ça n’a aucun impact sur l’exécution), et sinon le code est simple: on sépare par ligne, puis par , et on convertit les str en int.

type Vector = list[int]

def prepare_data(data: str) -> list[Vector]:
    rows = data.split('\n')
    points = [[int(i) for i in r.split(',')] for r in rows]
    return points

Il me faut ensuite une fonction pour calculer la distance euclidienne entre deux points. J’ai très envie d’utiliser numpy ou scipy qui me faciliterait ici grandement la vie, mais pour le Advent of Code j’essaie de rester sur la librairie standard autant que possible:

def dist(a: Vector, b: Vector) -> float:
    return sum((ai-bi)**2 for ai, bi in zip(a, b))**.5

Ce n’est pas la notation la plus claire, mais c’est très pythonesque. On parcourt ensemble les listes d’entiers élément par élément avec zip, on fait le carré des différences, on somme le tout, et on fait la racine carrée en mettant à la puissance 0.5.

On s’occupe ensuite de la matrice des distances. J’utilise itertools.combinations pour récupérer toutes les combinaisons possibles de points deux à deux. Juste pour éviter une double boucle for. Si j’ai des points ['a', 'b', 'c', 'd'], je recevrai alors les paires [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]. J’utilises ensuite sorted pour me faire un “argsort”, la fonction qui permet de trier les index d’un tableau sans trier le tableau lui-même. On peut faire ça en faisant le tri sur un tableau des indices (qu’on obtient avec range(len(tableau))), et en fournissant comme clé de tri une fonction lambda x: tableau[x]. On va grâce à ça trier selon els valeurs de tableau, mais on va récupérer les indices et pas les valeurs.

import itertools

def dist_matrix(points: list[Vector]) -> tuple[list[float], list[int]]:
    matrix = [dist(p1, p2) for p1, p2 in itertools.combinations(points, 2)]
    s = sorted(range(len(matrix)), key=lambda x: matrix[x])
    return matrix, s

Ma fonction renvoie la matrice des distances, et les indices ordonnés. Vérifions que tout fonctionne, et que je peux bien récupérer les paires de points les plus proches avec ça.

def main():
    points = load_input(8, '_sample', prepare_data)
    matrix, order = dist_matrix(points)
    print(order[0]) # print: 18

order[0] me renvoie l’indice 18. À quelle paire de point cet indice fait référence? L’ordre dans lequel les paires de points sont rangés dans matrix vient de itertools.combinations, donc je peux le réutiliser pour, au lieu de paires de points, récupérer des paires d’indices:

def main():
    # ...
    match_idx = list(itertools.combinations(range(len(points)), 2))
    print(match_idx[order[0]]) # (0, 19)

Grâce à ça, je peux voir que l’indice 18 fait référence à la paire de points (0, 19). Vérifions: si tout va bien, quand je récupères points[0] et points[19] et que je calcule la distance entre les deux, je devrais récupérer la même valeur que dans matrix[18], et cette valeur devrait être la valeur minimale dans matrix.

def main():
    # ...
    p0, p1 = match_idx[order[0]]
    print(dist(points[p0], points[p1]), matrix[order[0]], min(matrix))
    # 316.902, 316.902, 316.902

Ouf. Tout va bien, on peut passer à la suite.

Première partie, enfin!

On va enfin pouvoir se préoccuper du problème à résoudre: joindre progressivement les lampes pour former des circuits. En entrée, on aura la liste des points, l’ordre dans lequel on doit prendre les paires de points, et le nombre de jointures à faire (10 dans l’exemple, 1000 dans les vraies données). Je calcule d’abord les match_idxs dans la fonction ici, comme précédemment: je trouve ça plus logique de l’avoir ici que dans le main. J’initialise aussi un dictionnaire qui contiendra la référence de quels points se trouvent sur quels circuits. Et un compteur qui garde une trace du dernier identifiant de circuit donné:

def join_circuits(points: list[Vector], order: list[int], n_joins: int) -> dict[int, int]:
    match_idx = list(itertools.combinations(range(len(points)), 2))
    circuits: dict[int, int] = {}
    next_circuit = 1
    # ...

On va maintenant pouvoir commencer à former les circuits. On itère sur les paires de points dans l’ordre précalculé, et on regarde si on a déjà un numéro de circuit pour les points correspondants:

def join_circuits(points: list[Vector], order: list[int], n_joins: int) -> dict[int, int]:
    # ...
    for i in range(n_joins):
        best_match = order.pop(0)
        p0, p1 = match_idx[best_match]
        c0 = circuits.get(p0, None)
        c1 = circuits.get(p1, None)
        # ...

On va ensuite devoir traiter différents cas de figure:

• Si aucun des deux points n’est sur un circuit, on leur assigne next_circuit, qu’on incrémente ensuite de 1.
• S’ils sont déjà sur le même circuit, on n’a rien à faire.
• Si l’un des deux est sur un circuit mais l’autre pas, on met le nouveau point sur le circuit existant.
• S’ils sont tous les deux sur un circuit différent, on “fusionne” les circuits. Pour ça, il faut récupérer tous les autres points qui partagent le circuit du premier point, et on leur assigne le circuit du second (on pourrait faire l’inverse, ça ne change rien).

def join_circuits(points: list[Vector], order: list[int], n_joins: int) -> dict[int, int]:
    # ...
    for i in range(n_joins):
        # ...        
        if c0 is None and c1 is None:
            circuits[p0] = circuits[p1] = next_circuit
            next_circuit += 1
            continue
        if c0 == c1:
            continue
        if c0 is None:
            circuits[p0] = c1
            continue
        if c1 is None:
            circuits[p1] = c0
            continue
        # merge two different circuits
        toChange = []
        for key, value in circuits.items():
            if value == c0:
                toChange.append(key)
        for key in toChange:
            circuits[key] = c1
    return circuits

Après tout ça, on a un dictionnaire avec des “ids” de point et leur circuit correspondant. On nous demande de compter le nombre de points par circuit, et de multiplier les trois plus grands. Faisons ça dans deux fonctions distinctes, pour rester modulaire. Dans count_circuits, je vais réutiliser le truc d’hier avec le defaultdict pour initialiser automatiquement les compteurs à 0 sans devoir vérifier qu’une clé existe déjà. Pour chaque valeur de mon dictionnaire de circuits (c’est-à-dire chaque id de circuit) rencontré, j’incrémente le compteur. Je renvoie à la fin la liste des compteurs. Dans multiply_counts, je les trie par ordre décroissant (avec reverse=True dans sorted), je garde les n premiers, et je les multiplie à l’aide de math.prod.

def count_circuits(circuits: dict[int, int]) -> list[int]:
    circuit_counts = defaultdict(lambda: 0)
    for value in circuits.values():
        circuit_counts[value] += 1
    return list(circuit_counts.values())

def multiply_counts(circuit_counts: list[int], n: int) -> int:
    return prod(sorted(circuit_counts, reverse=True)[:n])

Dans le main, je bricole un peu pour que le nombre de connections à faire change selon qu’on regarde les données d’exemple ou les données réelles, et sinon j’appelle juste successivement mes différentes méthodes pour arriver au résultat de la première partie:

def main():
    suffix = '_sample'
    n_joins = 1000
    if suffix == '_sample':
        n_joins = 10

    points = load_input(8, suffix, prepare_data)
    _, order = dist_matrix(points)
    circuits = join_circuits(points, order, n_joins)
    counts = count_circuits(circuits)
    print(f"Part 1: {multiply_counts(counts, 3)}")

Deuxième partie: aller au bout

La deuxième partie nous demande de continuer le processus de jointures jusqu’à ce qu’on ait formé un seul circuit. Ca va: j’avais peur qu’on se retrouve face à un problème où on doit recalculer ou réordonner les distances à chaque itération, mais ici on peut continuer à fonctionner avec notre tableau de distances pré-calculé et pré-ordonné.

On commence par modifier la fonction de jointure pour que, si on ne lui fournit pas de nombre de jointures à faire, elle aille “jusqu’au bout”. Reste à définir proprement ce que ça veut dire. Dans le pire scénario, on devra parcourir toutes les correspondances, soit toute la liste order. On va donc assigner n_joins = len(order) si n_joins est None. La fonction va aussi maintenant retourner la dernière paire de points jointe, en plus du dictionnaire de circuits.

def join_circuits(points: list[Vector], order: list[int], n_joins: int | None = None) -> tuple[dict[int, int], tuple[Vector, Vector]]:
    # ...
    if n_joins is None:
        n_joins = len(order)

Mais en général, on va vouloir sortir de cette boucle plus tôt. Quand ça? Il faut que tous les points fassent partie d’un circuit, et qu’il n’y ait qu’un seul circuit. La première condition est donnée par len(circuits) == len(points), et la seconde doit tester qu’il n’y a qu’une seule valeur distincte dans circuits: len(set(circuits.values())) == 1. Je prends les valeurs de circuits (c’est-à-dire les identifiants de circuit), convertis en set (pour retirer les doublons), et je vérifie que la longueur de ce set est égale à 1 (un seul identifiant restant).

def join_circuits(points: list[Vector], order: list[int], n_joins: int | None = None) -> tuple[dict[int, int], tuple[Vector, Vector]]:
    # ...
    for i in range(n_joins):
        if (len(circuits) == len(points) and (len(set(circuits.values())) == 1)):
            break
        # ...

Le reste du code est inchangé, sauf le return:

def join_circuits(points: list[Vector], order: list[int], n_joins: int | None = None) -> tuple[dict[int, int], tuple[Vector, Vector]]:
    # ...
    return circuits, (points[p0], points[p1])

Pour la réponse finale, on doit maintenant multiplier les coordonnées en X des deux derniers points joints:

def main():
    suffix = '_sample'
    n_joins = 1000
    if suffix == '_sample':
        n_joins = 10

    points = load_input(8, suffix, prepare_data)
    matrix, order = dist_matrix(points)
    circuits, _ = join_circuits(points, order, n_joins)
    counts = count_circuits(circuits)
    print(f"Part 1: {multiply_counts(counts, 3)}")

    _, (p0, p1) = join_circuits(points, order)
    print(f"Part 2: {p0[0]*p1[0]}")

Et… ça ne marche pas?

Il m’a fallut un moment pour comprendre ce qui se passait. Pourtant, c’est une erreur assez traditionnelle en Python: oublier que quand on passe un objet mutable à une fonction, il risque fort de le muter! Dans ce cas-ci, lorsque join_circuits fait order.pop(0), il retire bien la première correspondance dans la liste passée en paramètre. Cette même liste qui est ensuite repassée à join_circuits pour la seconde partie, mais maintenant tronquée de ses n_joins premiers éléments.

La liste n’est pas si longue: on peut se permettre de faire une copie. Revoyons le main:

def main():
    suffix = '_sample'
    n_joins = 1000
    if suffix == '_sample':
        n_joins = 10

    points = load_input(8, suffix, prepare_data)
    matrix, order = dist_matrix(points)
    circuits, _ = join_circuits(points, order.copy(), n_joins)
    counts = count_circuits(circuits)
    print(f"Part 1: {multiply_counts(counts, 3)}")

    _, (p0, p1) = join_circuits(points, order.copy())
    print(f"Part 2: {p0[0]*p1[0]}")

Maintenant ça passe.

Solution sur codeberg