第九章：文字游戏
这一章将介绍第二个案例研究，即通过查找具有特定属性的单词来解答字谜游戏。 例如，我们将找出英文中最长的回文单词，以及字符按照字符表顺序出现的单词。 另外，我还将介绍另一种程序开发方法：简化为之前已解决的问题。
读取单词列表
为了完成本章的习题，我们需要一个英语单词的列表。 网络上有许多单词列表，但是最符合我们目的列表之一是由 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 。 有多少个具备这种特征的单词？
搜索
前一节的所有习题有一个共同点；都可以用在搜索一节中看到的搜索模式解决。 举一个最简单的例子：
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）的程序开发方法的一个示例， 也就是说，你认识到当前面临的问题是之前已经解决的问题的一个实例， 然后应用了已有的解决方案。
使用索引进行循环
前一节我用 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 时结束。 每次循环，函数会比较第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 。