--- categories: ['Traduction'] date: 2019-05-16T20:27:01+01:00 description: "Relecture du chapitre 8 - Dive into Python pour la communauté DVP" draft: false lastmod: 2019-05-18T19:07:01+01:00 tags: ['Traduction','Python'] title: "Dive Into Python 3 - 8 : Itérateurs avancés" --- 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 : ```python 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* : ```python 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 !) ```shell 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. ```python >>> 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. ```python >>> 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 : 1. The` sixth s`ick sheikh's sixth sheep's sick. 2. The sixth` sick s`heikh's sixth sheep's sick. 3. The sixth sick` sheikh's s`ixth sheep's sick. 4. The sixth sick sheikh's` sixth s`heep's sick. 5. The sixth sick sheikh's sixth` sheep's s`ick. 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. ```python >>> 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. ```python 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 : ```python >>> assert 1 + 1 == 2 ① >>> assert 1 + 1 == 3 ② Traceback (most recent call last): File "", line 1, in AssertionError >>> assert 2 + 2 == 5, "Only for very large values of 2" ③ Traceback (most recent call last): File "", line 1, in 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 : ```python assert len(unique_characters) <= 10, 'Too many letters' ``` … est équivalente à cela : ```python 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. ```python >>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'} >>> gen = (ord(c) for c in unique_characters) ① >>> gen ② 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]() : ```python 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](https://fr.wikipedia.org/wiki/Permutation)). 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. ```python >>> 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 "", line 1, in 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. ```python >>> 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 "", line 1, in 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` ------------------------------------------------ ```python >>> 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. ```python >>> 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. ```python …continuing from the previous interactive shell… >>> import itertools >>> groups = itertools.groupby(names, len) ① >>> groups >>> list(groups) [(4, ), (5, ), (6, )] >>> 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 ! ```python >>> 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 : ```python >>> 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. ```python 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()`. ```python >>> 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. ```python >>> 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. ```python >>> 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. ```python >>> eval('"A" + "B"') 'AB' >>> eval('"MARK".translate({65: 79})') 'MORK' >>> eval('"AAAAA".count("A")') 5 >>> eval('["*"] * 5') ['*', '*', '*', '*', '*'] ``` Mais attendez, ce n'est pas tout ! ```python >>> 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… ```python >>> 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 : ```python >>> 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](http://www.securityfocus.com/blogs/746)), 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. ```python >>> x = 5 >>> eval("x * 5", {}, {}) ① Traceback (most recent call last): File "", line 1, in File "", line 1, in 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 "", line 1, in File "", line 1, in 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 ! ```python >>> 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()` : ```python >>> 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. ```python >>> eval("__import__('math').sqrt(5)", … {"__builtins__":None}, {}) ① Traceback (most recent call last): File "", line 1, in File "", line 1, in NameError: name '__import__' is not defined >>> eval("__import__('subprocess').getoutput('rm -rf /')", … {"__builtins__":None}, {}) ② Traceback (most recent call last): File "", line 1, in File "", line 1, in 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. ```python >>> 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… 1. [Trouver toutes les lettres dans le puzzle]() avec la fonction `re.findall()` 2. [Trouver toutes les lettres uniques dans le puzzle]() avec sets et la fonction `set()` 3. [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` 4. [Convertir les lettres dans leur équivalent ASCII]() avec un générateur objet. 5. [Calculer toutes les solutions possibles]() avec la fonction `itertools.permutations()` 6. [Convertir chaque solution possible en une expression Python]() avec la méthode de chaînes `translate()` 7. [Tester chaque solution possible en évaluant l'expression Python]() avec la fonction `eval()` 8. Retourner la première solution qui évalue à `True` … en seulement 14 lignes de code. Lectures complémentaires (en anglais) ------------------------ - Le [module `itertools`](https://docs.python.org/3.1/library/itertools.html) - [`itertools` - Fonctions d'Itérateur pour boucles efficientes](https://pymotw.com/2/itertools/) - 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](http://code.activestate.com/recipes/576615-alphametics-solver/?in=user-178123), un résolveur alphamétique original de Raymond Hettinger pour Python 2 - [Plus de recettes de Raymond Hettinger](http://code.activestate.com/recipes/users/178123/) dans le référentiel de codes ActiveState - [Alphamétiques sur Wikipédia](https://en.wikipedia.org/wiki/Verbal_arithmetic) - [Index Alphamétiques](http://www.tkcs-collins.com/truman/alphamet/index.shtml), incluant [beaucoup de puzzles](http://www.tkcs-collins.com/truman/alphamet/alphamet.shtml) et un [générateur à fabriquer soi-même](http://www.tkcs-collins.com/truman/alphamet/alpha_gen.shtml). 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. © 2001–11 Mark Pilgrim *[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