Pensez en Python

Pour les exercices de ce chapitre, nous avons besoin d'une liste de mots français. Il y a beaucoup de listes de mots disponibles sur le Web, et vous pouvez en principe utiliser celle que vous préférerez. Nous allons toutefois utiliser la liste des mots pour le Scrabble de Jean-Philippe Durand, disponible à l'adresse http://jph.durand.free.fr/scrabble.htm (ou en format texte à l'adresse http://jph.durand.free.fr/scrabble.txt). Il vous sera peut-être plus facile de suivre si vous utilisez la même liste.

Ce fichier est en format texte brut, donc vous pouvez l'ouvrir avec un éditeur de texte, mais vous pouvez aussi le lire à partir de Python. La fonction interne open prend comme paramètre le nom du fichier et retourne un objet fichier que vous pouvez utiliser pour lire le fichier.

>>> fin = open('mots.txt')

fin (pour file in) est un nom usuel pour un objet fichier utilisé en lecture. L'objet fichier fournit plusieurs méthodes de lecture, dont readline, qui lit les caractères du fichier en entrée jusqu'à ce qu'elle arrive à un passage à la ligne et renvoie le résultat sous forme de chaîne de caractères :

>>> fin.readline()
'AA\r\n'

Le premier mot de cette liste particulière est « AA », qui est une sorte de lave. La séquence \r\n représente deux caractères non imprimables, un retour chariot et un saut de ligne, qui séparent ce mot du mot suivant, du moins dans un environnement Windows. Selon la façon dont vous avez récupéré la liste et si vous utilisez un environnement Mac, Unix ou Linux, il se peut que vous trouviez des passages à la ligne constitués du seul caractère \n de saut de ligne.

L'objet fichier garde en mémoire l'endroit où il se trouve dans le fichier, donc si vous appelez readline à nouveau, vous obtenez le mot de la ligne suivante :

>>> fin.readline()
'AH\r\n'

Le mot suivant est « AH », qui est un mot parfaitement légitime, n'ayez pas l'air aussi étonné. Ou, si ce sont les caractères non imprimables qui vous préoccupent, nous pouvons nous en débarrasser avec la méthode de chaîne de caractères strip :

>>> ligne = fin.readline()
>>> mot = ligne.strip()
>>> mot
'AI'

Vous pouvez également utiliser un objet fichier avec une boucle for. Ce programme lit mots.txt et affiche chaque mot, un par ligne :

fin = open('mots.txt')
for ligne in fin:
    mot = ligne.strip()
    print(mot)

Les solutions à ces exercices se trouvent dans la section suivante. Vous devriez au moins essayer de les résoudre avant de lire les solutions.

Exercice 1

