Salut !

Je vous propose un exercice d'algorithmique assez classique mais pas forcément évident. Comme le programme traite un grand nombre de données, les points à optimiser apparaîtront clairement.

Principe

Le but est d'écrire un programme qui prend en entrée deux mots et qui retourne un chemin possible permettant de passer de l'un à l'autre en utilisant une chaîne de mots issus du dictionnaire. Pour passer d'un mot à l'autre, la seule opération autorisée est la substitution d'une lettre. On peut noter que tous les mots doivent être de la même longueur, ce qui élimine déjà une bonne partie du dictionnaire.

Par exemple, pour passer de cat à dog, voici une solution possible :

cat
cot
dot
dog

Et pour passer de code à line :

code
cone
lone
line

Ou encore :

code
bode
bade
bake
bike
dike
dine
line

Bien entendu, plus le mot de départ est long et moins la probabilité qu'il y ait de résultat est grande.

Aller plus loin

Pour ajouter de la difficulté, vous pourrez vous demander comment trouver la chaîne la plus courte et comment trouver toutes les chaînes possibles. Je vous conseille de vous renseigner sur les graphes et les algorithmes qui permettent de répondre à ce genre de problème plus facilement.

Pensez également à toutes les optimisations que vous pourriez apporter à votre programme : certaines méthodes sont bien plus rapides que d'autres pour déterminer si passer de « cat » à « cot » est une opération valide, par exemple. D'ailleurs, quelle serait la méthode la plus rapide pour trouver tous les mots valides que l'on peut utiliser après un mot donné ?

Vous pouvez aussi vous amuser en changeant les règles de passage d'un mot à l'autre (substitution de 2 lettres, ajout/retrait d'une lettre autorisés, etc.).

Ressources

Liste de 80 000 mots anglais (750 Ko), version UTF-8 de la liste originale.

Liste de 235 000 mots anglais (2.4 Mo) du projet UNIX — ne contient pas les mots au pluriel.

Voici comment vous pouvez construire votre liste de mots :

# coding: utf-8

words = open('brit-a-z.txt').read().splitlines()

Bonne chance à vous, je posterai quelques éléments de réponse plus tard !

-
Edité par Anonyme 1 mai 2013 à 21:02:30

Puisque je n'aurai pas beaucoup de temps les semaines prochaines, je poste maintenant une réponse possible au problème et quelques remarques sur la manière dont on pouvait l'aborder. Ne lisez pas tout si vous voulez chercher par vous-même !

Je vais décrire ici une solution à base de graphe car c'est sans doute la solution la plus simple. D'ailleurs, même si on ne sait pas ce qu'est un graphe, on s'en sert implicitement dans plusieurs algorithmes « naïfs ».

Préparer le terrain

On demande les deux mots à l'utilisateur, on lit le dictionnaire et on retient seulement les mots qui ont la même longueur que les mots entrés :

if __name__ == '__main__':

    import sys

    w1 = input('Word 1\n>>> ')
    w2 = input('Word 2\n>>> ')
    print('')
   
    words = set(w for w in open('brit-a-z.txt').read().splitlines()
                if len(w) == len(w1))

    if w1 not in words or w2 not in words:
        print('Invalid words')
        sys.exit(0)

Trouver les mots « enfants » valides

Le but est de connaître quels sont les mots auxquels on peut accéder à partir de chaque mot du dictionnaire. Par exemple, pour « cat », on doit avoir « cot, cut, fat, car, caw… », pour « dot » on doit avoir « cot, dog, lot, not… », etc.

Une fois qu'on aura ce dictionnaire de couples (mot parent, mots enfants), toutes les informations dont on a besoin s'y trouveront : si on veut passer de « cat » à « dog », on analysera tous les mots valides à partir de « cat », puis les mots valides à partir de chacun de ces mots et ainsi de suite. Il faut choisir avec soin la méthode qui convertira notre liste de mots en graphe car sa part dans les performances du programme est grande.

Première méthode

On a donc besoin d'une fonction qui permet de trouver les mots « enfants » valides pour un mot « parent ». Dans notre cas, la distance de Hamming correspond au problème puisqu'elle permet de déterminer le nombre de positions pour lesquelles les lettres contenues dans les deux mots sont différentes :

def hamming_distance(w1, w2):
    return sum(x != y for (x, y) in zip(w1, w2))

Dans notre problème, on veut que cette distance soit égale à 1 (= une seule substitution autorisée). On pourrait donc définir la fonction :

def is_valid_child(w_parent, w):
    return sum(x != y for (x, y) in zip(w_parent, w)) == 1  # True si 1, False sinon

Bien qu'elle soit élégante, cette méthode n'est pas optimisée dans la mesure où ne s'intéresse qu'à deux résultats : soit la distance vaut 1, soit elle vaut autre chose, et dans ce cas on n'a pas besoin de savoir quoi, ni donc de calculer le nombre exact de différences. Pour optimiser cela, on trouve plusieurs propositions ici et notamment celle-ci :

def is_valid_child(w_parent, w):
    if w_parent[0] != w[0]:
        return w_parent[1:] == w[1:]
    different = False
    for i in range(1, len(w_parent)):
        if w_parent[i] != w[i]:
            if different:
                return False
            different = True
    return different

Une solution serait donc de scanner le dictionnaire et pour chaque mot w_parent, boucler de nouveau sur le dictionnaire et sélectionner les mots w_child pour lesquels is_valid_child(w_parent, w_child) est vérifié. Mais avec des milliers d'entrées, cela peut être assez long.

Deuxième méthode

Toujours dans le même thread, quelqu'un propose de réfléchir autrement : au lieu de scanner tout le dictionnaire à la recherche de mots « enfants » valides, on pourrait générer toutes les combinaisons possibles à partir du mot parent et ne garder que celles qui sont dans le dictionnaire (on générera des mots qui n'ont aucun sens).

