Le problème

Partie 1

Le jour 12 marque l’utilisation pour la première fois des graphes. Dans notre exploration des grottes sous-marines, notre seule échappatoire est de visiter toutes les cavités se trouvant dans ces grottes et ainsi de la cartographier.

Commençons par analyser un peu l’exemple de jeu de données :

start-A
start-b
A-c
A-b
b-d
A-end
b-end

Cette liste ressemble beaucoup à une liste d’arêtes, que l’on pourra donc reconstruire assez facilement pour représenter notre graphe. Puisque l’on va de cavité en cavité, ces arêtes sont bidirectionnelles, et voici un exemple de représentation du graphe correspondant :

    start
    /   \
c--A-----b--d
    \   /
     end

La spécificité de cet exercice repose sur le fait qu’il y a des petites et grandes cavités, représentées respectivement par des lettres minuscules ou majuscules. Les grandes cavités peuvent être visitées autant de fois qu’on le veut, tandis que les petites ne peuvent être visitées qu’une seule fois. Cette information est l’information cruciale de cette première partie. En effet, il faudra que notre algorithme prenne en charge les petites cavités déjà visitées pour ne pas y retourner une seconde fois.

Description de l’algorithme

Comme indiqué précédemment, le jeu de données est formaté de telle façon qu’il est assez simple de le transformer en une liste d’arêtes. Pour ma part, j’ai décidé de représenter ces arrêtes sous la forme d’un tuple (origine, destination).

Ainsi, le jeu de données illustré précédemment devient :

[(start, A), (start, b), (A, c), (A, b), (b, d), (A, end), (b, end)]

Souvent, lorsque l’on parle parcours de graphe, on va penser à un algorithme récursif que l’on appliquera à chaque nœud. Voici un algorithme incomplet, mais qui donne une idée de la fonction récursive que l’on souhaite implémenter. L’idée est de créer l’arbre des parcours possibles, et d’en calculer les terminaisons obtenues avec le mot-clé end :

# Il faut encore déterminer les paramètres de cette fonction récursive
function cherche_chemin(): 
    Si le noeud courant est 'end':
        On retourne 1 (c'est la fin d'un chemin possible)
    Sinon:
        On cherche toutes les arêtes contenant le noeud courant
        On retire toutes les arêtes contenant des cavités déjà visitées
        compteur <- 0
        Pour chaque arête dans ces arêtes :
            compteur <- compteur + cherche_chemin() # Paramètres à déterminer
        On retourne compteur

Il faut donc identifier les paramètres d’une telle fonction. J’en ai utilisé trois :

• edges, qui est la liste des arêtes construit à partir du fichier de données ;
• current_node, qui représente la cavité où l’on se trouve actuellement ;
• visited, qui représente un ensemble de petites cavités déjà visitées.

On peut donc transformer un peu notre pseudocode pour lui donner une allure un peu plus pythonesque :

def search_path(edges, current_node, visited):
    if current_node == 'end'
        return 1
    paths <- Ensemble des arêtes contenant 'current_node'
    paths <- paths - Ensemble des arêtes contenant une cavité de 'visited'
    count <- 0
    for path in paths:
        destination <- L'élément de path qui n'est pas égal à 'current_node'
        count += search(path_current_node, visited)
    return count

On commence à se rapprocher de la solution finale, mais il manque encore les aspects suivants :

• On n’ajoute aucune valeur à visited
• Lorsque l’on change de branche dans notre parcours d’arbre des chemins possibles, il faut faire attention aux valeurs des cavités stockées dans visited.

Le premier point peut-être résolu si on fait appel aux expressions régulières. En effet, les cavités mineures sont écrites avec des lettres minuscules (apparemment, une ou deux lettres). On peut donc écrire un pattern qui va vérifier si le nom de la cavité est composé uniquement de lettres minuscules ou pas, avant de l’ajouter dans l’ensemble visited.

Le second point est très important. En effet, en passant visited en paramètre de notre fonction récursive, toutes les modifications (et donc, tous les ajouts) que l’on fera sur cet ensemble seront préservées. Mais cela risque de fausser notre algorithme. Avec l’exemple donné par l’énoncé, on pourrait avoir le cas suivant :

1. Je pars de start.
2. Je vais dans b, et je parcours toutes les branches possibles partant de b.
3. Une fois que j’ai parcouru toutes les issues de b, je vais maintenant regarder A. Mais si j’ai ajouté b et d dans l’ensemble des cavités parcourues, celles-ci ne pourront pas être parcourues lorsque je pars de A quand bien même je n’y suis pas encore passé.

Dans l’algorithme de cette première partie, il faudra donc utiliser des copies pour ne pas modifier les valeurs stockées dans visited à chaque parcours de nouvelle branche. La solution finale est donnée juste après, dans la section qui suit.

Solution proposée

import re


pattern = re.compile('[a-z]+')


def parse_input_data():
    with open('input-large', 'r') as data:
        return [tuple(line.split('-')) for line in data.read().splitlines()]


