Résumé: les doublets consistent à changer un mot en un autre en modifiant une seule lettre à chaque étape pour faire un mot différent. C’est Lewis Caroll qui a mentionné la première fois cet exercice devenu un classique en informatique.

Mots-clés: chaîne de caractères, graphe, chemin le plus court, Dijkstra.

Solution : donnée en P5JS.

thèmes

de plus

Les échelles de mots

La création de doublets ou les échelles de mots consistent à changer un mot en un autre en modifiant une seule lettre à chaque étape, afin d’obtenir un mot différent. Les deux mots, au début et à la fin d’une telle chaîne, ont évidemment la même longueur. Ils ne doivent pas avoir de lettres identiques dans les mêmes positions. Tous les mots de la chaîne doivent être des noms communs, à l’origine, en anglais, les noms propres étant exclus. Par exemple: CAFE, CALE, CELE, TELE, TELS, TEES, THES. Une solution est dite parfaite si l’on trouve un nombre d’étapes égal au nombre de lettres différentes entre les deux mots. Si une solution parfaite n’est pas possible, la meilleure solution est donnée par la chaîne la plus courte.

Pour jouer ce jeu avec deux ou plusieurs joueurs, Lewis Carroll a inventé un ensemble de règles déterminant les scores et permettant de savoir qui gagne. La première mention de ce jeu apparaît dans le journal de Lewis Carroll le 12 mars 1878. Lewis Carroll était invité à un souper et il a inventé ce jeu, comme il le dit dans un pamphlet, pour deux jeunes filles qui n’avaient rien à faire. Certains programmes informatiques contenant tous les mots anglais peuvent être obtenus maintenant et d’autres ont été écrits pour rechercher les chaînes de longueur minimales en quelques secondes. La tâche est équivalente à rechercher les chemins les plus courts entre les points d’un graphe. Donald Knuth, l’informaticien célèbre de l’université de Stanford a construit un graphe dans lequel 5757, parmi les mots les plus courants de cinq lettres en anglais, noms propres exclus, sont représentés par des points, chacun joignant par une ligne chaque mot, lequel peut être obtenu en changeant seulement une lettre. Le graphe a 14’135 lignes. Une fois dans la mémoire de l’ordinateur, des programmes peuvent être écrits pour déterminer en une fraction de seconde le chemin le plus court joignant deux mots du graphe. Knuth a trouvé que les mots de trois lettres c’était trop simple et que les mots de six lettres c’était beaucoup moins intéressant, car il y en avait trop qui ne pouvaient pas être connectés entre eux.

La plupart des paires de mots de cinq lettres de la liste de Knuth peuvent être joints par des échelles. Certains, Knuth les appelle les mots aloof, parce que l’on ne peut pas trouver d’autres mots à partir de ceux-là. Dans son graphe, il en a trouvé 671, tels que les mots earth, ocean, below, sugar, laugh, first, third, ninth. En français, il existe 94 mots sans voisins: ACUL, AFRO, AGHA, AIGU, AMOK, ARUM, AZUR, BAHT, BODY, CIAO, CLUB, COSY, DAHU, DAUW, DESK, EDEN, ENOL, ENVI, EPAR, ETOC, EVOE, EXPO, FIQH, FISC, FOLK, FUGU, GIRL, GLEY, GOAL, GOLF, GOTH, GUNZ, GYMS, HADJ, HOPI, INFO, INOX, INTI, INUK, ITOU, IVRE, IXIA, JAZZ, JEEP, KEPI, KERN, KHOL, KICK, LABO, LAKH, LEHM, LULU, LYNX, MAAR, MAMY, MUON, NOEL, OEIL, OGAM, OHMS, ORAL, OUAH, OUED, OUZO, OVNI, PRAO, RUMB, SIKH, SMOG, SNOB, SUMO, THUG, THYM, UBAC, UGNI, ULNA, ULVE, UMMA, UNAU, VOEU, VOMI, WASP, WATT, WITZ, WURM, YAWL, YEYE, YORK, YUAN et YUKO.

Pour passer d'APE à MAN, Lewis Carrotl avait représenter l'échelle comme suit:

En Français, cela pourrait donner:

Il y a 103 paires de mots qui n’ont qu’un seul voisin. Lewis Carroll ajouta en 1892 une nouvelle règle qui permet de réarranger les lettres de n’importe quel mot. Avec cette nouvelle liberté, il est possible, par exemple, de passer du Roux à prof: ROUX, POUX, POIX, PRIX, PRIS, PROS et PROF.