Dive Into Python 3 - 8 : Itérateurs avancés

Article publié, le 16 Mai 2019 et modifié le 18 Mai 2019
25 minutes de lecture

Cet article contient 5127 mots.
Source brute de l'article :
Commit version : 9c0a93f

Dive Into Python 3 - 8 : Itérateurs avancés

Great fleas have little fleas upon their backs to bite ’em, And little fleas have lesser fleas, and so ad infinitum. — Augustus De Morgan

En plongée

Tout comme les expressions régulières dopent les chaînes aux stéroïdes, le module itertools dopent les itérateurs aux stéroïdes. Mais d’abord, je veux vous montrer un puzzle classique :

HAWAII + IDAHO + IOWA + OHIO == STATES
510199 + 98153 + 9301 + 3593 == 621246

H = 5
A = 1
W = 0
I = 9
D = 8
O = 3
S = 6
T = 2
E = 4

De tels puzzles sont appelés cryptarithmes ou alphamétiques. Les lettres épellent des mots réels, mais si vous remplacez chaque lettre par un chiffre de 0-9, elles « épellent » aussi une équation arithmétique. L’astuce consiste à déterminer quelle lettre correspond à chaque chiffre. Toutes les occurrences de chaque lettre doivent correspondre au même chiffre, aucun chiffre ne doit être répété, et aucun « mot » ne peut démarrer avec le chiffre 0.

Dans ce chapitre, nous plongerons en profondeur dans un incroyable programme Python écrit à l’origine par Raymond Hettinger. Ce programme résout les puzzles alphamétiques en seulement 14 lignes de code :

import re
import itertools

def solve(puzzle):
    words = re.findall('[A-Z]+', puzzle.upper())
    unique_characters = set(''.join(words))
    assert len(unique_characters) <= 10, 'Too many letters'
    first_letters = {word[0] for word in words}
    n = len(first_letters)
    sorted_characters = ''.join(first_letters) + \
        ''.join(unique_characters - first_letters)
    characters = tuple(ord(c) for c in sorted_characters)
    digits = tuple(ord(c) for c in '0123456789')
    zero = digits[0]
    for guess in itertools.permutations(digits, len(characters)):
        if zero not in guess[:n]:
            equation = puzzle.translate(dict(zip(characters, guess)))
            if eval(equation):
                return equation

if __name__ == '__main__':
    import sys
    for puzzle in sys.argv[1:]:
        print(puzzle)
        solution = solve(puzzle)
        if solution:
            print(solution)

Vous pouvez exécuter ce programme depuis la ligne de commande. Sous Linux, cela ressemblerait à ceci. (Cela peut prendre un peu de temps, selon la vitesse de votre ordinateur, et comme il n’y a pas de barre de progression, soyez patient !)

you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES"
HAWAII + IDAHO + IOWA + OHIO = STATES
510199 + 98153 + 9301 + 3593 == 621246

you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA"
I + LOVE + YOU == DORA
1 + 2784 + 975 == 3760

you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY"
SEND + MORE == MONEY
9567 + 1085 == 10652

Trouver toutes les occurrences d’un motif

La première chose que ce résolveur alphamétique fait est de trouver toutes les lettres (A-Z) dans le puzzle.

>>> import re
>>> re.findall('[0-9]+', '16 2-by-4s in rows of 8')  ①
['16', '2', '4', '8']
>>> re.findall('[A-Z]+', 'SEND + MORE == MONEY')     ②
['SEND', 'MORE', 'MONEY']

① Le module re est une implémentation Python des expressions régulières. Il a une fonction astucieuse appelée findall() qui prend un motif d’expression régulière et une chaîne, et trouve toutes les occurrences du motif dans la chaîne. Dans ce cas, le motif correspond aux séquences de nombres. La fonction findall() retourne une liste de toutes les sous-chaînes qui correspondent au motif.

② Ici est le motif d’expression régulière qui correspond aux séquences de lettres. Une fois encore, la valeur de retour est une liste, et chaque item dans la liste est une chaîne qui correspond au motif d’expression régulière.

Voici un autre exemple qui stimulera un peu votre cerveau.

>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.")
[' sixth s', " sheikh's s", " sheep's s"]

Surpris ? L’expression régulière recherche un espace, un s, et ensuite la plus petite série possible de tout caractère (.*?), suivi d’un espace et encore d’un s. Bien, en regardant cette chaîne en entrée, je vois cinq correspondances :

