据说 Google 出过一道题目: WWWDOT - GOOGLE = DOTCOM.
其中每个字母代表一个数字, 数字不能重复, 而且最高位的数字不能为 0.
像这样的谜题被称为 cryptarithms 或者字母算术 (alphametics). 字母可以拼出实际的单词, 而如果你把每一个字母都用 0-9 中的某一个数字代替后, 也同样可以拼出一个算术等式. 关键的地方是找出每个字母都映射到了哪个数字. 每个字母所有出现的地方都必须映射到同一个数字, 数字不能重复, 并且 "单词" 不能以 0 开始.
最著名的字母算术谜题是 SEND + MORE = MONEY.
Raymond Hettinger 写过一个令人难以置信的 Python 程序, 这个程序只用 14 行代码来解决任何字母算术谜题.
代码见:
不过该代码是 python 3.x 版本的, 下面是我改过的可以在 2.x 版运行的代码:
- # -*- coding : utf-8 -*-
- # Copyright (c) 2009, Raymond Hettinger, All rights reserved.
- # Ported to Python 2.x and modified by poboke.com
- import re
- import itertools
- import string
- def solve(puzzle):
- #匹配出所有字母, 转为大写
- words = re.findall('[A-Z]+', puzzle.upper())
- #将字母放到集合里
- unique_chars = set(''.join(words))
- #因为数字只有 10 个, 所以如果字母大于 10 个就会出错
- assert len(unique_chars) <= 10, 'Too many letters'
- #将式子的首字母排到前面, 方便判断首字母是否为 0
- first_letters = {Word[0] for Word in words}
- n = len(first_letters)
- sorted_chars = ''.join(first_letters) +''.join(unique_chars - first_letters)
- #所有数字
- digits = '0123456789'
- zero = digits[0]
- #获取所有数字的全排列
- for guess in itertools.permutations(digits, len(sorted_chars)):
- #所有式子的首字母都不能为 0
- if zero not in guess[:n]:
- #将字母替换为数字
- trans = string.maketrans(sorted_chars, ''.join(guess))
- equation = puzzle.translate(trans)
- #如果数字式子的计算结果正确
- if eval(equation):
- print equation
- if __name__ == '__main__':
- import sys
- for puzzle in sys.argv[1:]:
- print(puzzle)
- solve(puzzle)
这个是 python2 的代码, 如果是 python3, 需要修改
string.maketrans 为 str.maketrans
print 加括号
执行结果如下:
- poboke$ python alphametics.py "WWWDOT - GOOGLE == DOTCOM"
- WWWDOT - GOOGLE == DOTCOM
- 777589 - 188103 == 589486
- 777589 - 188106 == 589483
- poboke$ python alphametics.py "WWWDOT - POBOKE == DOTCOM"
- WWWDOT - POBOKE == DOTCOM
- 666435 - 231397 == 435038
- 666435 - 231398 == 435037
- 666180 - 485893 == 180287
- 666180 - 485897 == 180283
- poboke$ python alphametics.py "SEND + MORE == MONEY"
- SEND + MORE == MONEY
- 9567 + 1085 == 10652
- poboke$ python alphametics.py "SIX + SEVEN + SEVEN == TWENTY"
- SIX + SEVEN + SEVEN == TWENTY
- 650 + 68782 + 68782 == 138214
来源: http://www.bubuko.com/infodetail-2928811.html