Python 教程 9 — 文字游戏(附答案)

这一章将介绍第二个案例研究，即通过查找具有特定属性的单词来解答字谜游戏。 例如，我们将找出英文中最长的回文单词，以及字符按照字符表顺序出现的单词。 另外，我还将介绍另一种程序开发方法：简化为之前已解决的问题。

1.读取单词列表 #

为了完成本章的习题，我们需要一个英语单词的列表。 网络上有许多单词列表，但是最符合我们目的列表之一是由 Grady Ward收集并贡献给公众的列表。

它由113,809个填字游戏单词组成，即在填字游戏以及其它文字游戏中被认为有效的单词。 在Moby集合中，该列表的文件名是113809of.fic ；你可以点击下方按钮下载一个拷贝，文件名已被简化为 words.txt。

该文件是纯文本，因此你可以用一个文本编辑器打开它，但是你也可以从Python中读取它。 内建函数 open 接受文件名作为形参，并返回一个 文件对象（file object） ，你可以使用它读取该文件。

>>> fin = open('words.txt')

fin是输入文件对象的一个常用名。该文件对象提供了几个读取方法， 包括 readline ，其从文件中读取字符直到碰到新行，并将结果作为字符串返回：

>>> fin.readline()
'aa\r\n'

在此列表中，第一个单词是“aa”，它是一种岩浆。 序列\r\n代表两个空白字符，回车和换行， 它们将这个单词和下一个分开。

此文件对象跟踪它在文件中的位置， 所以如果你再次调用readline，你获得下一个单词：

>>> fin.readline()
'aah\r\n'

下一个单词是“aah”，它是一个完全合法的单词， 所以不要那样看我。 或者，如果空格困扰了你，我们可以用字符串方法 strip 删掉它：

>>> line = fin.readline()
>>> word = line.strip()
>>> word
'aahed'

你也可以将文件对象用做for循环的一部分。 此程序读取 words.txt 并打印每个单词，每行一个：

fin = open('words.txt')
for line in fin:
    word = line.strip()
    print(word)

2.练习 #

下一节给出了这些习题的答案。 在你看这些答案之前，应该至少试着解答一下。

习题 9-1 #

编程写一个程序，使得它可以读取 words.txt　，然后只打印出那些长度超过20个字符的单词(不包括空格)。

习题 9-2 #

1939年，Ernest Vincent Wright出版了一本名为 《Gadsby》 的小说， 该小说里完全没有使用字符“e”。由于“e”是最常用的英文字符，因此这并容易做到。

事实上，不使用这个最常用的符号(字符e)来构建一个孤立的想法是很难的。 开始进展缓慢，但是经过有意识的、长时间的训练，你可以逐渐地熟练。

好啦，不再说题外话了（让我们开始编程练习）。

写一个叫做has_no_e的函数，如果给定的单词中不包含字符“e”，其返回 True 。

修改上一节中的程序，只打印不包含“e”的单词，并且计算列表中不含“e”单词的比例。

习题 9-3 #

编写一个名为 avoids 的函数，接受一个单词和一个指定禁止使用字符的字符串， 如果单词中不包含任意被禁止的字符，则返回True 。

修改你的程序，提示用户输入一个禁止使用的字符，然后打印不包含这些字符的单词的数量。 你能找到一个5个禁止使用字符的组合，使得其排除的单词数目最少么？

习题 9-4 #

编写一个名为uses_only的函数，接受一个单词和一个字符串。 如果该单词只包括此字符串中的字符，则返回True。 你能只用 acefhlo 这几个字符造一个句子么？ 除了“Hoe alfalfa”外。

习题 9-5 #

编写一个名为uses_all的函数，接受一个单词和一个必须使用的字符组成的字符串。 如果该单词包括此字符串中的全部字符至少一次，则返回True。 你能统计出多少单词包含了所有的元音字符aeiou吗？如果换成aeiouy呢？

习题 9-6 #

编写一个名为is_abecedarian的函数， 如果单词中的字符以字符表的顺序出现（允许重复字符），则返回True 。 有多少个具备这种特征的单词？

