python解字母算术问题

    其实是在为了写上一篇blog，在网上搜索python groupby关键字搜索到的一篇文章，是《深入Python 3》中高级迭代器中的一章，文章通过一个python解字母算术的示例代码对其中的关键特性进行了分析，不过原代码时基于python 3的，我这里的环境是python 2.7，于是就比照原代码做了一些修改。

  

    原文章地址：

    首先，介绍下什么是字母算术：

HAWAII + IDAHO + IOWA + OHIO == STATES
510199 + 98153 + 9301 + 3593 == 621246

'''像这样的谜题被称为字母算术，把每一个字母都用0-9中的某一个数字替换后，同样可以拼出一个算术等式'''
H = 5
A = 1
W = 0
I = 9
D = 8
O = 3
S = 6
T = 2
E = 4

    对于求解这样的难题，可以通过仅仅十多行的python代码实现，先把修改后的最终代码放上来：

#!/usr/bin/env python
import re
import itertools
import string

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}
    first_letters = [word[0] for word in words]
    n = len(first_letters)
    sorted_characters = ''.join(first_letters) + \
        ''.join(unique_characters - set(first_letters))

    #characters = tuple(ord(c) for c in sorted_characters)
    #digits = tuple(ord(c) for c in '0123456789')
    characters = sorted_characters
    digits = '0123456789'

    zero = digits[0]
    for guess in itertools.permutations(digits, len(characters)):
#前n个为首字母，保证非0
        if zero not in guess[:n]:
            numbers = ''.join(guess)
            table = string.maketrans(characters,numbers)
            #equation = puzzle.translate(dict(zip(characters, guess)))
            equation = puzzle.translate(table)
            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)

    测试用例：

$ python puzz.py 'I + LOVE + YOU == DORA'
I + LOVE + YOU == DORA
1 + 2784 + 975 == 37

Lyn@HOME ~/python
$ python puzz.py 'SEND + MORE == MONEY'
SEND + MORE == MONEY
9567 + 1085 == 10652

Lyn@HOME ~/python
$ python puzz.py 'HAWAII + IDAHO + IOWA + OHIO == STATES'
HAWAII + IDAHO + IOWA + OHIO == STATES
510199 + 98153 + 9301 + 3593 == 621246

    注：既然是最简单的实现，那么必然方法不可能是最优，这段python代码的实现也就是基于穷举法进行的测试，那么运行时间必然不那么让人满意。

    

    python代码逻辑如下：

1、通过re.findall()函数找到谜题中的所有字母

2、使用集合和set()函数找到谜题中出现的所有不同字母

3、通过assert语句检查是否超过10个不同的字母

4、通过itertools.permutations()函数计算所有可能的解法

5、构建trans table，并使用translate()字符串方法将所有可能的解转换成python表达式

6、使用eval()函数通过求值python表达式来检验解法

7、返回第一个求值结果为True的解法

   这其中比较新颖的用法有两个，一个是itertools.permutations方法，一个是string的translage方法。

1、itertools.permutations()

   这是python中计算排列的一种简单方法，当有一个列表，接着需要将它们拆开然后组合成小一点的列表的所有可能，所有的小列表的大小必须一致。最小是1，最大是元素的总数目，并且不能有重复。这个时候，我们就可以使用permutations()方法

   举个例子：

>>> 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 "", line 1, in <module>
StopIteration

    permutations()函数接受一个序列(列表、深圳字符串)和一个表示要排列的元素的数目的数字，函数返回迭代器，可以在需要的时候遍历使用

    在permutations()的返回序列中，(2,1)和(1,2)是不同的；但在itertools.combinations函数(同样用于返回序列给定长度的所有组合的迭代器)中，(1,2)和(2,1)不会同时返回，因为它认为这两个序列只是顺序不同而已。

2、string.translate

    字符串的翻译从一个转换表开始，通过转换表将一个字符映射到另一个字符，在Python2.7中的使用跟Python3不太一样，首先看下示例：

import string
'''Python 2.7'''
table = string.maketrans('A','0')
print 'MAKE'.translate(table)

output:
MOKE

'''对于多个转换'''
table = string.maketrans('AB','OZ')
print 'MABKE'.translate(table)

output:
MOZKE

'''Python3'''
print 'MABKE'.translate({'A':'0','B':'Z'})

output
MOZKE

    在2.7版本中，使用translate方法之前首先需要手动构建转换表，string.maketrans(from，to)接收两个字符串参数，这两个字符串确定转换关系，转换时根据字符串中字符的index进行对应的匹配；string.translate(table[,deletechars])以上面生成的trans table作为参数完成最终的动作

    在3版本中，可以直接使用dict作为参数完成translate动作，从个人感觉来说，3.0的方法更符合逻辑一些。

    理解了这两个主要的函数，那整个逻辑也就差不多清晰了，按照上文提供的大纲理解上面那段代码应该没什么问题了。