Objectifs

Utiliser la bibliothèque parcoursGraphede fonctions développées lors du TP Algorithmes de parcours de graphes pour relier entre eux des mots par une chaine de proximité.

Vous pouvez accéder à cette bibliothèque : ici

Consignes


Présentation du problème

On dispose d’une variable DICO qui est une liste de mots d’un même nombre de lettres.

Voici un exemple avec des mots de quatre lettres (cf dico.py) :

			
DICO = ["aime", "auge", "baie", "brie", "bris", "bure", "cage", "cale", "came", "cape",
"cime", "cire", "cris", "cure", "dame", "dime", "dire", "ducs", "dues", "duos",
"dure", "durs", "fart", "fors", "gage", "gaie", "gais", "gale", "gare", "gars",
"gris", "haie", "hale", "hors", "hure", "iris", "juge", "jure", "kart", "laie",
"lame", "lime", "lire", "loge", "luge", "mage", "maie", "male", "mare", "mari",
"mars", "mere", "mers", "mime", "mire", "mors", "muet", "mure", "murs", "nage",
"orge", "ours", "page", "paie", "pale", "pame", "pane", "pape", "pare", "pari",
"part", "paru", "pere", "pers", "pipe", "pire", "pore", "prie", "pris", "pues",
"purs", "rage", "raie", "rale", "rame", "rape", "rare", "rime", "rire", "sage",
"saie", "sale", "sape", "sari", "scie", "sure", "taie", "tale", "tape", "tare",
"tari", "tige", "toge", "tore", "tors", "tort", "trie", "tris", "troc", "truc"]
			
		

Le problème que l’on se pose est le suivant : on se donne deux mots m1 et m2 de DICO et on cherche à trouver, si elle existe, une suite de mots de DICO telle que :

Il s’agit donc de trouver une méthode de résolution qui permette de trouver une telle suite des mots permettant d’aller d’un mot de DICO à un autre. En Python, cela revient à écrire une fonction solve(depart,arrivee), paramétrée par deux chaînes de caractères depart et arrivee, dont le résultat est la liste de mots de la suite solution quand elle existe, et None dans le cas contraire.

Exemples :

			
>>> solve('ours', 'cage')
['ours', 'duos', 'ducs', 'dues', 'dure', 'bure', 'brie', 'baie', 'aime', 'came', 'cage']
		  
	  
			
>>> solve('ours', 'orme')
None
			
		

Etude à réaliser

Indications :

Auteur : Hugues Malherbe