The sixth sick sheikh’s sixth sheep’s sick.
The sixth sick sheikh’s sixth sheep’s sick.
The sixth sick sheikh's sixth sheep’s sick.
The sixth sick sheikh’s sixth sheep’s sick.
The sixth sick sheikh’s sixth sheep's sick.

Mais la fonction re.findall() ne retourne seulement que trois correspondances. Elle retourne spécifiquement la première, la troisième et la cinquième. Pourquoi cela ? Parce qu’ elle ne renvoie pas les correspondances qui se chevauchent. La première correspondance chevauche la seconde, ainsi la première est retournée et la seconde est sautée. Ensuite, la troisième chevauche la quatrième, ainsi la troisième est retournée et la quatrième est sautée. Finalement, la cinquième est retournée. Trois correspondances et pas cinq.

Cela n’a rien à voir avec le résolveur alphamétique ; Je pensais juste que c’était intéressant.

Trouver les items uniques dans une séquence

Sets rend trivial la recherche d’items uniques dans une séquence.

>>> a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick']
>>> set(a_list)                      ①
{'sixth', 'The', "sheep's", 'sick', "sheik's"}
>>> a_string = 'EAST IS EAST'
>>> set(a_string)                    ②
{'A', ' ', 'E', 'I', 'S', 'T'}
>>> words = ['SEND', 'MORE', 'MONEY']
>>> ''.join(words)                   ③
'SENDMOREMONEY'
>>> set(''.join(words))              ④
{'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}

① À une liste donnée de nombreuses chaînes, la fonction set() retournera un ensemble de chaînes uniques depuis la liste. Cela à du sens si vous le considérez comme une boucle for. Prendre le premier item de la liste, et le mettre dans l’ensemble. Le second. Le troisième. Le quatrième. Le cinquième - attendez, c’est déjà dans l’ensemble, donc il n’est répertorié qu’une fois, car les ensembles Python n’autorisent pas les doublons. La sixième. La septième – encore, une dupliquée, qui ne sera listée qu’une fois. Le résultat final ? Chacun des items uniques de la liste originale, sans duplication. La liste originale n’a même pas besoin d’être triée en premier.

② La même technique fonctionne avec les chaînes, puisqu’une chaîne est une séquence de caractères.

③ À une liste donnée de chaînes, ''.join(a_list) concatène toutes les chaînes ensemble en une seule.

④ Ainsi, à une liste donnée de chaînes, la ligne de code retourne tous les caractères uniques dans toutes les chaînes, sans duplication.

Le résolveur alphamétique utilise cette technique pour construire un ensemble de tous les caractères uniques dans le puzzle.

unique_characters = set(''.join(words))

Cette liste est utilisée plus tard pour assigner des chiffres aux caractères ainsi le résolveur parcourt les solutions possibles.

Créer des assertions

Tout comme beaucoup de langages de programmation, Python a une instruction assert. Voici comment elle fonctionne :

>>> assert 1 + 1 == 2                                     ①
>>> assert 1 + 1 == 3                                     ②
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
>>> assert 2 + 2 == 5, "Only for very large values of 2"  ③
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError: Only for very large values of 2

① L’instruction assert est suivie de toute expression Python valide. Dans ce cas, l’expression 1 + 1 == 2 est évaluée à True, l’instruction assert ne fait rien.

② Toutefois, si l’expression Python est évaluée à False, l’instruction assert lèvera une AssertionError.

③ Vous pouvez aussi inclure un message humainement compréhensible qui est affiché si AssertionError est levée.

Donc, cette ligne de code :

assert len(unique_characters) <= 10, 'Too many letters'

… est équivalente à cela :

if len(unique_characters) > 10:
    raise AssertionError('Too many letters')

Le résolveur alphamétique utilise l’instruction exacte assert pour s’affranchir rapidement si le puzzle contient plus de dix lettres uniques. Puisque chaque lettre est assignée à un chiffre unique, et qu’il y a seulement dix chiffres, un puzzle avec plus de dix lettres uniques ne peut pas avoir de solution possible.

Générateur d’expressions

Un générateur d’expression est tout comme un générateur de fonction mais sans fonction.

>>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
>>> gen = (ord(c) for c in unique_characters)  ①
>>> gen                                        ②
<generator object <genexpr> at 0x00BADC10>
>>> next(gen)                                  ③
69
>>> next(gen)
68
>>> tuple(ord(c) for c in unique_characters)   ④
(69, 68, 77, 79, 78, 83, 82, 89)

① Un générateur d’expression est comme une fonction anonyme qui donne des valeurs. L’expression ressemble en elle-même à une liste de compréhension, mais elle est entourée de parenthèses au lieu de crochets.

② Le générateur d’expression retourne… un itérateur.

③ L’appel à next(gen) retourne la valeur suivante dans l’itérateur.

④ Si vous le souhaitez, vous pouvez itérer au-travers toutes les valeurs possibles et retourner un tuple, une liste, ou un ensemble, en soumettant le générateur d’expression à tuple(), list() ou set(). Dans ces cas, vous n’avez pas besoin de parenthèses supplémentaires – il suffit de passer l’expression ord(c) for c in unique_characters telle qu’elle à la fonction tuple(), et Python comprend que c’est un générateur d’expressions.

Utiliser un générateur d’expressions au lieu d’une liste de compréhension peut soulager à la fois le CPU et la RAM. Si vous construisez une liste pour juste la détruire ensuite (p. ex. pour la passer à tuple() ou set()), utilisez plutôt un générateur d’expression.

Voici une autre manière d’accomplir la même chose, en utilisant un générateur de fonction :

def ord_map(a_string):
    for c in a_string:
        yield ord(c)

gen = ord_map(unique_characters)

Le générateur d’expression est plus compact mais fonctionne de même manière.

Calculer les Permutations… La manière facile !

Tout d’abord, que sont les permutations ? Les permutations sont un concept mathématique. (Il y a actuellement de nombreuses définitions, selon le type de maths que vous faites. Ici, je parle des combinatoires, mais si cela ne vous dit rien, ne vous inquiétez pas. Comme toujours, Wikipedia est votre ami).

L’idée est de prendre une liste de choses (qui peuvent être des nombres, des lettres, ou des ours dansants) et de trouver toutes les moyens possibles pour les scinder en petites listes. Toutes ces petites listes ont la même taille, qui peuvent aussi petites que 1 et aussi grandes que le nombre total des items.

Oh, rien ne doit être répété. Les mathématiciens disent des choses telles que « trouvons les permutations de 3 items différents pris 2 à la fois » ce qui signifie que vous avez une séquence de 3 items et que vous devez trouver toutes les paires ordonnées possibles.

>>> import itertools                              ①
>>> perms = itertools.permutations([1, 2, 3], 2)  ②
>>> next(perms)                                   ③
(1, 2)
>>> next(perms)
(1, 3)
>>> next(perms)
(2, 1)                                            ④
>>> next(perms)
(2, 3)
>>> next(perms)
(3, 1)
>>> next(perms)
(3, 2)
>>> next(perms)                                   ⑤
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

① Le module itertools contient toutes sortes de choses amusantes, incluant la fonction permutations() qui fait tout le travail difficile pour trouver les permutations.

② La fonction permutations() prend une séquence (ici une liste de trois entiers) et un nombre, qui est le nombre d’items que vous voulez dans chaque petit groupe. La fonction retourne un itérateur, que vous pouvez utiliser dans une boucle for ou tout autre code qui itère. Ici, je vais parcourir l’itérateur manuellement pour afficher toutes les valeurs.

③ La première permutation de [1, 2, 3], qui prend 2 à la fois, est (1, 2).

④ Notez que les permutations sont ordonnées : (2, 1)est différent de (1, 2).

⑤ C’est tout ! Ce sont toutes les permutations de [1, 2, 3] qui prennent 2 à la fois. Les pairs telles que (1, 1) et (2, 2) ne seront jamais vues, parce qu’elles contiennent des répétitions qui ne sont pas des permutations valides.

La fonction permutations() ne nécessite pas de liste. Elle peut prendre n’importe quelle séquence – même une chaîne.

>>> import itertools
>>> perms = itertools.permutations('ABC', 3)  ①
>>> next(perms)
('A', 'B', 'C')                               ②
>>> next(perms)
('A', 'C', 'B')
>>> next(perms)
('B', 'A', 'C')
>>> next(perms)
('B', 'C', 'A')
>>> next(perms)
('C', 'A', 'B')
>>> next(perms)
('C', 'B', 'A')
>>> next(perms)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> list(itertools.permutations('ABC', 3))    ③
[('A', 'B', 'C'), ('A', 'C', 'B'),
 ('B', 'A', 'C'), ('B', 'C', 'A'),
 ('C', 'A', 'B'), ('C', 'B', 'A')]

① Une chaîne est juste une séquence de caractères. Dans le but de trouver des permutations, la chaîne ‘ABC’ est équivalente à la liste [‘A’, ‘B’, ‘C’].

② La première permutation de trois items [‘A’, ‘B’, ‘C’], qui prennent 3 à la fois, est (‘A’, ‘B’, ‘C’). Il y a cinq autres permutations. Les trois mêmes caractères dans chaque ordre imaginable.

③ Puisque la fonction permutations() retourne toujours un itérateur, une manière facile de déboguer les permutations est de passer l’itérateur dans la fonction interne list() pour voir toutes les permutations immédiatement.

Autres trucs amusants dans le module `itertools`

>>> import itertools
>>> list(itertools.product('ABC', '123'))   ①
[('A', '1'), ('A', '2'), ('A', '3'),
 ('B', '1'), ('B', '2'), ('B', '3'),
 ('C', '1'), ('C', '2'), ('C', '3')]
>>> list(itertools.combinations('ABC', 2))  ②
[('A', 'B'), ('A', 'C'), ('B', 'C')]

① La fonction itertools.product() retourne un itérateur contenant le produit cartésien de deux séquences.

② La fonction itertools.combinations() retourne un itérateur contenant toutes les combinaisons possibles d’une séquence donnée d’une longueur donnée. Tout comme la fonction itertools.permutations(), excepté que les combinaisons n’incluent pas les items qui sont la copie d’autres items dans un ordre différent. Ainsi, itertools.permutations('ABC', 2) retournera les deux ('A', 'B') et ('B', 'A') (entres autres), mais itertools.combinations('ABC', 2) ne retournera pas ('B', 'A') parce que c’est une copie de ('A', 'B') dans un ordre différent.

>>> names = list(open('examples/favorite-people.txt', encoding='utf-8'))  ①
>>> names
['Dora\n', 'Ethan\n', 'Wesley\n', 'John\n', 'Anne\n',
'Mike\n', 'Chris\n', 'Sarah\n', 'Alex\n', 'Lizzie\n']
>>> names = [name.rstrip() for name in names]                             ②
>>> names
['Dora', 'Ethan', 'Wesley', 'John', 'Anne',
'Mike', 'Chris', 'Sarah', 'Alex', 'Lizzie']
>>> names = sorted(names)                                                 ③
>>> names
['Alex', 'Anne', 'Chris', 'Dora', 'Ethan',
'John', 'Lizzie', 'Mike', 'Sarah', 'Wesley']
>>> names = sorted(names, key=len)                                        ④
>>> names
['Alex', 'Anne', 'Dora', 'John', 'Mike',
'Chris', 'Ethan', 'Sarah', 'Lizzie', 'Wesley']

① Cet idiome retourne une liste à partir des lignes d’un fichier texte.

② Malheureusement (dans cet exemple), l’idiome list(open(filename)) inclus aussi le retour chariot à la fin de chaque ligne. Cette liste de compréhension utilise la méthode des chaînes rstrip() pour effacer les espaces de fin de chaque ligne. (Les chaînes ont aussi une méthode lstrip() pour supprimer les espaces en début, et une méthode strip() qui supprime les deux).

③ La fonction sorted() prend une liste et la retourne triée. Par défaut, le tri est alphabétique.

④ Mais la fonction sorted() peut aussi prendre une fonction en tant que paramètre key, elle est triée par la clé en question. Dans ce cas, la fonction de tri est len(), ainsi elle est triée par len(each item). Les noms les plus courts sont en premier, puis de plus en plus longs.

Qu’est-ce que cela a à voir avec le module itertools ? Je suis content que vous le demandiez.

…continuing from the previous interactive shell…
>>> import itertools
>>> groups = itertools.groupby(names, len)   ①
>>> groups
<itertools.groupby object at 0x00BB20C0>
>>> list(groups)
[(4, <itertools._grouper object at 0x00BA8BF0>),
 (5, <itertools._grouper object at 0x00BB4050>),
 (6, <itertools._grouper object at 0x00BB4030>)]
>>> groups = itertools.groupby(names, len)   ②
>>> for name_length, name_iter in groups:    ③
…     print('Names with {0:d} letters:'.format(name_length))
…     for name in name_iter:
…         print(name)
…
Names with 4 letters:
Alex
Anne
Dora
John
Mike
Names with 5 letters:
Chris
Ethan
Sarah
Names with 6 letters:
Lizzie
Wesley

① La fonction itertools.groupby() prend une séquence et une fonction clé, et retourne un itérateur qui génère des paires. Chaque paire contient le résultat de key_function(each item) et un autre itérateur contient tous les items que partage la clé résultante.

② L’appel à la fonction list() a « épuisé » l’itérateur, c’est-à-dire que vous avez déjà généré chaque élément de l’itérateur pour créer la liste. Il n’y a pas de bouton “reset” sur un itérateur ; vous ne pouvez pas juste le démarrer une fois qu’il est épuisé. Si vous voulez le parcourir encore par une boucle (dans une nouvelle boucle for), vous devez appeler encore itertools.groupby() pour créer un nouvel itérateur.

③ Dans cet exemple, à une liste donnée de noms toujours triée par longueur, itertools.groupby(names, len) sortira tous les noms de 4 lettres dans un itérateur, tous les noms de 5 lettres dans un autre, et ainsi de suite. La fonction groupby() est complètement générique ; elle peut regrouper les chaînes par première lettre, les nombres par nombre de facteurs ou toute autre fonction clé imaginable.

La fonction itertools.groupby() fonctionne seulement si la séquence en entrée est déjà triée par la fonction de regroupement. Dans l’exemple ci-dessus, vous avez groupé une liste de noms par la fonction len(). Cela a fonctionné parce que la liste entrée était déjà triée par longueur.

Regardez de plus prés !

>>> list(range(0, 3))
[0, 1, 2]
>>> list(range(10, 13))
[10, 11, 12]
>>> list(itertools.chain(range(0, 3), range(10, 13)))        ①
[0, 1, 2, 10, 11, 12]
>>> list(zip(range(0, 3), range(10, 13)))                    ②
[(0, 10), (1, 11), (2, 12)]
>>> list(zip(range(0, 3), range(10, 14)))                    ③
[(0, 10), (1, 11), (2, 12)]
>>> list(itertools.zip_longest(range(0, 3), range(10, 14)))  ④
[(0, 10), (1, 11), (2, 12), (None, 13)]

① La fonction itertools.chain() prend deux itérateurs et retourne un itérateur qui contient tous les items du premier itérateur, suivis de ceux du second itérateur. (Actuellement, il peut prendre n’importe quel nombre d’itérateurs, et les enchaîner dans l’ordre où ils sont passés dans la fonction.)

② La fonction zip() fait quelque chose de prosaïque qui s’avère extrêmement utile : elle prend n’importe quel nombre de séquences et retourne un itérateur qui retourne des tuples des premiers items de chaque séquence, ensuite les seconds items de chacune, puis les troisièmes, et ainsi de suite.

③ La fonction zip() s’arrête à la fin de la plus petite séquence. range(10, 14) a 4 items, mais range(10, 14) en a seulement 3, ainsi la fonction zip() retourne un itérateur de 3 items.

④ D’un autre côté, la fonction itertools.zip_longest() s’arrête à la fin de la séquence la plus longue, insérant des valeurs None pour les items passés en fin des séquences plus courtes.

Ok, tout cela est très intéressant, mais quel rapport cela a-t-il avec le résolveur d’alphamétique ? Voici comment :

>>> characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y')
>>> guess = ('1', '2', '0', '3', '4', '5', '6', '7')
>>> tuple(zip(characters, guess))                            ①
(('S', '1'), ('M', '2'), ('E', '0'), ('D', '3'),
 ('O', '4'), ('N', '5'), ('R', '6'), ('Y', '7'))
>>> dict(zip(characters, guess))                             ②
{'E': '0', 'D': '3', 'M': '2', 'O': '4',
 'N': '5', 'S': '1', 'R': '6', 'Y': '7'}

① À une liste donnée de lettres et une liste de chiffres (chacune représentée ici sous forme de chaînes de 1 caractère), la fonction zip() créera une paire de lettres et de chiffres, dans l’ordre.

② Pourquoi est-ce cool ? Parce que cette structure de données se trouve être exactement la bonne structure à transmettre à la fonction dict() pour créer un dictionnaire qui utilise des lettres comme clés et leurs chiffres associés comme valeurs. (Ce n’est bien sûr pas la seule manière de faire cela. Vous pouvez utiliser un dictionnaire de compréhension pour créer directement le dictionnaire). Bien que la représentation imprimée du dictionnaire liste les paires dans un ordre différent (les dictionnaires n’ont pas d ‘«ordre» en soi), vous pouvez voir que chaque lettre est associée à un chiffre, en fonction de l’ordre d’origine des séquences characters et guess.

Le résolveur alphamétique utilise cette technique pour créer un dictionnaire qui fait correspondre chaque lettre dans le puzzle au chiffre, pour chaque solution possible.

characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
…
for guess in itertools.permutations(digits, len(characters)):
    …
    equation = puzzle.translate(dict(zip(characters, guess)))

Mais qu’est-ce la méthode translate() ? Ahhh, vous arrivez maintenant la partie réellement amusante.

Une nouvelle manière de manipuler les chaînes

Les chaînes Python ont beaucoup de méthodes. Vous avez appris certaines de ces méthodes dans le chapitre Chaînes : lower(), count(), et format(). Maintenant je veux vous présenter une technique de manipulation puissante mais peu connue : la méthode translate().

>>> translation_table = {ord('A'): ord('O')}  ①
>>> translation_table                         ②
{65: 79}
>>> 'MARK'.translate(translation_table)       ③
'MORK'

① La traduction des chaînes débute avec une table de traduction, qui est simplement un dictionnaire qui fait correspondre un caractère avec un autre. Actuellement “caractère” est incorrect - la table de traduction fait réellement correspondre un octet avec un autre.

② Rappelez-vous, les octets en Python 3 sont des entiers. La fonction ord() retourne la valeur ASCII d’un caractère, qui, dans le cas de A-Z, est toujours un octet de 65 à 90.

③ La méthode translate() sur une chaîne prend une table de traduction et la parcourt. Pour cela, elle remplace toutes les occurences des clés de la table de traduction avec les valeurs correspondantes. Dans ce cas, elle “traduit” MARK en MORK.

Qu’est-ce que cela a à voir avec la résolution de puzzles alphamétiques ? En fait, tout.

>>> characters = tuple(ord(c) for c in 'SMEDONRY')       ①
>>> characters
(83, 77, 69, 68, 79, 78, 82, 89)
>>> guess = tuple(ord(c) for c in '91570682')            ②
>>> guess
(57, 49, 53, 55, 48, 54, 56, 50)
>>> translation_table = dict(zip(characters, guess))     ③
>>> translation_table
{68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50}
>>> 'SEND + MORE == MONEY'.translate(translation_table)  ④
'9567 + 1085 == 10652'

① En utilisant un générateur d’expressions, nous calculons les valeurs d’octet pour chaque caractère d’une chaîne. characters est un exemple de valeur de sorted_characters dans la fonction alphametics.solve().

② En utilisant un autre générateur d’expression, nous calculons les valeurs d’octet de chaque chiffre dans la chaîne. Le résultat, guess, est de la forme retournée par la fonction itertools.permutations() dans la fonction alphametics.solve().

③ Cette table de traduction est générée par itération de characters et de guess ensemble et en construisant un dictionnaire depuis la séquence de pairs résultante. C’est exactement ce que fait la fonction alphametics.solve() à l’intérieur de la boucle for.

④ Enfin, nous passons cette table de traduction à la méthode translate() du puzzle originale de la chaîne. Cela convertit chaque lettre dans la chaîne vers le chiffre correspondant (basé sur les lettres dans characters et les chiffres dans guess). Le résultat est une expression Python valide, tout comme l’est une chaîne.

C’est assez impressionnant. Mais que pouvez-vous faire avec une chaîne qui se trouve être une expression Python valide ?

Évaluer arbitrairement des chaînes en tant qu’expressions Python

Ceci est la pièce finale du puzzle (ou plutôt, la pièce finale du résolveur de puzzle). Après toutes ces manipulations sympathiques de chaînes, il nous reste une chaîne telle que '9567 + 1085 == 10652'. Mais c’est une chaîne, et qu’est-ce qui est bon avec une chaîne ? Tapez eval(), l’outil universel Python d’évaluation.

>>> eval('1 + 1 == 2')
True
>>> eval('1 + 1 == 3')
False
>>> eval('9567 + 1085 == 10652')
True

Mais attendez, il y a plus ! La fonction eval() n’est pas limitée aux expressions booléennes. Elle peut capturer toute expression Python et retourner tout type de données.

>>> eval('"A" + "B"')
'AB'
>>> eval('"MARK".translate({65: 79})')
'MORK'
>>> eval('"AAAAA".count("A")')
5
>>> eval('["*"] * 5')
['*', '*', '*', '*', '*']

Mais attendez, ce n’est pas tout !

>>> x = 5
>>> eval("x * 5")         ①
25
>>> eval("pow(x, 2)")     ②
25
>>> import math
>>> eval("math.sqrt(x)")  ③
2.2360679774997898

① L’expression que prend eval() peut référencer des variables globales définies en-dehors d’ eval(). Si elle est appelée dans une fonction, elle peut référencer des variables locales, aussi.

② Et des fonctions.

③ Et des modules.

Eh, attendez une minute…

>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')")                  ①
'Desktop         Library         Pictures \
 Documents       Movies          Public   \
 Music           Sites'
>>> eval("subprocess.getoutput('rm /some/random/file')")  ②

① Le module subprocess vous permet d’exécuter arbitrairement des commandes shell et d’avoir le résultat en tant que chaîne Python.

② Arbitrairement les commandes shell peuvent avoir des conséquences permanentes.

C’est même pire que cela, parce qu’il y a la fonction globale __import__() qui prend un nom de module en tant que chaîne, importe le module, et lui retourne une référence. Combinée à la puissance d’ eval(), vous pouvez construire une expression simple qui supprimera tous vos fichiers :

>>> eval("__import__('subprocess').getoutput('rm /some/random/file')")  ①

① Maintenant, imaginez la sortie de 'rm -rf ~'. En fait, il n’y aurait pas de sortie, mais il ne resterait plus aucun fichier.

eval() is EVIL

Bien, la partie diabolique est d’évaluer arbitrairement des expressions depuis des sources non vérifiées. Vous ne devriez utiliser eval() que sur une entrée de confiance. Bien sûr, le truc consiste à déterminer ce qui est «fiable». Mais voici quelque chose que je sais avec certitude : vous NE DEVRIEZ PAS prendre ce résolveur alphamétique et le mettre sur Internet en tant que petit service web sympa. Ne faites pas l’erreur de penser : “Mon Dieu, la fonction fait beaucoup de manipulation de chaîne avant d’obtenir une chaîne à évaluer ; je ne peux pas imaginer comment quelqu’un pourrait exploiter cela.” Quelqu’un comprendra comment passer furtivement du code exécutable nuisible après toute cette manipulation de chaîne (des choses étranges se sont produites), et vous pourrez alors dire adieu à votre serveur.

Mais il existe sûrement un moyen d’évaluer les expressions en toute sécurité ? Mettre eval() dans une sandbox où il ne peut accéder à rien ni endommager le reste du monde ? Eh bien, oui et non.

>>> x = 5
>>> eval("x * 5", {}, {})               ①
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name 'x' is not defined
>>> eval("x * 5", {"x": x}, {})         ②
25
>>> import math
>>> eval("math.sqrt(x)", {"x": x}, {})  ③
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name 'math' is not defined

① Le second paramètre et le troisième passés à la fonction eval() agissent dans les espaces de noms global et local pour évaluer l’expression. Dans ce cas, les deux sont vides, ce qui signifie alors que, quand la chaîne "x * 5" est évaluée, il n’y a pas de référence à x ni dans l’espace de nom global ou local, ainsi eval() lève une exception.

② Vous pouvez sélectivement inclure des valeurs spécifiques dans l’espace de noms global en les listant individuellement. Alors ces variables - et seulement celles-là - seront disponibles durant l’évaluation.

③ Même si vous venez d’importer le module math, vous ne pouvez l’inclure dans l’espace de noms à la fonction eval(), ainsi l’évaluation échouera.

Pfff, c’était facile. Laissez-moi faire un service web alphamétique, maintenant !

>>> eval("pow(5, 2)", {}, {})                   ①
25
>>> eval("__import__('math').sqrt(5)", {}, {})  ②
2.2360679774997898

① Même si vous avez passé des dictionnaires vides pour les espaces de noms global et local, toutes les fonctions internes de Python seront toujours disponibles durant l’évaluation. Ainsi pow(5, 2) fonctionne, parce que 5 et 2 sont des littéraux, et que pow() est une fonction interne.

② Malheureusement (et même si vous ne voyez pas pourquoi cela est malheureux, lisez la suite), la fonction __import__() est aussi une fonction interne, ainsi cela fonctionne aussi.

Oui, cela signifie que vous pouvez toujours faire des choses méchantes, même si vous configurez explicitement les espaces de noms global et local pour vider les dictionnaires lors de l’appel à eval() :

>>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})

