第九章:文字游戏

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

读取单词列表

为了完成本章的习题,我们需要一个英语单词的列表。 网络上有许多单词列表,但是最符合我们目的列表之一是由 Grady Ward收集并贡献给公众的列表,这也是Moby词典项目的一部分 (见:http://wikipedia.org/wiki/Moby_Project )。 它由113,809个填字游戏单词组成,即在填字游戏以及其它文字游戏中被认为有效的单词。 在Moby集合中,该列表的文件名是113809of.fic ;你可以从http://thinkpython.com/code/words.txt 下载一个拷贝,文件名已被简化为 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)

练习

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

习题 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 。 有多少个具备这种特征的单词?

使用索引进行循环

前一节我用 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=0i=len(word)-1 时结束。 每次循环,函数会比较第\(i\)个字符(可以将其认为是当前字符) 和第\(i+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

调试

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

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

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

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

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

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

—Edsger W. Dijkstra

术语表

文件对象(file object):
代表打开文件的变量。
简化为之前已经解决的问题:
通过把未知问题简化为已经解决的问题来解决问题的方法。
特殊用例(special case):
一种不典型或者不明显的测试用例(而且很可能无法正确解决的用例)。

练习题

习题 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

习题 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位数字,然后输出所有符合要求的结果。答案: http://thinkpython2.com/code/cartalk2.py

习题 9-9

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

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

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

编写一个查找谜题答案的Python函数。提示:字符串的 zfill 方法特别有用。 答案:http://thinkpython2.com/code/cartalk3.py

贡献者

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