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 et qui est devenu un classique en informatique.
Mots-clés : chaîne de caractères, graphe, chemin le plus court.
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 : cold, cord, card, ward, warm1 . 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. Deux mots, bares et cores sont connectés à 25 autres mots. Il n’y en a pas d’autres.
Il y a 103 paires de mots qui n’ont qu’un seul voisin tels que odium - opium, monade - gonade2 . 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 iron au lead : iron, icon, coin, corn, cord, lord, load, lead.
Il est difficile, mais il n’est pas impossible de former une phrase à partir d’une chaîne de mots. Le 26 juillet 1879, dans Vanity Fair, Lewis Carroll pose la question : comment passer de why à not3 ? La solution de Lewis Carroll est why, who, woo, wot et not.
Le but de l’exercice consiste donc à construire des doublets pour la langue française. Bien évidemment, il est impossible de taper tous les mots de cinq lettres en français, à moins de pouvoir les obtenir par un moyen quelconque, en revanche, on peut construire un programme informatique qui, étant donné une liste de mots, soit capable de vérifier si les règles sont respectées et de proposer, éventuellement, des solutions dans un mini-dictionnaire.
Pour résoudre le problème, il est conseillé de procéder comme Donald Knuth il faut prendre un certain nombre de mots de même taille, construire un graphe indiquant les liens pour passer d’un mot à l’autre en ne changeant qu’une seule lettre et, ensuite, construire le chemin le plus court, en prenant éventuellement tous les chemins qui mènent d’un mot à un autre. A titre d’exemple, on peut même s’entraîner sur des mots anglais et retrouver les problèmes parmi les plus intéressants de Lewis Carroll. Exemple : rogue vers beast, quell vers bravo, kettle vers holder, etc. Dans un article du journal World Ways, consacré aux amusements linguistiques, on trouve également les problèmes suivants : tram vers mart, flog vers golf et loops vers spool.
Les solutions sont en cours de développement... Toute solution est la bienvenue.