3.搜索 #

前一节的所有习题有一个共同点；都可以用在搜索一节中看到的搜索模式解决。 举一个最简单的例子：

def has_no_e(word):
    for letter in word:
        if letter == 'e':
            return False
    return True

for循环遍历 word 中的字符。 如果我们找到字符“e”，那么我们可以马上返回 False ； 否则我们必须检查下一个字符。 如果我们正常退出循环，就意味着我们没有找到一个“e”， 所以我们返回 True 。

你也可以用 in 操作符简化上述函数，但是我之所以一开始写成这样，是因为它展示了搜索模式的逻辑。

avoid　是一个更通用的has_no_e函数，但是结构是相同的：

def avoids(word, forbidden):
    for letter in word:
        if letter in forbidden:
            return False
    return True

一旦我们找到一个禁止使用的字符，我们返回 False ； 如果我们到达循环结尾，我们返回 True 。

除了检测条件相反以外，下面uses_only函数与上面的函数很像：

def uses_only(word, available):
    for letter in word:
        if letter not in available:
            return False
    return True

这里我们传入一个允许使用字符的列表，而不是禁止使用字符的列表。 如果我们在 word 中找到一个不在 available 中的字符，我们就可以返回 False 。

除了将 word 与所要求的字符的角色进行了调换之外， 下面的uses_all函数也是类似的。

def uses_all(word, required):
    for letter in required:
        if letter not in word:
            return False
    return True

该循环遍历需要的字符，而不是遍历 word 中的字符。如果任何要求的字符没出现在单词中， 则我们返回 False 。

如果你真的像计算机科学家一样思考， 你可能已经意识到uses_all是前面已经解决的问题的一个实例， 你可能会写成：

def uses_all(word, required):
    return uses_only(required, word)

这是一种叫做简化为之前已解决的问题（reduction to a previously solved problem）的程序开发方法的一个示例， 也就是说，你认识到当前面临的问题是之前已经解决的问题的一个实例， 然后应用了已有的解决方案。

4.使用索引进行循环 #

前一节我用 for 循环来编写函数，因为我只需要处理字符串中的字符； 我不必用索引做任何事情。

对于下面的is_abecedarian，我们必须比较邻接的字符， 用 for 循环来写的话有点棘手。

def is_abecedarian(word):
    previous = word[0]
    for c in word:
        if c < previous:
            return False
        previous = c
    return True

一种替代方法是使用递归：

def is_abecedarian(word):
    if len(word) <= 1:
        return True
    if word[0] > word[1]:
        return False
    return is_abecedarian(word[1:])

另一中方法是使用 while 循环：

def is_abecedarian(word):
    i = 0
    while i < len(word)-1:
        if word[i+1] < word[i]:
            return False
        i = i+1
    return True

循环起始于 i=0 ， i=len(word)-1 时结束。 每次循环，函数会比较第ii个字符（可以将其认为是当前字符） 和第i+1i+1个字符（可以将其认为是下一个字符）。

如果下一个字符比当前的小（字符序靠前）， 那么我们在递增趋势中找到了断点，即可返回 False 。

如果到循环结束时我们也没有找到一点错误，那么该单词通过测试。 为了让你相信循环正确地结束了，我们用'flossy'这个单词来举例。 它的长度为6，因此最后一次循环运行时，i是4，这是倒数第2个字符的索引。 最后一次迭代时，函数比较倒数第二个和最后一个字符，这正是我们希望的。

下面是is_palindrome函数的一种版本（详见习题6-3） ，其中使用了两个索引；一个从最前面开始并往前上， 另一个从最后面开始并往下走。

def is_palindrome(word):
    i = 0
    j = len(word)-1

    while i<j:
        if word[i] != word[j]:
            return False
        i = i+1
        j = j-1

    return True

或者，我们可以把问题简化为之前已经解决的问题，这样来写:

def is_palindrome(word):
    return is_reverse(word, word)

使用图8-2：堆栈图中描述的 is_reverse。

5.调试 #