Oups. Je suis heureux de ne pas avoir créer de service web alphamétique. N’y a-t-il aucun moyen d’utiliser eval() de manière sécurisée ? Eh bien, oui et non.

>>> eval("__import__('math').sqrt(5)",
…     {"__builtins__":None}, {})          ①
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
>>> eval("__import__('subprocess').getoutput('rm -rf /')",
…     {"__builtins__":None}, {})          ②
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<string>", line 1, in <module>
NameError: name '__import__' is not defined

① Pour évaluer des expressions non vérifiées de manière sûre, vous avez besoin de définir un dictionnaire d’espace de noms global qui fait correspondre "__builtins__" à None, une valeur Python null. En interne, les fonctions “built-in” sont contenues dans un pseudo-module appelé "__builtins__". Ce pseudo-module (càd l’ensemble des fonctions internes) est rendu disponible aux expressions évaluées à moins que vous les surchargiez explicitement.

② Soyez sûr que vous surchargiez __builtins__. Non pas __builtin__, __built-ins__, ou toute autre variation qui fonctionnera parfaitement mais qui vous expose à des risques catastrophiques.

Ainsi, eval() est sûr maintenant ? Eh bien, oui et non.

>>> eval("2 ** 2147483647",
…     {"__builtins__":None}, {})          ①

