Jour 11 - Traversée récursive

Après mon échec cuisant du jour 10, malgré une seconde journée passée dessus, j’ai voulu jeter un oeil en vitesse, le soir, sur le jour 11.

Et, sans doute parce que j’ai autant sué sur le pathfinding sur le précédent, la solution ici m’est venue immédiatement, et m’a pris seulement quelques minutes à coder, ce qui fait bien plaisir.

Le problème à résoudre est une traversée de graphes – c’est-à-dire exactement la façon dont j’ai tenté de modéliser le problème d’hier!

Préparation des données

On a une série de noeuds connectés de façon directionnelle. Il n’y a pas de cycles. Les données sont encodées ainsi:

D’abord, l’identifiant du noeud, puis :, puis les identifiants des noeuds auxquels il est connecté. Si je traduit l’exemple en graphique grâce à mermaid, ça donne:

L’objectif est d’aller de you à out, et de compter le nombre de chemins possibles pour y parvenir.

On à affaire à un graphe, je vais créer une petite classe pour gérer sa construction. Chaque noeud sera identifié par un str, et on a un dictionnaire pour lier cet identifiant aux identifiants connectés.

class Graph:
    def __init__(self):
        self.nodes: dict[str, set[str]] = defaultdict(lambda: set())
    
    def add(self, node: str, connections: set[str]) -> None:
        self.nodes[node] = connections

Et on va le construire en lisant l’input et en séparant les lignes comme il faut. La seule petite subtilité par rapport à ce qu’on a fait les autres jours est que j’utilise strip() pour retirer l’espace entre le : et les identifiants.

def prepare_data(data: str) -> Graph:
    rows = data.split('\n')
    g = Graph()
    for row in rows:
        key, elements = row.split(':')
        connections = set(elements.strip().split(' '))
        g.add(key, connections)
    return g

Première partie: compter les chemins

Si le noeud xxx est connecté aux noeuds yyy et zzz, et qu’on connait le nombre de chemins allant de yyy à out, et de zzz à out, quel est le nombre de chemins de xxx à out? C’est la somme des deux.

def count_all_paths(graph: Graph, start: str, end: str) -> int:
    if start == end:
        return 1
    return sum(count_all_paths(graph, n, end) for n in graph.nodes[start])

def main():
    graph = load_input(11, '', prepare_data)
    print(f"Part 1: {count_all_paths(graph, 'you', 'out')}")

Un peu plus de chemins

On ne s’arrête évidemment pas là: maintenant, on a un autre point de départ (svr), le même point d’arrivée, mais on doit cette fois-ci compter uniquement les chemins contenant dac et fft, dans n’importe quel ordre. Il y a un autre exemple pour illustrer tout ça, mais on va passer ici, le principe est le même. La fonction récursive en elle-même change peu. Je veux cette fois-ci garder trace de si je suis déjà passé par dac et fft, et ne compter que ces chemins-là.

Je vais donc garder les “noeuds à visiter” dans un set, duquel on va retirer les éléments au fur et à mesure qu’on les traverse. Lorsqu’on arrive à end, on ne compte le chemin que s’il ne reste plus de noeuds à visiter.

def count_all_paths_with(graph: Graph, start: str, end: str, contains: set[str]) -> int:
    if start == end:
        return 1 if len(contains) == 0 else 0
    return sum(count_all_paths_with(graph, n, end, contains - {start}) for n in graph.nodes[start])

Si start n’est pas dans contains, contains - {start} renverra juste contains. S’il était dedans, il renverra contains sans le start.

def main():
    # ...
    print(f"Part 2: {count_all_paths_with(graph, 'svr', 'out', {'dac', 'fft'})}")

On est de nouveau dans un truc beaucoup trop long. Mais cette fois-ci le problème est simple à résoudre. On repasse énormément de fois dans les mêmes noeuds, avec ces appels récursifs, donc on peut rajouter un cache: une fois qu’on a la réponse pour un noeud, plus besoin de la recalculer. Pour pouvoir utiliser cache, il faut que tous les arguments de la fonction soient hashable. On va donc faire quelques petites modifications au passage:

class Graph:
    # ... 
    def __hash__(self):
        return id(self)

@functools.cache
def count_all_paths(graph: Graph, start: str, end: str) -> int:
    # ...

@functools.cache
def count_all_paths_with(graph: Graph, start: str, end: str, contains: frozenset[str]) -> int:
    # ...

def main():
    # ...
    print(f"Part 2: {count_all_paths_with(graph, 'svr', 'out', frozenset({'dac', 'fft'}))}")

Le __hash__ de Graph utilise simplement son id, soit son “adresse” en mémoire (raccourci très imprécis, je sais, mais c’est l’idée).

Cette fois-ci, le résultat est presque instantané, et on comprend pourquoi ça prenait du temps avant: sur mon input, j’ai 603 chemins pour la première partie, et 380 961 604 031 372 chemins pour la seconde. C’est beaucoup.