Écrivez un programme qui lit mots.txt et affiche uniquement les mots de plus de 14 caractères (sans compter les caractères non imprimables). Pour l'instant, n'affichez que les premiers 20 ou 30 mots trouvés (il y en a plus de 2000 dans la liste que nous avons suggéré d'utiliser).

Exercice 2

En 1969, Georges Perec a publié le roman appelé La Disparition qui ne comporte pas une seule fois la lettre « e ». (Voir https://fr.wikipedia.org/wiki/La_Disparition_%28roman%29) Comme « e » est de loin la lettre la plus commune en français, c'est presque un tour de force.

En fait, il est difficile de construire même une seule idée, sans l'aide de ce symbole le plus commun. Cela va lentement au début, mais avec de la prudence et des heures d'entraînement, vous pouvez vous y habituer progressivement.

Très bien, je vais arrêter maintenant.

Écrivez une fonction appelée n_a_aucun_E qui renvoie True si le mot donné ne contient aucune lettre « E ».

Modifiez votre programme de l'exercice précédent pour afficher seulement les mots de plus de 14 lettres qui ne contiennent aucun « e » et calculer le pourcentage de mots de la liste qui ne contiennent aucun « e ». Si vous utilisez la liste suggérée, n'oubliez pas que les mots sont écrits en lettres capitales et que c'est dont la lettre capitale « E » qu'il vous faudra détecter. À titre d'information, sur l'ensemble des 130 557 mots de notre liste en entrée, seuls un peu plus de 18 000 n'ont aucune fois la lettre E.

Exercice 3

Écrivez une fonction nommée evite qui prend un mot et une liste de lettres interdites, et qui renvoie True si le mot ne contient aucune des lettres interdites.

Modifiez votre programme pour inviter l'utilisateur à saisir une chaîne de lettres interdites et ensuite afficher le nombre de mots de la liste en entrée qui ne contient aucune de celles-ci. Pouvez-vous trouver une combinaison de 5 lettres interdites qui exclut le plus petit nombre de mots ?

Exercice 4

Écrivez une fonction nommée utilise_uniquement qui prend un mot et une chaîne de lettres, et qui renvoie True si le mot ne contient que les lettres de la liste. Pouvez-vous faire une phrase en utilisant seulement les lettres acefhlo ?

Exercice 5

Écrivez une fonction nommée utilise_toutes qui prend un mot et une chaîne de lettres requises, et qui renvoie True si le mot utilise toutes les lettres requises au moins une fois. Combien y a-t-il de mots qui utilisent toutes les voyelles aeiou ? Et aeiouy ?

Exercice 6

Écrivez une fonction appelée est_en_ordre_alphabetique qui renvoie True si les lettres d'un mot apparaissent dans l'ordre alphabétique (les lettres doublées sont autorisées). Combien y a-t-il de mots de ce genre ?

Tous les exercices de la section précédente ont quelque chose en commun : ils peuvent être résolus avec le modèle de recherche que nous avons vu dans la section 8.6Recherche. L'exemple le plus simple est :

def n_a_aucun_E(mot):
    for lettre in mot:
        if lettre == 'E':
            return False
    return True

La boucle for parcourt les caractères de mot. Si nous trouvons la lettre « E », nous pouvons immédiatement renvoyer False ; sinon, nous devons aller à la lettre suivante. Si nous sortons de la boucle normalement, cela signifie que nous ne trouvons aucun « E », alors nous renvoyons True.

Vous pouviez écrire cette fonction de manière plus concise en utilisant l'opérateur in, mais j'ai commencé par cette version, car elle démontre la logique du modèle de recherche.

evite est une version plus générale de n_a_aucun_E, mais elle a la même structure :

def evite(mot, interdites):
    for lettre in mot:
        if lettre in interdites:
            return False
    return True

Au lieu d'une liste de lettres interdites, nous avons une liste de lettres disponibles. Si nous trouvons dans le mot une lettre qui ne fait pas partie des disponibles, nous pouvons renvoyer False.

utilise_toutes est semblable, sauf que nous inversons le rôle du mot et de la chaîne de lettres :

def utilise_toutes(mot, requises):
    for lettre in requises: 
        if lettre not in mot:
            return False
    return True

Au lieu de parcourir les lettres de mot, la boucle parcourt les lettres requises. Si l'une des lettres requises ne figure pas dans le mot, nous pouvons renvoyer False.

Si vous pensiez vraiment comme un informaticien, vous auriez remarqué que utilise_toutes était une variante du problème résolu précédemment, et vous auriez écrit :

def utilise_toutes(mot, requises):
    return utilise_toutes(requises, mot)

Cela représente un exemple de méthode de développement d'un programme appelée réduction à un problème déjà résolu, qui signifie que vous reconnaissez le problème que vous essayez de résoudre comme une variante d'un problème résolu et appliquez une solution existante.

J'ai utilisé des boucles for pour écrire les fonctions de la section précédente parce que j'avais besoin uniquement des caractères dans les chaînes ; je n'avais pas besoin d'utiliser les indices.

Pour est_en_ordre_alphabetique, nous devons comparer des lettres adjacentes, ce qui est un peu difficile avec une boucle for :

def est_en_ordre_alphabetique(mot):
    precedent = mot[0]
    for c in mot:
        if c < precedent:
            return False
        precedent = c
    return True

Une autre possibilité est d'utiliser la récursivité :

def est_en_ordre_alphabetique(mot):
    if len(mot) <= 1:
        return True
    if mot[0] > mot[1]:
        return False
    return est_en_ordre_alphabetique(mot[1:])

Une autre option serait d'utiliser une boucle while:

def est_en_ordre_alphabetique(mot):
    i = 0
    while i < len(mot) - 1:
        if mot[i+1] < mot[i]:
            return False
        i = i + 1
    return True

La boucle commence à i = 0 et se termine lorsque i = len(mot) - 1. À chaque itération, la boucle compare le ième caractère (que vous pouvez voir comme le caractère actuel) au i + 1ème caractère (que vous pouvez voir comme le caractère suivant).

Si le caractère suivant est inférieur au (alphabétiquement avant le) caractère actuel, alors nous avons découvert une interruption dans la suite alphabétique, et nous renvoyons False.

Si nous arrivons à la fin de la boucle sans rencontrer une telle situation, alors le mot passe le test. Pour vous convaincre que la boucle se termine correctement, prenons un exemple comme 'EFFORT'. La longueur du mot est de 6, donc la dernière exécution de la boucle a lieu lorsque i est 4, qui est l'indice de l'avant-dernier caractère. Lors de la dernière itération, on compare l'avant-dernier caractère (R) au dernier (T), ce qui est ce que nous voulons.

Voici une version de is_palindrome (voir Exercice 3 du chapitre 6) qui utilise deux indices ; l'un commence au début et augmente ; l'autre commence à la fin et diminue.

def is_palindrome(mot):
    i = 0
    j = len(mot) - 1

    while i < j:
        if mot[i] != mot[j]:
            return False
        i = i + 1
        j = j - 1

    return True

Ou nous pourrions réduire à un problème déjà résolu et écrire :

def is_palindrome(mot):
    return is_inverse(mot, mot)

en utilisant la fonction is_inverse de la section 8.11Débogage.

Il est difficile de tester des programmes. Les fonctions de ce chapitre sont relativement faciles à tester, parce que vous pouvez vérifier les résultats à la main. Même ainsi, il est difficile sinon impossible de choisir un ensemble de mots pour tester toutes les erreurs possibles.

Si nous prenons n_a_aucun_E comme exemple, il y a deux cas évidents à vérifier : les mots qui ont un 'E' devraient retourner False et les mots qui n'en ont pas devraient retourner True. Vous ne devriez avoir aucune difficulté à trouver un mot de chaque type.

Dans chaque cas, il y a des sous-cas moins évidents. Parmi les mots qui contiennent un « E », vous devez tester mots avec un « E » au début, à la fin, et quelque part au milieu. Vous devez tester des mots longs, des mots courts, et des mots très courts, comme la chaîne vide. La chaîne vide est un exemple d'un cas particulier, qui est l'un des cas non évidents où les erreurs se cachent souvent.

En plus des cas de test que vous générez, vous pouvez également tester votre programme avec une liste de mots comme ceux dans le fichier mots.txt. En examinant la sortie, vous pourriez être en mesure de remarquer les erreurs, mais attention : vous pourriez déceler un type d'erreur (les mots qui ne devraient pas être inclus, mais le sont), mais pas l'autre (les mots qui devraient être inclus, mais ne le sont pas).

En général, les tests peuvent vous aider à trouver des bogues, mais il n'est pas facile de générer un bon jeu de cas de tests, et, même si vous le faites, vous ne pouvez pas être sûr que votre programme est correct. Selon un légendaire chercheur en informatique :

• objet fichier : une valeur qui représente un fichier ouvert.
• réduction à un problème déjà résolu : une façon de résoudre un problème en l'exprimant comme une variante d'un problème déjà résolu.
• cas spécial : un cas de test qui est atypique ou non évident (et moins susceptible d'être géré correctement).

Exercice 7

Cette question est basée sur un casse-tête diffusé sur le programme de radio Car Talk (http://www.cartalk.com/content/puzzlers) :

• Donnez-moi un mot contenant trois lettres doubles consécutives. Je vais vous donner quelques mots qui se rapprochent, mais ne remplissent pas cette condition. Par exemple, le mot ASSOMMEE A-s-s-o-m-m-é-e. Ce serait super, sans le 'o' qui s'y faufile. Ou Mississippi : M-i-s-s-i-s-s-i-p-p-i. Si vous pouviez enlever ces i, cela fonctionnerait. Mais il y a un mot qui a trois paires consécutives de lettres et à ma connaissance, il pourrait en être le seul (avec ce même mot mis au pluriel). Bien sûr, il y en a peut-être d'autres, mais je ne peux penser qu'à un seul. Quel est le mot ?

Écrivez un programme pour le trouver. Solution : cartalk1.py.

Exercice 8

Voici un autre casse-tête diffusé sur Car Talk (http://www.cartalk.com/content/puzzlers) :

• Je roulais sur l'autoroute l'autre jour et mon regard a été attiré par mon compteur kilométrique. Comme la plupart de ces compteurs, il affiche six chiffres, seulement en kilomètres entiers. Donc, si ma voiture avait 300 000 kilomètres, par exemple, j'aurais vu 3-0-0-0-0-0.
  Maintenant, ce que je voyais ce jour-là était très intéressant. Je remarquai que les 4 derniers chiffres étaient palindromiques ; c'est-à-dire ils composent le même nombre si on les lit de gauche à droite ou de droite à gauche. Par exemple, 5-4-4-5 est un palindrome, donc mon compteur pouvait indiquer 3-1-5-4-4-5.
  Un kilomètre plus tard, les 5 derniers chiffres étaient un palindrome. Par exemple, on aurait pu lire 3-6-5-4-5-6. Un kilomètre après, sur les 6 chiffres, les 4 du milieu composaient un palindrome. Et accrochez-vous ! Un kilomètre plus tard, tous les 6 composaient un palindrome !
  La question est qu'affichait le compteur kilométrique quand j'ai regardé la première fois ?

Écrivez un programme Python qui teste tous les numéros à six chiffres et affiche les chiffres qui satisfont à ces exigences. Solution : cartalk2.py.

Exercice 9

Voici un autre casse-tête Car Talk que vous pouvez résoudre par une recherche (http://www.cartalk.com/content/puzzlers) :

• Récemment, j'étais en visite chez ma mère et nous avons réalisé que si l'on inverse les deux chiffres qui composent mon âge, nous obtenons son âge. Par exemple, si elle a 73 ans, moi j'en ai 37. Nous nous demandions combien de fois cela est arrivé au fil du temps, mais nous nous sommes détourné l'attention avec d'autres sujets et nous n'avons pas trouvé une réponse.
  Lorsque je suis rentré chez moi, j'avais découvert que les chiffres de nos âges ont été réversibles six fois jusqu'à présent. Je me suis dit aussi que si nous sommes chanceux cela arriverait de nouveau dans quelques années, et si nous sommes vraiment chanceux cela se produirait encore une fois par la suite. Autrement dit, cela serait arrivé 8 fois en total. Donc la question est, quel âge ai-je maintenant ?

Écrivez un programme Python qui recherche des solutions à ce casse-tête. Indice : vous pourriez trouver utile la méthode de chaîne de caractères zfill.

Solution : cartalk3.py.