Voici la fonction qui génère toutes les combinaisons possibles :

import string

def potential_children(w_parent):
    combinations = set()
    for i in range(len(w_parent)):
        combinations.update(w_parent[:i] + l + w_parent[i+1:] for l in
                            string.ascii_lowercase if l != w_parent[i])
    return combinations

Cette méthode est la plus efficace et c'est donc celle que l'on va retenir. Néanmoins, cela met de côté les rares mots anglais accentués et ceux qui contiennent une apostrophe ou un trait d'union (on pourrait modifier la fonction pour les inclure).

Construire le graphe

On peut maintenant construire le graphe, le dictionnaire qui associera à chaque mot parent ses mots enfants valides.

def dict_graph(dictionary):
    def w_children(w_parent):
        return dictionary & potential_children(w_parent)

    return {w_parent: w_children(w_parent) for w_parent in dictionary}

La fonction w_children retourne l'intersection entre les mots du dictionnaire et tous les mots potentiels que l'on vient de générer, pour éliminer ceux qui n'existent pas.

Pour le moment, voici ce que l'on a :

import string


def potential_children(w_parent):
    combinations = set()
    for i in range(len(w_parent)):
        combinations.update(w_parent[:i] + l + w_parent[i+1:] for l in
                            string.ascii_lowercase if l != w_parent[i])
    return combinations


def dict_graph(dictionary):
    def w_children(w_parent):
        return dictionary & potential_children(w_parent)

    return {w_parent: w_children(w_parent) for w_parent in dictionary}


if __name__ == '__main__':

    import sys

    w1 = input('Word 1\n>>> ')
    w2 = input('Word 2\n>>> ')
    print('')
   
    words = set(w for w in open('brit-a-z.txt').read().splitlines()
                if len(w) == len(w1))

    if w1 not in words or w2 not in words:
        print('Invalid words')
        sys.exit(0)

    graph = dict_graph(words)

Trouver le plus court chemin

