23五 2013

字母算术的穷举算法

这是一个最开始由Raymond Hettinger写的一个解决字母算术(alphametics)问题的程序，其思想是穷举，在这里将我加了注释的版本发出来。主要是找到所有不同字母，然后将所有数字穷举，利用translate()和eval()计算并验证。

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’ # 如果超过10个不同字母则返回字幕太多
first_letters = {word[0] for word in words} # 将参与计算的元素的第一位分离出来
n = len(first_letters) # 用n统计共有多少个参与计算的元素
sorted_characters = ”.join(first_letters) + \
”.join(unique_characters - first_letters) # 将所有参与运算的字母按“首字母+其他字母”组合
characters = tuple(ord(c) for c in sorted_characters) # 将字母转换成ascii码值
digits = tuple(ord(c) for c in ’0123456789′) # 将数字转化成ascii码值
zero = digits[0]
for guess in itertools.permutations(digits, len(characters)): # 用itertools.permutations生成所有可能
if zero not in guess[:n]:
equation = puzzle.translate(dict(zip(characters, guess))) # 用translate把原字符串进行替换
if eval(equation): # 检测是否正确
return equation
if __name__ == ‘__main__‘:
import sys
sys.argv.append(‘send + more == money’) # 在我的系统里sys.argv[1] = [], so…
for puzzle in sys.argv[1:]:
print(puzzle)
solution = solve(puzzle)
if solution:
print(solution)

照例把我的运行结果放出来（AMD Athlon TK-55，运行时CPU占用50%左右）