def search_path(edges, current_node, visited):
    if current_node == 'end':
        return 1
    paths = {edge for edge in edges if current_node in edge}
    paths -= {edge for edge in edges for node in visited if node in edge}
    count = 0
    copy_visited = visited.copy()
    if pattern.match(current_node):
        copy_visited.add(current_node)
    for path in paths:
        end = path[1] if current_node == path[0] else path[0]
        count += search_path(edges, end, copy_visited)
    return count


def solve_part_one():
    edges = parse_input_data()
    count = search_path(edges, 'start', set())
    print(count)

Partie 2

La seconde partie de l’exercice nous explique qu’il est désormais possible de visiter une seule cavité mineure deux fois. L’algorithme est donc assez proche de ce qui a pu être proposé en Partie 1, mais ce changement a des effets sur les arêtes que l’on doit retirer ou non à chaque étape de l’algorithme.

Si on reprend l’algorithme utilisé en Partie 1, on se rend compte que :

1. La cavité start est conforme à l’expression régulière ;
2. Il faut trouver un moyen de déterminer si une cavité quelconque a été déjà visitée deux fois. Si c’est le cas, cela implique que toutes les cavités mineures sont désormais interdites d’accès. Sinon, une cavité mineure quelconque peut être visitée une seconde fois.

Gérer le premier point est assez simple. Gérer le second nécessite d’introduire une variable supplémentaire pour déterminer s’il est encore possible d’explorer une cavité mineure une seconde fois. J’obtiens la solution suivante, que je vais décrire en insérant des commentaires dans le code :

def search_path(edges, current_node, visited, visited_twice):
    if current_node == 'end':
        return 1
    
    paths = {edge for edge in edges if current_node in edge}
    # Puisque 'start' remplit les conditions de la regex, mais qu'il n'est pas 
    # possible d'y retourner, on retire toutes les arêtes contenant 'start' à
    # la liste des chemins possibles.
    if current_node != 'start':
        paths -= {edge for edge in edges if 'start' in edge}
    # Si une cavité mineure a été visitée deux fois, cela implique qu'il n'est 
    # plus possible de visiter une cavité mineure déjà visitée. On se retrouve
    # dans la même situation q'en partie 1.
    if visited_twice:
        paths -= {edge for edge in edges for node in visited if node in edge}
    count = 0
    copy_visited = visited.copy()
    if pattern.match(current_node):
        # Si `current_node` est une cavité mineure déjà visitée, mais qu'il est
        # encore possible de visiter une cavité mineure une seconde fois, alors
        # cela signifie qu'on est en train de la parcourir pour la seconde fois.
        # Et on va donc changer la valeur de `visited_twice` pour indiquer qu'il
        # ne sera plus possible de visiter les cavités mineures dans `visited`.
        if current_node in visited and not visited_twice:
            visited_twice = current_node
        else:
            copy_visited.add(current_node)
    for path in paths:
        end = path[1] if current_node == path[0] else path[0]
        # Si la destination n'est pas déjà visitée ou qu'elle a déjà été visitée
        # mais qu'il est possible de la visiter une seconde fois, alors on la 
        # visite encore une fois.
        if end not in visited or (end in visited and not visited_twice):
            count += search_path(edges, end, copy_visited, visited_twice)
    return count
    
    
def solve_part_two():
    edges = parse_input_data()
    count = search_path_part_two(edges, 'start', set(), None)
    print(count)

Les difficultés

Les graphes, c’est toujours assez compliqué à gérer. Cela nécessite de penser à la bonne représentation en termes de structures de données (dictionnaire, matrice d’adjacence, liste d’arêtes, etc.), mais aussi d’appliquer des algorithmes pas triviaux non plus.

Ici, on cherche finalement à compter le nombre de feuilles dans l’arbre des chemins possibles. On aurait pu le créer, puis le parcours en entier pour chercher les terminaisons. J’ai opté pour un calcul récursif du nombre de terminaison en même temps que je construis l’arbre.

Mon point de vue sur les fonctions récursives, c’est que ce n’est vraiment pas intuitif. J’aime bien alors simplifier le problème au maximum. Et pour l’exercice d’aujourd’hui, la question qui se pose est la suivante : “Qu’est-ce que je fais pour chaque nœud ?” Pour aujourd’hui, la réponse à cette question est :

• Si c’est un nœud end, alors je suis arrivé à une terminaison et je retourne 1 pour incrémenter mon compteur de terminaison.
• Sinon, il faut déterminer les chemins valides (i.e., ceux que l’on peut encore visiter selon les règles des Parties 1 ou 2), et les visiter les nœuds correspondants.

À la récursivité s’ajoute la difficulté du passage par référence d’un ensemble permettant justement de garder en mémoire les cavités mineures déjà visitées. Comme expliqué précédemment, il faudra donc penser à créer des copies de l’ensemble visited à chaque étape de la récursivité pour être sûr d’explorer tous les chemins possibles.

Je crois savoir que les exercices du weekend sont souvent plus difficiles que ceux des journées ouvrés précédents. L’exercice d’aujourd’hui, bien que très intéressant sur les concepts mis en œuvre, ne vient pas me contredire en tout cas.