① Même sans accéder à __builtins__, vous pouvez toujours lancer une attaque par déni de service. Par exemple, essayer de lever 2 à la puissance 2147483647 augmentera l’utilisation du CPU de votre serveur à 100% pendant un certain temps. (Si vous essayez cela dans un terminal interactif, appuyez plusieurs fois sur Ctrl-C pour en sortir.) Techniquement cette expression retournera éventuellement une valeur, mais en attendant, votre serveur fera plus rien d’autres.

Enfin, il est possible d’évaluer en toute sécurité des expressions Python non vérifiées, pour une définition du terme «sûr» qui ne s’avère pas très utile dans la vie réelle. C’est bien si vous vous contentez de jouer, et c’est bien si vous ne transmettez que des données fiables. Mais tout autre ne fait que provoquer des ennuis.

Résumons cela ensemble

Pour récapituler : ce programme résoud des puzzles alphamétiques par force brute, càd, par une recherche exhaustive de toutes les solutions possibles Pour faire cela, il faut…

Trouver toutes les lettres dans le puzzle avec la fonction re.findall()
Trouver toutes les lettres uniques dans le puzzle avec sets et la fonction set()
Vérifier qu’il n’y a pas plus de 10 lettres uniques (ce qui signifie que le puzzle est définitivement non résolvable) avec l’instruction assert
Convertir les lettres dans leur équivalent ASCII avec un générateur objet.
Calculer toutes les solutions possibles avec la fonction itertools.permutations()
Convertir chaque solution possible en une expression Python avec la méthode de chaînes translate()
Tester chaque solution possible en évaluant l’expression Python avec la fonction eval()
Retourner la première solution qui évalue à True

