Глава 8. Подробнее об итераторах

Добавлено 11 мая 2020 в 16:46

Блох больших кусают блошки.
Блошек тех – малютки-крошки,
Нет конца тем паразитам,
Как говорят, ad infinitum.
Огастес де Морган

Содержание главы

Погружение

Так же, как регулярные выражения переводят строки на стероиды, модуль itertools переводит на стеродиды итераторы. Но сначала я хочу показать вам классическую головоломку.

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

Такие головоломки называются криптарифмами. Буквы составляют настоящие слова, но, если заменить каждую букву цифрой от 0 до 9, получится еще и правильное математическое равенство. Весь фокус в том, чтобы выяснить, какая буква соответствует какой цифре. Все вхождения каждой буквы должны заменяться одной и той же цифрой, одной цифре не могут соответствовать несколько букв, и «слова» не могут начинаться с цифры 0.

В данной главе мы познакомимся с потрясающей программой на языке Python, написанной Рэймондом Хейттингером. Эта программа решает криптарифмические головоломки и состоит всего из 14 строк кода.

Наиболее известная криптарифмическая головоломка SEND + MORE = MONEY.

Скачать файл alphametics.py.

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)

Вы можете запустить эту программу из командной строки. В Linux это будет выглядеть так. (Выполнение программы может потребовать некоторого времени, зависящего от быстродействия вашего компьютера, а индикатор выполнения в программе отсутствует. Поэтому просто наберитесь терпения.)

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

8.2 Нахождение всех вхождений шаблона

Первая вещь, которую делает эта программа, – это находит все слова в головоломке.

>>> 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']

Строка 2. Модуль re реализует в Python регулярные выражения. В этом модуле есть удобная функция findall(), которая принимает в качестве параметров шаблон регулярного выражения и строку, и находит все подстроки, соответствующие шаблону. В этом случае шаблон соответствует последовательности цифр. Функция findall() возвращает список всех подстрок, соответствующих заданному шаблону.
Строка 4. Здесь регулярное выражение соответствует последовательности букв. И снова возвращаемое значение представляет собой список, каждый элемент которого – это строка, соответствующая шаблону регулярного выражения.

Вот другой пример, над которым вам, возможно, придется поломать голову.

Это самая трудная скороговорка на английском языке.

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

Удивлены? Приведенное регулярное выражение ищет пробел, за которым следуют буква s, кратчайшая возможная последовательность любых символов (.*?), пробел и еще одна буква s. Ну, глядя на эту входную строку, я вижу пять совпадений:

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.

Но функция re.findall() вернула только три вхождения: первое, третье и пятое. Почему? Потому что она не возвращает перекрывающиеся подстроки. Первая подстрока перекрывается со второй, поэтому возвращается только первая строка, а вторая пропускается. Затем третья подстрока перекрывается с четвертой, поэтому возвращается только третья подстрока, а четвертая пропускается. Наконец, возвращается пятая подстрока. Три совпадения, а не пять.

Это не имеет никакого отношения к решению криптарифмов, я просто подумал, что это интересно.

8.3 Нахождение уникальных элементов в последовательностях

Множества делают задачу нахождения уникальных элементов в последовательности тривиальной.

>>> 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'}

Строка 2. Получив список из нескольких строк, функция set() вернет множество уникальных строк из этого списка. Работа этой функции будет более понятной, если вы представите цикл for. Возьмите первый элемент из списка и добавьте его во множество. Второй. Третий. Четвертый. Пятый – постойте-ка, он уже есть во множестве, поэтому его не нужно добавлять, потому что множества в Python не допускают содержание повторяющихся элементов. Шестой. Седьмой – снова дубликат, пропускаем его. Каким будет результат? Все уникальные элементы исходного списка без дубликатов. Исходный список даже сортировать предварительно не нужно.
Строка 5. Тот же подход работает, если функции set() передать строку, а не список, поскольку строка – это просто последовательность символов.
Строка 8. Получив список строк, функция ''.join(a_list) объединяет все эти строки в одну строку.
Строка 10. Этот фрагмент кода, получив список строк, возвращает все уникальные символы, встречающиеся во всех строках.

Наша программа для решения криптарифмов использует эту технику для получения множества всех уникальных букв, используемых в головоломке.

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

Этот список будет позже использоваться для назначения цифр символам, когда программа будет перебирать возможные решения.

8.4 Проверка выполнения условий

Подобно многим языкам программирования, Python содержит оператор подтверждения отсутствия ошибок assert. Вот как он работает.

>>> 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