Une fois que l'on a notre graphe, on peut en faire tout et n'importe quoi (récupérer tous les chemins possibles pour un mot, les plus longs, les plus courts, etc.) grâce à des algorithmes génériques ou plutôt ciblés.

Pour trouver une chaîne de mots, on pourrait utiliser cet algorithme récursif très classique :

def find_path(graph, start, end, path=[]):
    path = path + [start]
    children = graph[start]
    if end in children:
        path.append(end)
        return path
    for child in children:
        if child not in path:
            newpath = find_path(graph, child, end, path)
            if newpath: return newpath
    return None

On commence en listant les mots enfants children du mot de départ start, si le mot end auquel on veut arriver est contenu dans les mots enfants, alors on retourne le chemin path et c'est terminé. C'est le meilleur des cas : par exemple, pour passer de « dot » à « dog », on se rend compte que « dog » fait déjà partie du premier niveau de mots voisins. Mais si ce n'est pas le cas, alors on passe au niveau inférieur et pour chaque mot enfant, on réitère l'algorithme en se souvenant à chaque fois du chemin parcouru grâce à path et on balaye ainsi les enfants de chaque enfant des enfants de chaque enfant (…) du mot de départ jusqu'à ce que l'on trouve end.

Cet algorithme fonctionne mais a l'inconvénient de s'interrompre dès qu'il trouve end par un chemin ou un autre et il n'est donc pas possible en l'état de trouver le chemin le plus court. En utilisant une version modifiée, on pourrait théoriquement y arriver, mais ce serait bien long.

