IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Think Julia


précédentsommairesuivant

9. Étude de cas : jeux de mots

Ce chapitre présente la deuxième étude de cas, qui consiste à résoudre des énigmes lexicales en recherchant des mots présentant certaines propriétés. Par exemple, nous trouverons les palindromes les plus longs en anglais et nous chercherons des mots dont les lettres apparaissent dans l'ordre alphabétique. Un autre plan de développement de programmes sera présenté : la réduction à un problème précédemment résolu.

9-1. Lecture de listes de mots

Pour les exercices de ce chapitre, nous utiliserons une liste de mots français. Celle qui convient le mieux à notre objectif est une liste de mots collectée et mise dans le domaine public par Christophe Pallier dans le cadre du projet de dictionnaire Français-GUTenberg de Christophe Pythoud [8]. Il s'agit d'une liste de 336 531 mots encodés en UTF-8. Un navigateur comme Firefox permet d'enregistrer directement ce fichier sous le nom mots_FR.txt (par exemple).

Ce fichier est en mode texte brut, tout éditeur de texte peut l'afficher. Cependant, ce fichier est lisible depuis Julia. La fonction intégrée open prend le nom du fichier comme paramètre et retourne un flux de fichier utilisable pour lire le fichier.

 
Sélectionnez
1.
2.
julia> fin = open("/home/chemin_vers_fichier/mots_FR.txt")
IOStream(<file /home/chemin_vers_fichier/mots_FR.txt>)

fin est un flux de fichier utilisé pour l'entrée et lorsqu'il n'est plus nécessaire, il doit être fermé avec close(fin).

Julia fournit plusieurs fonctions de lecture, dont readline qui lit les caractères du fichier jusqu'à arriver à une NEWLINE et retourne le résultat sous forme de chaîne :

 
Sélectionnez
1.
2.
julia> readline(fin)
"a"

