4 - Le mot le plus long
Le but de cet exercice est de trouver le mot le plus long qu’il est possible de faire à partir d’un ensemble de lettres.
Énoncé:
Le but de cet exercice est de trouver la meilleure solution possible au jeu du mot le plus long. Pour cela, on va s’aider d’un dictionnaire enrichi de mots clés pour connaître les mots disponibles.
Ce fichier de dictionnaire est téléchargeable directement ou mieux en faisant une commande wget ou scp.
> scp votre_login@ssh.enseirb-matmeca.fr:~mfaverge/IF104/dico.utf8 votre_repertoire_de_travail
ou depuis votre répertoire de travail:
> wget https://cours-mf.gitlabpages.inria.fr/if104/exercices/dico/dico.utf8
Le premier objectif consiste à extraire du dictionnaire une liste de mot valides pour le jeu suivant les règles suivantes:
- Les mots composés sont exclus
- Les abréviations sont exclues
- Les mots autorisés sont:
- les noms (au singulier)
- les verbes uniquement à l’infinitif et au participe passé (sans féminin, ni pluriel)
- les autres mots: adjectifs, adverbes, pronoms, interjections (sans féminin, ni pluriel)
Pour extraire cette liste, il suffit de remarquer que chaque ligne du dictionnaire contient 3 colonnes:
- Le mot du dictionnaire
- L’infinitif du verbe, ou la forme au singulièr du nom/adjectif/…
- Une liste de mot-clés qui caractérisent le mot
Si on regarde plus attentivement, on constate qu’elle est formée comme suit:
Avec Type l’un des mots-clés suivant:
Abr, Adj, Adv, Con, Conj, Det, Int, Nom, Ono, Pre, Pro, QPro, Ver
Et la forme est une liste de mots-clés séparés par des + parmi lesquels on retrouve:
3Fem, 3Mas, Fem, Mas,
CPre, IFut, IImp, IPSim, IPre, ImPre, Imp, Inf, PC, PPas, PPre, SImp, SPre,
P1, P2, P3,
PL, SG,
InvGen, InvPL, PProRefl, Prox
Card, DemPro,
A l’aide des commandes bash avancées: grep, cut, awk, sort, ..., générer la liste des mots valides pour le jeu du mot le plus long.
Deuxième étape - Trouver un mot avec les lettres passées en arguments
Une fois que nous avons réussi à extraire la liste des mots valides dans un second fichier. Nous allons essayer de faire un scipt shell mot_le_plus_long.sh qui prend en argument une chaîne de caractères avec les lettres données et retourne le, ou les, mot(s) qui respectent les contarintes données dans la premières partie et qui contiennent tout ou un sous-ensemble des lettres passées en paramètre.
> ./mot_le_plus_long.sh tuz
zut
> ./mot_le_plus_long.sh xxxx
Pas de solutions
On réfléchira à réduire la taille du dictionnaire une seconde fois à l’aide de commandes shell si possible.
Si vous n’arrivez pas à une solution, vous pouvez suivre les étapes ci-dessous qui en proposent une. Le script final est fourni à la fin. A chaque étape, pour voir la solution, il vous suffira de cliquer sur “La solution ?".
Etape 1
Dans la suite, nous appellerons le mot en paramètre word.
- D’abord il faut filtrer les mots du dictionnaire en fonction des caractères de
word. On est sûr que le mot le plus long commence par une des lettres de word. Nous devons donc garder uniquement les mots qui commencent par une lettre de word.
La solution ?
grep ^[$1] nouveauDico.utf8 > tmpLettre
Etape 2
- Ensuite il faut garder uniquement les mots dont la longueur est inférieure ou égale à la longueur de
word.
La commande awk a une option length pour calculer le nombre de caractères d’un mot.
La solution ?
awk -v x=$n 'length($1)<=x {print}{}' tmpLettre > tmpSize > tmpLettre
Etape 3
- Comme on cherche le mot le plus long, autant trier dans l’ordre
décroissant du nombre de lettres.
La solution ?
cat tmpSize | awk '{print $1}' | awk '{print length(), $0 | "sort -r -n"}' | awk '{print $2}' > tmpSorted # on ne regarde que la première colonne, on ne garde pas la définition
Etape 4
-
Maintenant vous pouvez commencer à chercher le mot. Pour cela, il faut :
- Lire le dictionnaire ligne par ligne
- Regarder si toutes les lettres du mot courant sont dans
word
- Si c’est le cas alors on a trouvé le mot le plus long
- Sinon on passe au mot suivant
- A la fin, s’il ne reste plus de lignes dans le dictionnaire, alors il n’existe pas de mot le plus long.
- Vous pouvez optimiser encore plus la taille de votre dictionnaire. Si vous trouvez une lettre qui n’est pas dans
word, vous pouvez supprimer tous les mots du dictionnaire qui contiennent cette lettre.
-
Le script final est :
#on récupère le nombre de caractère dans le mot
n=$(echo $1 | wc -c | awk '{print $1}')
n=$(($n - 1))
#on insert un espace entre chaque lettre
word=$(echo $1 | sed 's/./& /g')
# maintenant on enlève du dictionnaire :
# 1- tous les mots qui ne contiennent pas au moins une lettre du mot
grep ^[$1] nouveauDico.utf8 > tmpLettre #ici on ne prend que les mots qui commencent par un des caractères du mot qu'on cherche. Mais ça tombe bien on est sûr que le mot qu'on cherche commence par un de ces caractères
# 2- les mots restants qui sont plus long que le nombre de lettres
awk -v x=$n 'length($1)<=x {print}{}' tmpLettre > tmpSize
# maintenant on trie selon la longueur des mots : le plut long sera
# en haut (comme ça on sort de la boucle dès qu'on trouve le match :
# on sait que c'est le plus long)
cat tmpSize | awk '{print $1}' | awk '{print length(), $0 | "sort -r -n"}' | awk '{print $2}' > tmpSorted ## on ne regarde que la première colonne, on ne garde pas la définition
found=0
while true
do
# on vérifie si chaque lettre du mot du dictionnaire est dans le mot word.
# On doit également vérifier que si une lettre apparaît plusieurs fois dans le mot du dictionnaire, alors elle apparaît autant de fois dans word
line=$(head -n 1 tmpSorted)
echo $line
echo $word > tmpWord
echo $word > tmpWord.back
dico=$line
for i in $(echo $dico | sed 's/./& /g')
do
if grep $i tmpWord > /dev/null;
then
found=1
echo "la lettre $i est trouvée"
sed -i "s/$i/-/" tmpWord
else
found=0
echo "letter $i from word $dico not in $word"
# on supprime tous les mots qui contiennent cette lettre tant qu'à faire
if ! grep $i tmpWord.back >/dev/null; # ici l'idée est que si on ne trouve pas la lettre dans le mot, autant supprimer tout les mots qui la contiennent du dictoinnaire. Mais il faut faire attention au lettres qui apparaissent deux fois (dans le mot paramètre du programme). Donc ce qu'on fait c'est testé si la lettre existe dans le mot en paramètre avant de la supprimer du dico
then
grep -v $i tmpSorted > tmp
mv tmp tmpSorted
else
sed -i '1d' tmpSorted ## si une lettre qui est dans le mot en paramètre, mais qui n'existe qu'une fois, on supprime la ligne
fi
break
fi
done
if [ $found -eq 1 ];
then
echo "Le mot le plus long est $line"
exit 0
fi
nb_lines=$(wc -l tmpSorted | awk '{print $1}')
if [ $nb_lines -eq 0 ];
then
echo "Il n'existe aucun mot avec ces lettres"
exit 1
fi
done