Строка 1. За словом assert следует любое допустимое в Python выражение. В данном случае, выражение 1 + 1 == 2 возвращает значение True, поэтому assert ничего не делает.
Строка 2. Однако, если выражение возвращает False, assert выбрасывает исключение.
Строка 6. Вы также можете добавить информативное сообщение, которое будет выведено при возбуждении исключения AssertionError.

Поэтому, эта строка кода

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

эквивалентна

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

Программа для решения криптарифмов использует именно это выражение, чтобы прекратить выполнение, если в головоломке содержится более десяти уникальных букв. Поскольку каждая буква соответствует цифре, а цифр всего десять, головоломка с более чем десятью уникальными буквами не может иметь решения.

8.5 Выражения-генераторы

Выражения-генераторы похожи на функции-генераторы, но без функции.

>>> 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)

Строка 2. Выражение-генератор – это как анонимная функция, которая выдает значения. Само выражение выглядит как генератор списков, но оно обернуто не в квадратные, а в круглые скобки.
Строка 3. Выражение-генератор возвращает... итератор.
Строка 5. Вызов next(gen) возвращает следующее значение итератора.
Строка 9. Если вы хотите, то можете пройтись по всем возможным значениям и вернуть кортеж, список или множество, просто направив выражение-генератор функции tuple(), list() или set(). В этих случаях вам не нужно дополнительных скобок – просто передайте функции "голое" выражение ord(c) for c in unique_characters в tuple(), и Python поймет, что это выражение-генератор.

Использование выражений-генераторов вместо генераторов списков помогает сохранить ресурсы центрального процессора и оперативной памяти. Если вы используете список, только чтобы потом передать его (например, в tuple() или set()), используйте выражение-генератор!

Вот еще один способ сделать то же самое, используя функцию-генератор:

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

gen = ord_map(unique_characters)

Выражения-генераторы более компактны, но функционально равноценны.

8.6 Расчет перестановок ... Ленивый способ!

Прежде всего, что такое эти перестановки? Перестановки – это математическое понятие. (На самом деле есть несколько определений, в зависимости от того, с каким разделом математики вы имеете дело. Здесь я говорю о комбинаторике, но если это ни о чем вам не говорит, не беспокойтесь. Как всегда, Википедия – это ваша друг.)

Идея состоит в том, что вы берете список вещей (это могут быть числа, буквы или танцующие медведи) и находите все возможные способы разбить их на более мелкие списки. Все меньшие списки имеют одинаковый размер, который может быть от 1 до общего количества элементов. И ничто не может повторяться. Математики говорят что-то вроде «давайте найдем перестановки 3 разных предметов, взятых по 2 за раз», что означает, что у вас есть последовательность из 3 предметов, и вы хотите найти все возможные упорядоченные пары.

>>> 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

Строка 1. В модуле itertools много всего интересного, включая функцию permutations(), которая выполняет всю тяжелую работу по поиску перестановок.
Строка 2. Функция permutations() принимает последовательность (здесь список из трех целых чисел) и число, которое представляет собой количество элементов, которое вы хотите получить в каждой меньшей группе. Функция возвращает итератор, который вы можете использовать в цикле for или в любом месте, где выполняется итерация. Здесь, чтобы вывести все значения, я покажу использование итератора вручную.
Строка 3. Первая перестановка [1, 2, 3], взятая по 2 за раз, равна (1, 2).
Строка 8. Обратите внимание, что перестановки упорядочены: (2, 1) отличается от (1, 2).
Строка 15. Вот и всё! Это все перестановки из [1, 2, 3], взятые по 2 за раз. Такие пары, как (1, 1) и (2, 2), никогда не появятся, поскольку они содержат повторы, и поэтому они не являются корректными перестановками. Когда перестановок больше нет, итератор вызывает исключение StopIteration.

В модуле itertools много всего интересного.

Функция permutations() не должна принимать только список. Она может принять любую последовательность, даже строку.

>>> 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')]

Строка 2. Строка – это просто последовательность символов. Для поиска перестановок строка 'ABC' эквивалентна списку ['A', 'B', 'C'].
Строка 4. Первая перестановка из 3 элементов ['A', 'B', 'C'], взятая по 3 за раз, – это ('A', 'B', 'C'). Есть еще пять других перестановок – те же три символа в каждом возможном порядке.
Строка 19. Поскольку функция permutations() всегда возвращает итератор, простой способ отладки перестановок заключается в том, чтобы для немедленного отображения всех перестановок передать этот итератор во встроенную функцию list().