… en seulement 14 lignes de code.

Lectures complémentaires (en anglais)

Le module itertools
itertools - Fonctions d’Itérateur pour boucles efficientes
Regarder la Présentation “Easy AI with Python” de Raymond Hettinger au PyCon 2009. semble ne plus être disponible
Recette 576615: Résolveur Alphamétique, un résolveur alphamétique original de Raymond Hettinger pour Python 2
Plus de recettes de Raymond Hettinger dans le référentiel de codes ActiveState
Alphamétiques sur Wikipédia
Index Alphamétiques, incluant beaucoup de puzzles et un générateur à fabriquer soi-même.

Tout plein de remerciements à Raymond Hettinger pour son accord à modifier la licence de son code, ainsi j’ai pu le porter vers Python 3 et l’utiliser comme base de ce chapitre.

*[ASCII]: American Standard Code for Information Interchange - Code américain normalisé pour l’échange d’information *[CPU]: Central Processing Unit - Processeur *[RAM]: Random Access Memory - Mémoire Vive *[càd]: c’est-à-dire

Dive Into Python 3 - 8 : Itérateurs avancés

En plongée

Trouver toutes les occurrences d’un motif

Trouver les items uniques dans une séquence

Créer des assertions

Générateur d’expressions

Calculer les Permutations… La manière facile !

Autres trucs amusants dans le module itertools

Une nouvelle manière de manipuler les chaînes

Évaluer arbitrairement des chaînes en tant qu’expressions Python

Résumons cela ensemble

Lectures complémentaires (en anglais)

Autres trucs amusants dans le module `itertools`