TP

Une chaîne reliant les mots 'ours' et 'cage'

Simulation

Nous commencerons avec une liste de 110 mots de 4 lettres :

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

À faire : récupérer cette liste et l'écrire dans un script que vous aurez nommé : dico.py

Construction du graphe

Le graphe sera un dictionnaire dont les clés seront les mots de la liste et les valeurs les mots de la liste qui ne diffèrent que d'une lettre ( sans changer de place) de la clé.

À faire :

Écrire ce nouveau script, dans le même dossier que dico.py

Ce script crée le graphe souhaité

1
import dico
2
3
def distance(mot1,mot2,k):
4
    # calcule la distance entre 2 mots de k lettres
5
    i = 0
6
    dist = 0
7
    while i < k:
8
        if mot1[i] != mot2[i]:
9
            dist = dist + 1
10
        i =i + 1
11
    return dist
12
13
def creation():
14
    # crée le dictionnaire des mots adjacents au mot de la liste
15
    g={}
16
    for element1 in dico.DICO:
17
        liste=[]
18
        for element2 in dico.DICO:
19
            if distance(element1,element2,4) == 1:
20
                liste.append(element2)
21
        g[element1] = liste
22
    return g
23
24
graphe=creation()
25
print(graphe['ours'])
pour le mot 'ours' on obtient la liste :
1
['durs', 'murs', 'purs']
Le parcours du graphe
Nous avons deux parcours possibles : le parcours en profondeur et le parcours en largeur.
Avec un parcours en profondeur
Rappelons l'algorithme
1
fonction parcours_profondeur(graphe,sommet):
2
   liste_visité <-- liste vide
3
   liste_fermé <-- liste vide
4
   p <-- pile
5
   on empile p avec le sommet
6
   on ajoute le sommet à la liste_visité
7
   tant que la pile n'est pas vide:
8
      tmp <-- le sommet de la pile
9
      voisins <-- liste des voisins de tmp
10
      si voisins n'est pas vide:
11
         v <-- un voisin au hasard
12
         on ajoute v à liste_visité
13
         on empile v
14
      sinon:
15
      liste_fermé <-- tmp
16
      on dépile p
17
   retourner liste_fermé
  • On a donc besoin d'une pile
  • Il nous faudra mémoriser les sommets visités et leur parents
  • Il nous faudra également un moyen de savoir si on a trouvé une solution
  • Il faudra également afficher le résultat...
Pour la pile, il suffit de récupérer la classe pile.
Pour les sommets visités et leur parents, on utilisera un dictionnaire : clé un sommet et sa valeur son parent.
Une variable booléenne fera l'affaire pour savoir si on a trouvé ou pas
On affichera le résultat sous forme d'une liste allant du premier sommet au dernier.
Voici le script :
1
###########################################################
2
#rajouter votre classe pile ici
3
4
5
############################################################
6
def Solution(end, parents):
7
    """
8
   
9
    """
10
    solution = []
11
    courant = end
12
    while courant != None:
13
        solution = [courant] + solution
14
        courant = parents[courant]
15
    return solution
16
17
18
19
def solve(graphe,depart, arrivee):
20
    
21
    """
22
    
23
    """
24
    candidats=Pile()
25
    candidats.empiler(depart)
26
    visite = dict()         
27
    visite[depart] = None
28
    trouve = False
29
    while candidats.vide()==False  and not trouve:
30
        courant = candidats.depiler()           
31
        if courant == arrivee:
32
            trouve = True
33
        else:
34
            for value in graphe[courant]:
35
                if not value in visite and not value in candidats.L:
36
                    visite[value] = courant
37
                    candidats.empiler(value)
38
    if trouve:
39
        return Solution(arrivee, visite)
40
    else:
41
        return None
42
    
43
solve(graphe,'ours','cage')
À faire :
Rajouter ce code à votre script ( n'oubliez pas d'y écrire votre classe pile)
et vérifier que la chaîne obtenue est :
1
['ours', 'purs', 'pers', 'pere', 'pore', 'tore', 'tors', 'mors', 'mars', 'mare', 'rare', 'rire', 'rime', 'lime', 'lame', 'pame', 'pape', 'tape', 'tale', 'sale', 'saie', 'gaie', 'gage', 'cage']
2
La solution obtenue n'est pas la plus courte puisque :
['ours', 'murs', 'mars', 'mare', 'mage', 'cage']
est une chaîne qui est bien plus courte ...
SimulationAvec un parcours en largeur
À faire :
Modifier le script précédent pour y appliquer un parcours en largeur et trouver la chaîne la plus courte...
SimulationAvec des mots de 6 lettres
Exercice
Sauriez-vous trouver l'échelle de mots la plus courte entre 'RENARD' et 'POULET' à partir du graphe se trouvant dans ce fichier : graphe6.py pour les pressés
Ou si vous n'êtes pas pressé depuis ce fichier qui contient la liste des mots de 6 lettres du dictionnaire du scrabble
ComplémentProlongement...Projets envisageables
S'intéresser au mots de 7 lettres
Trouver parmi les chaînes les plus courtes, la plus longue...
Le site qui a inspiré (très fortement) ce travail 
PrécédentPrécédentFin
AccueilAccueilImprimerImprimerRéalisé avec Scenari (nouvelle fenêtre)