8.7 Другие интересные вещи в модуле `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')]

Строка 2. Функция itertools.product() возвращает итератор, содержащий декартово произведение двух последовательностей.
Строка 6. Функция itertools.combination() возвращает итератор, содержащий все возможные комбинации заданной последовательности заданной длины. Она похожа на функцию itertools.permutations(), за исключением того, что комбинации не включают элементы, которые являются дубликатами других элементов в другом порядке. Таким образом, itertools.permutations('ABC', 2) вернет (среди прочего) и ('A', 'B'), и ('B', 'A'); а itertools.combination('ABC', 2) будет не возвращать ('B', 'A'), потому что это дубликат ('A', 'B') в другом порядке.

Скачать файл favorite-people.txt.

>>> 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']

Строка 1. Это выражение возвращает список строк в текстовом файле.
Строка 5. К сожалению (для этого примера), выражение list(open(filename)) также включает возврат каретки в конце каждой строки. Этот генератор списка использует строковый метод rstrip() для удаления пробельных символов с конца каждой строки. (Строки также имеют метод lstrip() для удаления пробельных символов в начале и метод strip(), который выполняет удаление с обеих сторон.)
Строка 9. Функция sorted() берет список и возвращает его отсортированным. По умолчанию сортировка выполняется по алфавиту.
Строка 13. Но функция sorted() также может в качестве параметра key принимать функцию; и тогда она будет выполнять сортировку по этому «ключу». В этом случае функция сортировки – это len(), поэтому сортировка производится по len(каждый элемент). Сначала идут короткие имена, потом длиннее, потом самые длинные.

Какое это имеет отношение к модулю itertools? Я рад, что вы спросили.

…продолжение предыдущего вывода интерактивной оболочки…
>>> 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

Строка 3. Функция itertools.groupby() принимает последовательность и ключевую функцию и возвращает итератор, который генерирует пары. Каждая пара содержит результат выполнения ключевая_функция(каждый_элемент) и другой итератор, содержащий все элементы, для которых результат выполнения ключевой функции будет равен этому ключу.
Строка 10. Вызов функции list() «исчерпал» итератор, т.е. вы уже сгенерировали каждый элемент итератора для создания списка. На итераторе нет кнопки «сброса»; когда вы исчерпали его, вы не можете просто начать всё сначала. Если вы хотите пройтись по нему снова (скажем, в следующем цикле for), вам нужно снова вызвать itertools.groupby(), чтобы создать новый итератор.
Строка 11. В этом примере, дан список имен, уже отсортированных по длине; itertools.groupby(names, len) поместит все четырехбуквенные имена в один итератор, все пятибуквенные имена в другой итератор и так далее. Функция groupby() полностью универсальна; она может группировать строки по первой букве, по значениям их количественных факторов или по любой другой ключевой функции, которую вы только можете придумать.

Функция itertools.groupby() работает только в том случае, если входная последовательность уже отсортирована функцией группировки. В приведенном выше примере мы сгруппировали список имен с помощью функции len(). Это сработало только потому, что входной список уже был отсортирован по длине.

Вы внимательно смотрите?

>>> 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)]

Строка 5. Функция itertools.chain() принимает два итератора и возвращает итератор, который содержит все элементы первого итератора, а затем все элементы второго итератора. (На самом деле, она может принимать любое количество итераторов, и она объединяет их все в порядке их передачи в функцию.)
Строка 7. Функция zip() делает нечто прозаичное, что оказывается чрезвычайно полезным: она принимает любое количество последовательностей и возвращает итератор, который возвращает кортежи первых элементов каждой последовательности, затем вторых элементов каждой последовательности, затем третьих и так далее.
Строка 9. Функция zip() останавливается в конце самой короткой последовательности. range(10, 14) содержит 4 элемента (10, 11, 12 и 13), но range(0, 3) содержит только 3 элемента, поэтому функция zip() возвращает итератор из 3 элементов.
Строка 11. Функция itertools.zip_longest(), напротив, останавливается в конце самой длинной последовательности, вставляя значения None для элементов после конца более коротких последовательностей.

Хорошо, это было все очень интересно, но как это связано с решателем криптарифмов? Вот как:

>>> 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'}

Строка 3. Даны список букв и список цифр (каждая из которых представлена здесь как 1-символьная строка), функция zip создаст пары букв и цифр по порядку.
Строка 6. Почему это круто? Потому что эта структура данных оказывается именно той структурой, которую нужно передать функции dict() для создания словаря, в котором буквы используются как ключи, а связанные с ними цифры – как значения. (Конечно, это не единственный способ реализовать это. Вы можете использовать генератор словарей для создания словаря напрямую.) Хотя в печатном представлении словаря пары перечислены в другом порядке (словари не имеют «порядка»), вы можете видеть, что каждая буква связана с цифрой, основываясь на порядке исходных последовательностей characters и guess.

Решатель криптарифмов использует эту технику для создания словаря, который отображает буквы в головоломке на цифры в решении, для каждого возможного решения.

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)))

Но что это за метод translate()? Теперь мы переходим к действительно веселой части.

8.8 Новый вид манипуляции со строками

У строк в Python есть много методов. Вы узнали о некоторых из этих методов в главе «Строки»: lower(), count() и format(). Теперь я хочу познакомить вас с мощной, но малоизвестной техникой манипуляции со строками: с методом translate().

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

Строка 1. Перевод строки начинается с таблицы перевода, которая представляет собой просто словарь, который отображает один символ на другой. На самом деле, «символ» – это неправильно: таблица перевода, на самом деле, отображает один байт на другой.
Строка 2. Помните, байты в Python 3 являются целыми числами. Функция ord() возвращает значение ascii символа, которое в случае A–Z всегда является байтом от 65 до 90.
Строка 4. Метод translate() для строки берет таблицу перевода и пропускает через нее строку. То есть он заменяет все вхождения ключей таблицы перевода соответствующими значениями. В этом случае МАРК «переводится» на МОРК.

Теперь мы переходим к действительно веселой части.

Какое это имеет отношение к решению головоломок криптарифмов? Как оказалось, самое непосредственное.

>>> 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'

Строка 1. Используя выражение-генератор, мы быстро вычисляем значения байтов для каждого символа в строке. characters – пример значения sorted_characters в функции alphametics.solve().
Строка 4. Используя другое выражение генератора, мы быстро вычисляем байтовые значения для каждой цифры в этой строке. Результат, guess, имеет форму, возвращаемую функцией itertools.permutations() в функции alphametics.solve().
Строка 7. Эта таблица перевода создается путем объединения characters и guess вместе и построения словаря из полученной последовательности пар. Это именно то, что функция alphametics.solve() делает внутри цикла for.
Строка 10. Наконец, мы передаем эту таблицу перевода методу translate() исходной строки головоломки. Это преобразует каждую букву в строке в соответствующую цифру (на основе букв в characters и цифр в guess). Результатом является допустимое выражение Python в виде строки.

Это довольно впечатляюще. Но что вы можете сделать со строкой, которая является допустимым выражением Python?

8.9 Оценка произвольных строк в виде выражений Python

Это последняя часть головоломки (точнее, последняя часть решателя головоломки). После всех этих причудливых манипуляций со строками мы остаемся со строкой типа «9567 + 1085 == 10652». Но это строка, а что хорошего в строке? Введите eval(), универсальный инструмент оценки Python.

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

Но подождите, это еще не всё! Функция eval() не ограничивается булевыми выражениями. Она может обрабатывать любое выражение Python и возвращать любой тип данных.

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

Но подождите, это еще не всё!

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

Строка 2. Выражение, которое принимает eval(), может ссылаться на глобальные переменные, определенные вне eval(). При вызове внутри функции это выражение также может ссылаться на локальные переменные.
Строка 4. И функции.
Строка 7. И модули.

Подождите минутку...

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

Строка 2. Модуль subprocess позволяет запускать произвольные команды оболочки и получать результат в виде строки Python.
Строка 6. Произвольные команды оболочки могут иметь постоянные последствия.

Что еще хуже, это то, что есть глобальная функция __import__(), которая принимает имя модуля в виде строки, импортирует модуль и возвращает ссылку на него. В сочетании с мощью eval() вы можете создать одно выражение, которое уничтожит все ваши файлы:

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

Теперь представьте вывод 'rm -rf ~'. На самом деле не будет никакого вывода, но у вас не останется ни одного файла.

eval() – это ЗЛО

Что ж, зло – это оценка произвольных выражений из ненадежных источников. Вы должны использовать eval() только для доверенного ввода. Конечно, хитрость заключается в том, чтобы выяснить, чему «доверять». Но вот что, что я знаю наверняка: вы НЕ должны брать этот решатель криптарифмов и размещать его в Интернете как забавный маленький веб-сервис. Не делайте ошибку, думая: «Черт возьми, функция выполняет много манипуляций со строками, прежде чем получить строку для оценки; я не могу представить, как кто-то может воспользоваться этим.». Кто-то выяснит, как провести неприятный исполняемый код через все эти манипуляции со строками (странные вещи случаются), и тогда вы можете попрощаться со своим сервером.

Но наверняка есть какой-то способ безопасно оценить выражения? Поместить eval() в песочницу, где он не может получить доступ или нанести вред внешнему миру? Ну, да и нет.

>>> 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

Строка 2. Второй и третий параметры, передаваемые в функцию eval(), действуют как глобальные и локальные пространства имен для оценки выражения. В этом случае они оба пусты, что означает, что при оценке строки "x * 5" нет ссылок на x в глобальном или локальном пространстве имен, поэтому eval() выдает исключение.
Строка 7. Вы можете выборочно включать определенные значения в глобальное пространство имен, перечисляя их по отдельности. Тогда эти (и только эти) переменные будут доступны во время оценки.
Строка 10. Даже если вы только что импортировали модуль math, вы не включили его в пространство имен, переданное функции eval(), поэтому оценка завершилась с ошибкой.

Ну и дела, это было легко. Позвольте мне сделать веб-сервис alphametics прямо сейчас!

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

Строка 1. Даже если вы передали пустые словари для глобального и локального пространств имен, все встроенные функции Python по-прежнему доступны во время оценки. Таким образом, pow(5, 2) работает, потому что 5 и 2 – литералы, а pow() – встроенная функция.
Строка 3. К сожалению (и если вы не понимаете, почему это плохо, читайте дальше), функция __import__() также является встроенной функцией, поэтому она тоже сработает.

Да, это означает, что вы всё еще можете делать плохие вещи, даже если при вызове eval() явно устанавливаете глобальные и локальные пространства имен в виде пустых словарей:

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

Упс. Я рад, что не сделал этот веб-сервис alphametics. Есть ли способ безопасно использовать eval()? Ну, да и нет.

>>> 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

Строка 2. Для безопасной оценки ненадежных выражений вам необходимо определить глобальный словарь пространства имен, который отображает "__builtins__" в None, нулевое значение Python. Внутренние, «встроенные» функции содержатся внутри псевдомодуля, называемого «__builtins__». Этот псевдомодуль (то есть набор встроенных функций) доступен для вычисляемых выражений, только если вы явно не переопределите его.
Строка 8. Убедитесь, что вы переписали __builtins__. Не __builtin__, __built-ins__ или какой-либо другой вариант, который будет работать просто отлично, но подвергать вас катастрофическим рискам.

Так eval() теперь безопасна? Ну, да и нет.

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

Строка 2. Даже не имея доступа к __builtins__, вы все равно можете запустить атаку типа «отказ в обслуживании» (DoS-атака). Например, попытка возвести 2 в 2147483647-ую степень в течение некоторого времени увеличит загрузку процессора вашего сервера до 100%. (Если вы пытаетесь сделать это в интерактивной оболочке, нажмите несколько раз Ctrl+C, чтобы выйти из нее.) Технически это выражение в конечном итоге вернет значение, но в это время ваш сервер ничего не будет делать.

В конце концов, можно безопасно оценить ненадежные выражения Python для некоторого определения «безопасно», которое оказывается не очень полезным в реальной жизни. Хорошо, если вы просто играете в песочнице, и хорошо, если вы всегда передаете ему только доверенный ввод. Но всё остальное просто напрашивается на неприятности.

8.10 Собираем все вместе

Напомним: эта программа решает буквенные головоломки грубым перебором, то есть путем исчерпывающего поиска всех возможных решений. Чтобы сделать это, она...

находит все буквы в головоломке с помощью функции re.findall();
находит все уникальные буквы в головоломке с помощью множеств и функции set();
проверяет наличие более 10 уникальных букв (что означает, что головоломка определенно неразрешима) с помощью утверждения assert;
преобразует буквы в их эквиваленты ASCII с помощью выражения-генератора;
вычисляет все возможные решения с помощью функции itertools.permutations();
преобразует каждое возможное решение в выражение Python с помощью строкового метода translate();
проверяет каждое возможное решение, оценивая выражение Python с помощью функции eval();
возвращает первое решение, которое оценивается как True.

...всего в 14 строках кода.

8.11 Материалы для дальнейшего чтения

Модуль itertools
itertools – итераторные функции для эффективного перебора
Посмотрите выступление Рэймонда Хеттингера «Простой ИИ на Python» на PyCon 2009
Рецепт 576615: Решатель криптарифмов, оригинальное решение Раймона Хеттингера для Python 2
Больше рецептов Рэймонда Хеттингера в хранилище кода ActiveState
Криптарифмы в Википедии
Список криптарифмов, включая множество головоломок и генератор, чтобы сделать свою собственную

Большое спасибо Рэймонду Хеттингеру за согласие повторно лицензировать его код, чтобы я мог перенести его на Python 3 и использовать его в качестве основы для данной главы.