Pour un graphe non pondéré (c'est notre cas puisque les mots voisins ont tous la même valeur, aucun n'est plus « voisin » que l'autre), l'algorithme de parcours en largeur est l'une des méthodes les plus efficaces pour trouver le chemin le plus court entre un nœud et un autre.

Voici une adaptation en Python trouvée ici :

from collections import deque

def bfs(graph, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(graph[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])


def shortest_path(graph, start, end):
    paths = {None: []}
    for parent, child in bfs(graph, start):
        paths[child] = paths[parent] + [child]
        if child == end:
            return paths[child]
    return None

Code final

Bien que les performances soient tout à fait acceptables, ce code est sans doute perfectible. C'est surtout la génération du graphe (avec la fonction dict_graph) qui prend du temps, mais il serait possible de le mettre en cache.

import string
from collections import deque
 

def potential_children(w_parent):
    combinations = set()
    for i in range(len(w_parent)):
        combinations.update(w_parent[:i] + l + w_parent[i+1:] for l in
                            string.ascii_lowercase if l != w_parent[i])
    return combinations
 
 
def dict_graph(dictionary):
    def w_children(w_parent):
        return dictionary & potential_children(w_parent)
 
    return {w_parent: w_children(w_parent) for w_parent in dictionary}
 
 
def bfs(graph, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(graph[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])


def shortest_path(graph, start, end):
    paths = {None: []}
    for parent, child in bfs(graph, start):
        paths[child] = paths[parent] + [child]
        if child == end:
            return paths[child]
    return None


if __name__ == '__main__':
 
    import sys
 
    w1 = input('Word 1\n>>> ')
    w2 = input('Word 2\n>>> ')
    print('')
    
    words = set(w for w in open('brit-a-z.txt').read().splitlines()
                if len(w) == len(w1))
 
    if w1 not in words or w2 not in words:
        print('Invalid words')
        sys.exit(0)
 
    graph = dict_graph(words)
    result = shortest_path(graph, w1, w2)

    if result is not None:
        print('\n'.join(result))
    else:
        print('No chain was found')

Aller plus loin avec networkx

Networkx est un module Python facile à prendre en main et qui regroupe plusieurs fonctions sur les graphes, notamment pour trouver les chemins les plus courts.

Voici comment on pourrait aboutir au même résultat avec networkx.shortest_path, en gardant les mêmes fonctions potential_children et dict_graph :

if __name__ == '__main__':

    import sys
    import networkx as nx

    w1 = input('Word 1\n>>> ')
    w2 = input('Word 2\n>>> ')
    print('')

    words = set(w for w in open('brit-a-z.txt').read().splitlines()
                if len(w) == len(w1))

    if w1 not in words or w2 not in words:
        print('Invalid words')
        sys.exit(0)

    graph = nx.from_dict_of_lists(dict_graph(words))
    try:
        result = nx.shortest_path(graph, w1, w2)
        print('\n'.join(result))
    except nx.exception.NetworkXNoPath:
        print('No chain was found')

Une autre fonction intéressante est networkx.all_shortest_paths, qui permet d'obtenir tous les chemins les plus courts si plusieurs ont la même longueur. Par exemple, pour aller de « cat » à « dog », il y a deux chemins en 4 étapes : [['cat', 'cot', 'cog', 'dog'], ['cat', 'cot', 'dot', 'dog']].

Et si vous voulez obtenir toutes les chaînes possibles, il y a networkx.all_simple_paths (cela peut être long selon les mots entrés — il existe sans doute d'autres bibliothèques plus performantes que l'on peut utiliser via Python).

-
Edité par Anonyme 1 mai 2013 à 21:43:19

Bonjour,

Je relance cet exercice si simple à exposer et si plein de surprises !
Je l'ai fait en utilisant un fichier des mots français  utilisé dans l'exo 'le mot le plus long' ; il a deux avantages : j'ai un meilleur vocabulaire français qu'anglais    et il est volumineux (plus de 350.000 mots) ce qui rend les tests de performance très significatifs.
Le fichier contient un mot par ligne, mots en minuscules sans accent ni cédille mais éventuellement avec un tiret.

Dans une première version de l'exercice faite sans regarder la solution de Graphox, je suis parti sur un parcours de l'arbre des possibles en vertical par appel récursif de la fonction de parcours ... très mauvaise idée : on cherche d'abord en profondeur, ce qui sort des chaînes longues avant d'explorer les plus courtes. Par ex. : passer de 'mon'  à 'ton' renvoie des suites de 10 ou 12 mots bien avant de trouver mon>ton !

Donc deuxième version donnée ci-dessous avec parcours horizontal utilisant une file (deque). C'est "naïf" mais en théorie, ça marche et on doit obtenir toutes les solutions. En pratique, c'est surtout très très très lent et inutilisable ! Mais je donne le code pour montrer les gains obtenus par les choix d'optimisation ultérieurs  qui constituent une partie très intéressante de l'exercice.

# exercice 'chaîne de mots'

from collections import deque

def successeurs(mot):
    """ retourne la liste des mots 'successeurs'
          càd différant d'une lettre de mot
         - le mot lui-même est exclu """
    global dico
    lst = []
    for i in range(len(mot)) :
        for x in 'abcdefghijklmnopqrstuvwxyz' :
            new_mot = "".join([mot[:i], x, mot[i+1:]])
            if new_mot == mot : continue
            if new_mot in dico :
                lst.append(new_mot)
    return lst

   
# __main__


while True :
    # lire les mots de départ et d'arrivée
    depart = input("Mot de départ ? ").lower()
    taille = len(depart)
    cible = input("Mot d'arrivée ? ").lower()
    if len(cible) != taille :
        print("... les mots doivent avoir la même longueur ...")
        continue

    # créer le sous-dictionnaire des mots de longeur 'taille'
    dico = []
    taille_p = taille + 1
    dico_name = "f:/Python34/dico.txt"
    with open(dico_name) as dico_file :
        for mot in dico_file :
            if len(mot) == taille_p :
                mot = mot.strip('\n')
                dico.append(mot)
    print("dictionnaire de ",len(dico), " mots de ", taille, " lettres")

    # vérifier que depart et cible sont dans le dico !
    if (not depart in dico) or (not cible in dico) :
        print(" un mot : '", depart,"' ou '", cible, "' n'est pas dans le dictionnaire")
        continue
    
    # on y va !

    trouves = []                # liste des solutions trouvées
    sol_long = 400000           # taille de la plus petite solution trouvée
    fifo = deque()              # file des suites restant à tester
    fifo.appendleft([depart])
    # boucle de vidage de fifo
    while fifo :
        # lire la suite à traiter suivante
        suite = fifo.pop()
        long = len(suite)
        if long > sol_long : continue # la suite est déjà trop longue : au suivant
        # on approfondit la recherche :
        #  ajouter les successeurs du dernier mot dans la file
        for elt in successeurs(suite[-1]) :
            if elt in suite : continue  # si boucle sur le mot : passer au suivant
            new = suite.copy()
            new.append(elt)
            if elt == cible :       # bingo !
                trouves.append(new)
                sol_long = min(long, sol_long)
                continue            # on continue pour trouver toutes les solutions
            else :
                fifo.appendleft(new)    # ajouter dans la file des suites à traiter

    # fin de parcours :
    if trouves :
        for suite in trouves :
            print("Solution : ", " ".join(suite))
    else :
        print("pas de solution trouvée ...")

La version ci-dessus sort rapidement mon > ton > toi, mais prend plusieurs dizaines de minutes par ex. pour passer de 'larder' à 'gerber' car les mots de 6 lettres sont assez nombreux (14000) et chacun a pas mal de successeurs (mots différant d'une seule lettre du parent). Il est temps d'optimiser !

Éléments d'analyse pour l'optimisation :
Dans le dico des mots français proposé, pour une longueur de mot donnée, le nombre de mots dans le dico et le nombre moyen de successeurs par mot sont :
lettres  nb de mots    moy. successeurs
  2              81             10.59
  3            427               9.68
  4          1799               7.59
  5          5891              6.09
  6        13901              4.57
  7        25455              3.44
  8        38095              2.69
  9        47249              2.06
 10       49687              1.58
 11       45224              1.20
 12       35713              0.93
 13       24771              0.69
 14       15006              0.53
   ...

Première amélioration : le calcul des successeurs
C'était pas évident au départ, mais à l'analyse,  le calcul des successeurs apparaît comme un point critique pour la performance. On a deux pistes d'amélioration : diminuer le nombre d'appels à la fonction 'successeurs' et rendre cette fonction plus performante.
Une première idée - donnée dans la solution de Graphox - est de pré-calculer le dictionnaire {mot: liste de ses successeurs} . C'est judicieux pour les mots ayant beaucoup de successeurs car dans le parcours des possibles, beaucoup de mots reviennent plusieurs fois. Ex. polir, polie, polis, polit : chacun est successeur de tous les autres. Avec un pré-calcul du dico des successeurs, le calcul des fils se fera une seule fois. Alors que si on cherche les fils pendant le parcours de l'arbre, les successeurs de 'polis' de l'ex. seront calculés comme descendance à partir de ...polir>polis, ...polie>polis, ...polit>polis ... sans compter ...colis>polis etc
Par contre, pour les mots longs, c'est l'inverse. Par exemple pour un mot de dix lettres : il y a peu de successeurs par mot (1.6 en moyenne) mais il y a beaucoup de mots (49700), chacun nécessitant un grand nombre de combinaisons pour trouver un de ses successeurs ( 26**10 !). On rencontrera peu de successeurs pendant le parcours de l'arbre des descendants mais le calcul initial du dictionnaire pour tous les mots de 10 lettres est très lourd.
Au final la solution s'impose : calculer les successeurs d'un mot la première fois qu'on le rencontre dans le parcours de l'arbre et mémoriser le résultat dans le dictionnaire (partiel donc) {mot : liste de successeurs} ; ensuite, lorsqu'on retombe sur ce mot, on réutilise la liste déjà calculée.
On évite de calculer les successeurs pour des mots qu'on ne rencontrera jamais (de plus en plus fréquents quand la taille des mots augmente), mais dans le traitement des anneaux (l'exemple polie, polis, polit, polir) on ne fait le calcul qu'une fois. Le gain est assez spectaculaire dans tous les cas.

Deuxième amélioration :
Pour calculer les successeurs, j'utilise la même méthode combinatoire que la solution de Graphox, mais mon code initial est nettement plus lent ! J'ai repris l'idée (et le code) de remplacer dans cette partie les listes par des sets, et c'est bien plus rapide !
Je ne comprends pas bien cette grosse différence : l’implémentation des opérations sur les sets semble bien plus performante que celle des listes ? ou est-ce parce que j'utilise des boucles for explicites dans le cas des listes ? ou les deux ?

Troisième amélioration :
Dans le parcours de l'arbre des chaînes possibles : le nombre de cas à explorer explose rapidement avec la profondeur de recherche.
En gros, si on a en moyenne n successeurs pour chaque mot, le nombre des possibles à la profondeur p est de l'ordre de n**p.
En observant que la relation successeur est commutative ( a successeur de b <=> b successeur de a ), on voit qu'on peut effectuer la recherche en partant aussi bien du premier mot que du dernier.
L'idée est de parcourir simultanément les arbres des possibles pour le mot de départ A et le mot d'arrivée B jusqu'à rencontrer un ensemble de descendants communs. Si x est un de ces mots communs, la chaîne cherchée est A>>x suivie de l'inverse de  B>>x
La profondeur de recherche sera divisée par 2, soit en gros 2*n**(p/2) possibles traités contre n**p avant.
Par ex. la recherche solder >> agites donne des solutions de profondeur 9 :
        Solution :  solder souder bouder bouter bluter blutes elutes elites alites agites
Le nombre estimé de possibles est d'environ 1.900 contre 87.000 dans la version précédente.
Ou encore 'deraperons' >> 'retournent' : p= 26 (et oui !), n= 1.58 pour 10 lettres -> 770 possibles contre 14.250
    (Une solution pour le fun :  deraperons decaperons decalerons decelerons deceleront decelerant decelerait recelerait revelerait revererait repererait reperdrait rependrait repondrait retondrait retordrait remordrait remoudrait recoudrait recourrait refourrait refourrant refourrent defourrent defournent detournent retournent )

De plus on peut utiliser des 'set's et enfin, s'il n'y a pas de solution, le test d'arrêt 'plus aucun nouveau descendant' pour A ou B est d'autant plus rapide que les mots ont moins de successeurs.

Nouvelle version :

# exercice : chaîne de mots
# version : - parcours de l'arbre horizontal
#           - parcours simultané en partant de chacun des deux mots à relier
#              traité par deux instances de la classe SousArbre
#           - calcul des successeurs par combinatoire et sets
#           - dictionnaire des successeurs partiel créé on the fly
DEBUG = 1   #  flag pour les prints de debugging : 0= aucun, >0 = level 1, 2...
dico_name = "f:/Python34/dico.txt"  # path du fichier dictionnaire source

class SousArbre :
    """ gére le parcours des deux sous-arbres A et B
        dans des variables d'instances
            - 'filiation' dictionnaire
                  key = mot,
                  value (list) = chaine de mots depuis A ou B jusqu'à mot inclus
           - 'descends' = ensemble des mots descendant de la racine
    """
    def __init__(self, racine):
        """ racine = mot racine du sous-arbre (depart ou cible) """
        self.descends = {racine}                
        self.filiation = { racine : [racine] }
        self.root = racine

    def next_gen(self) :
        """ générateur :
                crée une nouvelle génération de descendants pour le sous-arbre
                retourne le nbr de nouveaux descendants créés (0 si plus aucun)
            - met à jour les filiations depuis la racine pour chaque nouveau descendant
            - met à jour l'ensemble des descendants de la racine
        """
        last_gen = {self.root}    # init avec la racine
        pop_desc = 1
        while pop_desc :
            new_gen = set()
            for mot in last_gen :
                new_gen.update(successeurs(mot))
                self.update_filiation(mot)
            new_gen -= self.descends        # on ne garde que les nouveaux venus
            self.descends.update(new_gen)   # mettre à jour la population des descendants
            pop_desc = len(new_gen)
            yield pop_desc
            last_gen = new_gen

    def update_filiation(self, mot):
        """ crée une filiation pour tous les successeurs de mot"""
        for smot in successeurs(mot) :
            if not smot in self.filiation.keys() :
                lst = self.filiation[mot].copy()
                lst.append(smot)
                self.filiation[smot] = lst
        return

# fonctions communes :
def successeurs(parent):
    """ retourne tous les successeurs du mot 'parent' (parent exclu) """
    global dico
    global dico_succ
    if parent in dico_succ :
        return dico_succ[parent]
    combinations = set()
    for i in range(len(parent)):
        combinations.update("".join((parent[:i], car, parent[i+1:]))
                for car in 'abcdefghijklmnopqrstuvwxyz')
    succs = dico & combinations
    succs.discard(parent)
    dico_succ[parent] = succs
    return succs

def debug(*args, level = 1) :
    """ outil de debugging """
    if DEBUG >= level : print(*args)

# __main__

while True :
    # lire les mots de départ et d'arrivée
    depart = input("Mot de départ ? ").lower()
    if depart == '' : break
    cible = input("Mot d'arrivée ? ").lower()
    taille = len(depart)
    if len(cible) != taille : 
        print("... les mots doivent avoir la même longueur ...")
        continue

    # dico = sous-ensemble de tous les mots de longeur 'taille'
    dico = set()
    taille_p = taille + 1
    with open(dico_name) as dico_file :
        for mot in dico_file :
            if len(mot) == taille_p and (not '-' in mot) :
                dico.add(mot.strip('\n'))    # enlever le \n 
    debug("dictionnaire de ",len(dico), " mots de ", taille, " lettres")

    # vérifier que depart et cible sont dans le dico !
    if (not depart in dico) or (not cible in dico) :
        print("'", depart,"' ou '", cible, "' n'est pas dans le dictionnaire !")
        continue
    
    # on y va !
    
    dico_succ = dict()  # pour un mot utilisé comme clé, donne le set de ses successeurs
    A = SousArbre(depart)
    B = SousArbre(cible)
    generateurA = iter(A.next_gen())
    generateurB = iter(B.next_gen())
    
    traiterA = 1          # bascule : 1 = traiter A, 0 = traiter B
    while True :
        delta_pop = (next(generateurA) if traiterA else next(generateurB))
        debug("nb nouveaux successeurs : ", delta_pop)
        communs = A.descends & B.descends
        if (delta_pop == 0) or communs : break   # arrêt si plus de descendant
                                                 #  ou s'il y a des 'communs'
        traiterA ^= 1     # basculer la recherche sur l'autre sous-arbre et boucler  

    # fin de parcours :
    if communs : # chaque elt de 'communs' est au centre d'une chaîne solution
        for mot in communs :
            lst = B.filiation[mot].copy()
            lst.pop() # 'mot' à la fois dans filiations de A et B
            lst.reverse()
            soluce = A.filiation[mot].copy()
            soluce.extend(lst)
            print("Solution : ", " ".join(soluce))
        debug("profondeur : ", len(soluce))
    else :
        print("... pas de solution entre '", depart, "' et '", cible, "'", sep='')

Au final, le programme dans cette nouvelle version s'avère très performant dans tous les cas avec un code relativement réduit !

Encore qq pistes d'améliorations éventuelles :
- tel que, on obtient plusieurs solutions mais pas toutes : il faudrait admettre plusieurs suites possibles dans les dictionnaires 'filiation' entre la racine et un descendant x alors que là on n'en garde qu'une, la première rencontrée.
- enfin, mon code Python me paraît assez moyen (manips de liste laborieuses ...) !

-
Edité par Rozo2 28 août 2014 à 17:10:43