程序测试很困难。本章中介绍的函数相对容易测试，因为你可以手工检查结果。 即使这样，选择一可以测试所有可能错误的单词集合，是很困难的，介于困难和不可能之间。

以 has_no_e为例，有两个明显的用例需要检查： 含有‘e’的单词应该返回 False ，不含的单词应该返回 True 。 你应该可以很容易就能想到这两种情况。

在每个用例中，还有一些不那么明显的子用例。 在含有“e”的单词中，你应该测试“e”在开始、结尾以及在中间的单词。 你还应该测试长单词、短单词以及非常短的单词，如空字符串。 空字符串是一个特殊用例（special case），及一个经常出现错误的不易想到的用例。

除了你生成的测试用例，你也可以用一个类似 words.txt 中的单词列表测试你的程序。 通过扫描输出，你可能会捕获错误，但是请注意： 你可能捕获一类错误（包括了不应该包括的单词） 却没能捕获另一类错误（没有包括应该包括的单词）。

一般来讲，测试能帮助你找到错误， 但是生成好的测试用例并不容易， 并且即便你做到了，你仍然不能保证你的程序是正确的。正如一位传奇计算机科学家所说：

程序测试能用于展示错误的存在，但是无法证明不存在错误！

—Edsger W. Dijkstra

6.术语表 #

文件对象（file object）:代表打开文件的变量。

简化为之前已经解决的问题：通过把未知问题简化为已经解决的问题来解决问题的方法。

特殊用例（special case）:一种不典型或者不明显的测试用例(而且很可能无法正确解决的用例)。

7.练习题 #

习题 9-7 #

