深入探究

正如正则表达式让字符串变得强大一样，itertools 模块也让迭代器变得强大。但首先，我想向你展示一个经典的谜题。

1HAWAII + IDAHO + IOWA + OHIO == STATES
2510199 + 98153 + 9301 + 3593 == 621246
3
4H = 5
5A = 1
6W = 0
7I = 9
8D = 8
9O = 3
10S = 6
11T = 2
12E = 4

这类谜题被称为密码算术题（cryptarithms）或字母算术题（alphametics）。这些字母拼出的是真实单词，但如果用 0–9 的数字替换每个字母，它就变成一个有效的算术等式。关键在于找出每个字母对应哪个数字。同一个字母的所有出现必须映射到相同的数字，数字不能重复使用，且任何“单词”都不能以 0 开头。

最著名的字母算术题是 SEND + MORE = MONEY。

在本章中，我们将深入研究一个由雷蒙德·赫廷格（Raymond Hettinger）编写的精彩 Python 程序。这个程序仅用 14 行代码就能解决字母算术题。

1import re
2import itertools
3
4def solve(puzzle):
5    words = re.findall('[A-Z]+', puzzle.upper())
6    unique_characters = set(''.join(words))
7    assert len(unique_characters) <= 10, '字母太多'
8    first_letters = {word[0] for word in words}
9    n = len(first_letters)
10    sorted_characters = ''.join(first_letters) + \
11        ''.join(unique_characters - first_letters)
12    characters = tuple(ord(c) for c in sorted_characters)
13    digits = tuple(ord(c) for c in '0123456789')
14    zero = digits[0]
15    for guess in itertools.permutations(digits, len(characters)):
16        if zero not in guess[:n]:
17            equation = puzzle.translate(dict(zip(characters, guess)))
18            if eval(equation):
19                return equation
20
21if __name__ == '__main__':
22    import sys
23    for puzzle in sys.argv[1:]:
24        print(puzzle)
25        solution = solve(puzzle)
26        if solution:
27            print(solution)

你可以通过命令行运行这个程序。在 Linux 上，操作如下：（根据计算机速度，这些任务可能需要一些时间，且没有进度提示，请耐心等待！）

1you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES"
2HAWAII + IDAHO + IOWA + OHIO = STATES
3510199 + 98153 + 9301 + 3593 == 621246
4
5you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA"
6I + LOVE + YOU == DORA
71 + 2784 + 975 == 3760
8
9you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY"
10SEND + MORE == MONEY
119567 + 1085 == 10652