Le premier mot de cette liste est a (conjugaison du verbe « avoir » à la troisième personne au singulier du présent de l'indicatif).

Le flux de fichiers garde une trace de l'endroit où il s'est arrêté, si bien qu'appeler à nouveau readline conduit à l'affichage du mot suivant :

 
Sélectionnez
1.
2.
julia> readline(fin)
"à"

Parce que le fichier peut être parcouru dans une boucle for, ce programme lit le fichier mots_FR.txt et imprime chaque mot, un par ligne :

 
Sélectionnez
1.
2.
3.
for line in eachline("/chemin_vers_fichier/mots_FR.txt")
    println(line)
end

Le dernier mot affiché est « zythums ».

9-2. Exercices

9-2-1. Exercice 9-1

Écrivez un programme qui lit mots_FR.txt et n'imprime que les mots de plus de 20 caractères (sans compter les espaces).

9-2-2. Exercice 9-2

Le roman La Disparition est un lipogramme écrit par Georges Perec (membre de l'Oulipo) en 1968 et publié en 1969. Il tire son originalité du fait que ses 300 pages (nombre variable selon les éditions) ne comportent pas une seule fois la lettre e, pourtant généralement la plus utilisée dans la langue française.

Écrivez une fonction appelée hasno_e qui retourne true si le mot passé en argument ne contient pas la lettre e.

Modifiez votre programme par rapport à la section précédente pour imprimer seulement les mots qui ne contiennent pas de e et calculez-en le pourcentage sur la liste.

9-2-3. Exercice 9-3

Écrivez une fonction nommée avoids qui prend un mot et une chaîne de lettres interdites en arguments, et qui retourne true si le mot n'en utilise aucune.

Modifiez votre programme pour demander à l'utilisateur d'entrer une chaîne de lettres interdites, puis imprimez le nombre de mots qui ne contiennent aucune de ces lettres. Pouvez-vous trouver une combinaison de 5 lettres interdites qui exclut le plus petit nombre de mots ?

9-2-4. Exercice 9-4

Écrivez une fonction nommée usesonly qui prend un mot et une chaîne de lettres, et qui retourne true si le mot ne contient que des lettres de cette série. Pouvez-vous faire une phrase (autre que « Hoe alfalfa ») en utilisant uniquement les lettres acefhlo ?

9-2-5. Exercice 9-5

Écrivez une fonction appelée usesall qui prend un mot et une chaîne de lettres obligatoires, et qui retourne true si le mot utilise toutes les lettres obligatoires au moins une fois. Combien y a-t-il de mots qui utilisent toutes les voyelles aeiou ? Que diriez-vous de aeiouy ?

9-2-6. Exercice 9-6

Écrivez une fonction appelée isabecedarian qui retourne true si les lettres d'un mot apparaissent dans l'ordre alphabétique (les lettres doubles sont admises). Combien existe-t-il de mots abécédaires ?

9-3. Recherche

Tous les exercices de la section 9.2Exercices présentent un point commun. Ils peuvent être résolus avec le modèle de recherche dans les chaînes (voir la section 8.8Recherche dans les chaînes). L'exemple le plus simple est le suivant :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
function hasno_e(word)
    for letter in word
        if letter == 'e'
            return false
        end
    end
    true
end

La boucle for traverse les caractères du mot passé en argument. Si la lettre e est détectée, le programme retourne immédiatement false. Sinon, il passe à la lettre suivante. Si le programme sort de la boucle normalement, cela signifie que la lettre e n'a pas été décelée et, par conséquent, le programme retourne true.

Cette fonction pourrait être reformulée de manière plus concise en utilisant l'opérateur ∉ (\notin TAB), mais la version de base illustre bien la logique du schéma de recherche.

La fonction avoids est une version plus générale de hasno_e, bien qu'elle présente la même structure :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
function avoids(word, forbidden)
    for letter in word
        if letter ∉ forbidden 
            return false
        end
    end
    true
end

Le programme peut retourner false dès qu'il trouve une lettre interdite passée comme second argument. S'il arrive au bout de la boucle, le programme retourne true.

La fonction usesonly est analogue, si ce n'est que le sens de la condition est inversé :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
function usesonly(word, available)
    for letter in word
        if letter ∉ available
            return false
        end
    end
    true
end

Au lieu d'une série de lettres interdites, nous avons une série de lettres permises. Si nous trouvons une lettre qui n'est pas présente dans un mot, le programme retourne false.

useall est similaire, sauf que nous inversons le rôle du mot et de la série de lettres :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
function useall(word, required)
    for letter in required
        if letter ∉ word
            return false
        end
    end
    true
end

Au lieu de parcourir les lettres du mot, la boucle parcourt les lettres obligatoires. Si l'une des lettres requises n'apparaît pas dans le mot, le programme retourne false.

Si vous pensez vraiment comme un informaticien, vous avez identifié que usesall est un exemple de problème déjà résolu. Dans ce cas, il est vraisemblable que vous ayez écrit :

 
Sélectionnez
1.
2.
3.
function useall(word, required)
    usesonly(required, word)
end

Il s'agit d'un exemple de plan de développement de programmes appelé réduction à un problème préalablement résolu. Cela signifie que le programmeur identifie le problème sur lequel il travaille comme un cas de problème résolu et qu'il applique une solution existante.

9-4. Boucles sur les indices

Les fonctions de la section 9.3Recherche ont été écrites avec des boucles for parce que seuls divers caractères des chaînes étaient utiles. Il était donc possible de travailler sans les indices.

Pour isabecedarian, nous devons comparer des lettres adjacentes, ce qui est un peu délicat avec une boucle for :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function isabecedarian(word) 
    i = firstindex(word)
    previous = word[i]
    j = nextind(word, i)
    for c in word[j:end] 
        if c < previous 
            return false
        end
        previous = c
    end
    true
end

Une autre possibilité consiste à faire appel à la récursion :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
function isabecedarian(word)
    if length(word) <= 1
        return true
    end
    i = firstindex(word)
    j = nextind(word, i)
    if word[i] > word[j]
        return false
    end
    isabecedarian(word[j:end])
end

Une option supplémentaire revient à exploiter une boucle while :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function isabecedarian(word)
    i = firstindex(word)
    j = nextind(word, 1)
    while j <= sizeof(word)
        if word[j] < word[i]
            return false
        end
        i = j
        j = nextind(word, i)
    end
    true
end

La boucle commence à i = 1 et j = nextind(word, 1). Elle se termine lorsque j > sizeof(word). À chaque passage, la boucle compare le iième caractère (qui peut être considéré comme le caractère courant) au jième caractère (qui est le suivant).

Si le caractère suivant est inférieur en termes d'ordre alphabétique au caractère courant, alors il y a rupture dans le schéma abécédaire. En conséquence, le programme retourne false.

Si la fin de la boucle est atteinte sans trouver de rupture, alors le mot passe le test. Pour se convaincre que la boucle se termine correctement, nous pouvons prendre pour exemple « choux ».

À présent, voici une version d'ispalindrome qui utilise deux indices. L'un commence au début et croît, l'autre commence à la fin et décroît.

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function ispalindrome(word)
    i = firstindex(word)
    j = lastindex(word)
    while i < j
        if word[i] != word[j]
            return false 
        end
        i = nextind(word, i)
        j = prevind(word, j)
    end 
    true
end

Ce cas peut être réduit à un problème préalablement résolu :

 
Sélectionnez
1.
2.
3.
function ispalindrome(word)
    isreverse(word, word)
end

La fonction isreverse a été étudiée à la section 8.13Débogage.

9-5. Débogage

Tester des programmes est une tâche complexe. Les fonctions présentées dans ce chapitre sont relativement faciles à tester, car les résultats sont vérifiables manuellement. Nonobstant cela, il est difficile — voire impossible — de choisir un ensemble de mots qui permettent de tester toutes les erreurs possibles.

Par exemple avec hasno_e, deux cas sont évidents à vérifier : les mots qui ont un e devraient amener le programme à retourner false, et les mots qui n'en ont pas devrait forcer le programme à retourner true. Trouver chacun de ces cas est assez facile.

Très souvent, existent des sous-cas moins évidents. Parmi les mots qui contiennent un « e », il convient de tester les mots qui ont un « e » au début, à la fin et quelque part au milieu. Cela implique de tester les mots longs, les mots courts et les mots très courts, comme la chaîne vide. Or, la chaîne vide est un exemple de cas particulier non trivial où des erreurs se camouflent souvent.

En plus des situations de test à traiter manuellement, tester le programme avec une liste de mots comme mots_FR.txt est nécessaire. En analysant la sortie, il est peut-être possible de détecter des erreurs. Attention, toutefois : on court toujours le risque de détecter un type d'erreur (des mots qui ne devraient pas être inclus, mais qui le sont) et inversement (des mots qui devraient être inclus et qui… ne le sont pas).

En général, les tests contribuent à trouver des bogues. En tout état de cause, il n'est guère facile de produire un bon ensemble de tests. Même dans ce cas, personne ne peut être sûr à 100 % que le programme est correct. Selon le célèbre informaticien Edsger W. Dijkstra :

Program testing can be used to show the presence of bugs, but never to show their absence !(19)

9-6. Glossaire

flux de fichiers valeur qui représente un fichier ouvert.

réduction à un problème préalablement résolu procédé destiné à résoudre un problème en l'exprimant comme un cas de figure déjà résolu.

cas particulier cas de test atypique ou non trivial (et susceptible de ne pas être traité correctement).

9-7. Exercices 9-7

9-7-1. Exercice

Cet exercice est basé sur un casse-tête qui fut diffusé dans l'émission de radio Car Talk :

« Donnez-moi un mot avec trois paires de lettres consécutives.
Je vous donne deux mots qui se qualifient presque. Par exemple, le mot « committee », c-o-m-m-i-t-t-e-e. Ce serait génial, sauf pour le i qui se faufile au milieu. Ou « Mississippi » : M-i-s-s-i-s-s-i-p-p-i. Si vous pouviez enlever ces i, ce serait parfait. Pourtant, il existe un mot qui a trois paires de lettres consécutives et, à ma connaissance, c'est peut-être le seul mot. Bien sûr, il y en a probablement 500 autres, mais je n'en connais qu'un seul. Quel est ce mot ? »

Écrivez un programme qui résout ce problème.

9-7-2. Exercice 9-8

Voici un autre casse-tête de l'émission de radio Car Talk :

« L'autre jour, je conduisais sur l'autoroute et, par hasard, j'ai jeté un coup d'œil à mon compteur kilométrique. Comme la plupart des odomètres, il affiche six chiffres, en kilomètres entiers seulement. Ainsi, si ma voiture avait par exemple fait 300 000 miles, je verrais 3-0-0-0-0-0.

Ce que j'ai vu ce jour-là était très intéressant. J'ai remarqué que les quatre derniers chiffres étaient palindromiques, c'est-à-dire qu'ils lisaient de la même façon en avant et en arrière. Par exemple, 5-4-4-5 est un palindrome. Donc, mon odomètre aurait pu afficher 3-1-5-4-4-5.

Un kilomètre plus tard, les 5 derniers chiffres étaient palindromiques. Par exemple, il aurait pu lire 3-6-5-4-5-6. Un kilomètre plus loin, les 4 chiffres du milieu sur 6 étaient palindromiques. Vous êtes prêt ? Un kilomètre plus tard, les 6 chiffres formaient un palindrome !

La question est de savoir ce qui était inscrit sur l'odomètre quand je l'ai regardé la première fois. »

Rédigez un programme Julia qui teste tous les nombres à six chiffres et qui affiche tous les nombres répondant aux exigences du casse-tête.

9-7-3. Exercice 9-9

Voici un dernier casse-tête de Car Talk :

« Récemment, j'ai eu la visite de ma mère. Nous avons réalisé que les deux chiffres qui composent mon âge, lorsqu'ils sont inversés, donnent son âge. Par exemple, si elle est âgée de 73 ans, j'ai 37 ans. Nous nous sommes demandées combien de fois cela s'était produit au fil des ans, mais nous nous sommes laissées distraire par d'autres sujets et nous n'avons jamais trouvé de réponse.

En rentrant chez moi, je me suis rendu compte que les chiffres de notre âge ont été réversibles six fois jusqu'à présent. J'ai aussi compris que si nous avons de la chance, cela se reproduirait dans quelques années, et si nous avons vraiment de la chance, cela se reproduirait encore une fois après. En d'autres termes, cela se produirait 8 fois en tout. La question est donc de savoir quel âge j'ai maintenant ? »

Écrivez un programme Julia qui cherche des solutions à cette énigme.

La fonction lpad pourrait vous être utile.


précédentsommairesuivant
Les tests de programmes peuvent être utilisés pour montrer la présence de bogues,  mais jamais pour montrer leur absence !

Licence Creative Commons
Le contenu de cet article est rédigé par Thierry Lepoint et est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 non transposé.
Les logos Developpez.com, en-tête, pied de page, css, et look & feel de l'article sont Copyright © 2021 Developpez.com.