这个问题基于广播节目 《Car Talk》 (http://www.cartalk.com/content/puzzlers)上介绍的一个字谜：找出一个包含三个连续双字符的单词。我将给你一系列几乎能够符合条件但实际不符合的单词。 比如，committee这个单词，c-o-m-m-i-t-t-e-e。 如果中间没有i的话，就太棒了。 或者Mississippi这个单词: M-i-s-s-i-s-s-i-p-p-i。假如将这些i剔除出去，就会符合条件。但是确实存在一个包含三个连续的单词对， 而且据我了解，它可能是唯一符合条件的单词。 当然也可能有500多个，但是我只能想到一个。那么这个单词是什么？

编写一个程序，找到这个单词。答案： http://thinkpython2.com/code/cartalk1.py 。

"""This module contains a code example related to
Think Python, 2nd Edition
by Allen Downey
http://thinkpython2.com
Copyright 2015 Allen Downey
License: http://creativecommons.org/licenses/by/4.0/
"""

from __future__ import print_function, division


def is_triple_double(word):
    """Tests if a word contains three consecutive double letters.
    
    word: string
    returns: bool
    """
    i = 0
    count = 0
    while i < len(word)-1:
        if word[i] == word[i+1]:
            count = count + 1
            if count == 3:
                return True
            i = i + 2
        else:
            i = i + 1 - 2*count
            count = 0
    return False


def find_triple_double():
    """Reads a word list and prints words with triple double letters."""
    fin = open('words.txt')
    for line in fin:
        word = line.strip()
        if is_triple_double(word):
            print(word)


print('Here are all the words in the list that have')
print('three consecutive double letters.')
find_triple_double()
print('')

习题 9-8 #

下面是另一个来自 《Car Talk》 的谜题（ http://www.cartalk.com/content/puzzlers ）:

“有一天，我正在高速公路上开车，我偶然注意到我的里程表。和大多数里程表一样，它只显示6位数字的整数英里数。 所以，如果我的车开了300,000英里，我能够看到的数字是:3-0-0-0-0-0。

我当天看到的里程数非常有意思。我注意到后四位数字是回文数；也就是说，正序读和逆序读是一样的。例如，5-4-4-5就是回文数。 所以我的里程数可能是3-1-5-4-4-5。

一英里后，后五位数字变成了回文数。例如，里程数可能变成了是3-6-5-4-5-6。又过了一英里后，6位数字的中间四位变成了回文数。 你相信吗？一英里后，所有的6位数字都变成了回文数。

那么问题来了，当我第一次看到里程表时，里程数是多少?”

编写写一个程序，测试所有的6位数字，然后输出所有符合要求的结果。

"""This module contains a code example related to
Think Python, 2nd Edition
by Allen Downey
http://thinkpython2.com
Copyright 2015 Allen Downey
License: http://creativecommons.org/licenses/by/4.0/
"""

from __future__ import print_function, division


def has_palindrome(i, start, length):
    """Checks if the string representation of i has a palindrome.
    i: integer
    start: where in the string to start
    length: length of the palindrome to check for
    """
    s = str(i)[start:start+length]
    return s[::-1] == s

    
def check(i):
    """Checks if the integer (i) has the desired properties.
    i: int
    """
    return (has_palindrome(i, 2, 4) and
            has_palindrome(i+1, 1, 5) and
            has_palindrome(i+2, 1, 4) and
            has_palindrome(i+3, 0, 6))


def check_all():
    """Enumerate the six-digit numbers and print any winners.
    """
    i = 100000
    while i <= 999996:
        if check(i):
            print(i)
        i = i + 1


print('The following are the possible odometer readings:')
check_all()
print()

习题 9-9 #

还是 《Car Talk》 的谜题（ http://www.cartalk.com/content/puzzlers ），你可以通过利用搜索模式解答：

“最近我探望了我的妈妈，我们忽然意识到把我的年纪数字反过来就是她的年龄。比如，如果她73岁，那么我就是37岁。 我们想知道过去这些年来，发生了多少次这样的巧合，但是我们很快偏离到其他话题上，最后并没有找到答案。

回到家后，我计算出我的年龄数字有6次反过来就是妈妈的年龄。 同时，我也发现如果幸运的话，将来几年还可能发生这样的巧合， 运气再好点的话，之后还会出现一次这样的巧合。 换句话说，这样的巧合一共会发生8次。那么，问题来了，我现在多大了？”

编写一个查找谜题答案的Python函数。提示：字符串的 zfill 方法特别有用。

"""This module contains a code example related to
Think Python, 2nd Edition
by Allen Downey
http://thinkpython2.com
Copyright 2015 Allen Downey
License: http://creativecommons.org/licenses/by/4.0/
"""

from __future__ import print_function, division


def str_fill(i, n):
    """Returns i as a string with at least n digits.
    i: int
    n: int length
    returns: string
    """
    return str(i).zfill(n)


def are_reversed(i, j):
    """Checks if i and j are the reverse of each other.
    i: int
    j: int
    returns:bool
    """
    return str_fill(i, 2) == str_fill(j, 2)[::-1]


def num_instances(diff, flag=False):
    """Counts the number of palindromic ages.
    Returns the number of times the mother and daughter have
    palindromic ages in their lives, given the difference in age.
    diff: int difference in ages
    flag: bool, if True, prints the details
    """
    daughter = 0
    count = 0
    while True:
        mother = daughter + diff

        # assuming that mother and daughter don't have the same birthday,
        # they have two chances per year to have palindromic ages.
        if are_reversed(daughter, mother) or are_reversed(daughter, mother+1):
            count = count + 1
            if flag:
                print(daughter, mother)
        if mother > 120:
            break
        daughter = daughter + 1
    return count
    

def check_diffs():
    """Finds age differences that satisfy the problem.
    Enumerates the possible differences in age between mother
    and daughter, and for each difference, counts the number of times
    over their lives they will have ages that are the reverse of
    each other.
    """
    diff = 10
    while diff < 70:
        n = num_instances(diff)
        if n > 0:
            print(diff, n)
        diff = diff + 1

print('diff  #instances')
check_diffs()

print()
print('daughter  mother')
num_instances(18, True)

贡献者 #

1. 翻译：@iphyer
2. 校对：@bingjin
3. 参考：@carfly

推荐阅读 #

有任何问题，可以在公众号后台回复：加群，回答相应验证信息，进入互助群询问。

​Python实用宝典 (pythondict.com)
关注公众号：Python实用宝典
更多精彩文章等你阅读