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

  1. import re  
  2. import itertools  
  3.   
  4. def solve(puzzle):   
  5.     words = re.findall(‘[a-z]+’, puzzle.upper())                        # 找到谜题中所有字母   
  6.     unique_characters = set(”.join(words))                             # 找到所有出现的不同字母   
  7.     assert len(unique_characters) <= 10, ‘too many letters’             # 如果超过10个不同字母则返回字幕太多   
  8.     first_letters = {word[0] for word in words}                         # 将参与计算的元素的第一位分离出来   
  9.     n = len(first_letters)                                              # 用n统计共有多少个参与计算的元素   
  10.     sorted_characters = ”.join(first_letters) + \   
  11.         ”.join(unique_characters - first_letters)                      # 将所有参与运算的字母按“首字母+其他字母”组合   
  12.     characters = tuple(ord(c) for c in sorted_characters)               # 将字母转换成ascii码值   
  13.     digits = tuple(ord(c) for c in ’0123456789′)                        # 将数字转化成ascii码值   
  14.     zero = digits[0]   
  15.     for guess in itertools.permutations(digits, len(characters)):       # 用itertools.permutations生成所有可能   
  16.         if zero not in guess[:n]:   
  17.             equation = puzzle.translate(dict(zip(characters, guess)))   # 用translate把原字符串进行替换   
  18.             if eval(equation):                                          # 检测是否正确   
  19.                 return equation   
  20.   
  21. if __name__ == ‘__main__‘:   
  22.     import sys  
  23.     sys.argv.append(‘send + more == money’)                             # 在我的系统里sys.argv[1] = [], so…   
  24.     for puzzle in sys.argv[1:]:   
  25.         print(puzzle)   
  26.         solution = solve(puzzle)   
  27.         if solution:   
  28.             print(solution)  

 

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

image

2 Thoughts on “字母算术的穷举算法

  1. Pingback: PythonChallenge谜题指南(Python3)-1 | the 3rd. Place Edit

Post Navigation