Le but de ce projet 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 mains à papas,
voici les cinq solutions possibles :
- mains → maias → mayas → payas → papas
- mains → maias → manas → panas → papas
- mains → pains → paies → papes → papas
- mains → maias → matas → patas → papas
- mains → maias → raias → rapas → papas
Bien entendu, plus le mot de départ est long et plus la probabilité qu'il y ait de résultats est faible.
Cahier des charges
Votre programme doit, au lancement, charger le contenu du fichier mots.txt dans un tableau. Quelques remarques concernant ce fichier :
- il contient des verbes conjugués ainsi que des pluriels ;
- il ne contient que des caractères sans majuscules, sans accents et sans cédilles ;
- il contient aussi des mots contenant un tiret (considérés comme un seul mot).
Votre programme utilise ensuite cette liste pour générer un dictionnaire associant à chaque mot un tableau de mots suivants possibles. Une fois ce dictionnaire construit, la suite devient plus facile.
Le programme demande ensuite à l'utilisateur de saisir deux mots. Il affiche alors toutes les solutions possibles pour passer d'un mot à l'autre.
Exemple d'exécution
Voici un exemple d'exécution de votre programme (le texte affiché par le programme est en bleu, tandis que le texte entré par l'utilisateur est en noir) :
Saisir deux mots : 1) mains 2) papas 5 solutions trouvées : - mains maias mayas payas papas - mains maias manas panas papas - mains pains paies papes papas - mains maias matas patas papas - mains maias raias rapas papas
Pour aller plus loin (palier 4)
Une fois que vous avez atteint le palier 3 des fonctionnalités, voici quelques idées pour aller plus loin et atteindre le palier 4 :
- 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. Vous pouvez pour cela 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é ?