# 第九章 案例学习：单词游戏
本章我们进行第二个案例学习，这一案例中涉及到了用搜索具有某些特征的单词来猜谜。比如，我们会发现英语中最长的回文词，然后搜索那些按照单词表顺序排列字母的单词。我还会给出一种新的程序开发计划：降低问题的复杂性和难度，还原到以前解决的问题。
## 9.1 读取字符列表
本章练习中，咱们需要用一个英语词汇列表。网上有很多，不过最适合我们的列表并且是共有领域的，莫过于 Grady Ward 这份词汇表，这是 Moby 词典计划的一部分（点击[此链接访问详情](http://wikipedia.org/wiki/Moby_Project)）。这是一份 113，809 个公认的字谜表；也就是公认可以用于字谜游戏以及其他文字游戏的单词。在 Moby 的词汇项目中，该词表的文件名为 113809of.fic；你可以下载一份副本，这里名字简化成 words.txt 了，下载地址[在这里](http://thinkpython2.com/code/words.txt)。
这个文件就是纯文本，所以你可以用文本编辑器打开一下，不过也可以用 Python 来读取。Python 内置了一个叫 open 的函数，接收文件名做参数，返回一个文件对象，你可以用它来读取文件。
```py
>>> fin = open('words.txt')
```
fin 是一个用来表示输入的文件的常用名字。这个文件对象提供了好几种读取的方法，包括逐行读取，这种方法是读取文本中的一整行直到结尾，然后把读取的内容作为字符串返回：
```py
>>> fin.readline()
'aa\r\n'
```
这一列当中的第一个词就是『aa』了，这是一种**熔岩**（译者注：“aa”是夏威夷词汇，音“阿阿”，用来描述表面粗糙的熔岩流。译者本人就是地学专业的，都很少接触这个词，本教材作者真博学啊）。后面跟着的\r\n 的意思代表着有两个转义字符，一个是回车，一个是换行，这样把这个单词从下一个单词分隔开来。
文件对象会记录这个单词在源文件中的位置，所以下次你再调用 readline 的时候，就能得到下一个词了：
```py
>>> fin.readline()
'aah\r\n'
```
下一个词是『aah』，这完全是一个正规的词汇，不要怪异眼神看我哦。另外如果转义字符让你很烦，咱们可以稍加修改来去掉它，用字符串的 strip 方法即可：
```py
>>> line = fin.readline()
>>> word = line.strip()
>>> word
'aahed'
```
在 for 循环中也可以使用文件对象。下面的这个程序读取整个 words.txt 文件，然后每行输出一个词：
```py
fin = open('words.txt')
for line in fin:
word = line.strip()
print(word)
```
## 9.2 练习
下面这些练习都有样例代码。不过你最好在看答案之前先自己对每个练习都尝试一下。
### 练习 1
写一个程序读取 words.txt，然后只输出超过 20 个字母长度的词（这个长度不包括转义字符）。
### 练习 2
在 1939 年，作家厄尔尼斯特·文森特·莱特曾经写过一篇 5 万字的小说《葛士比》，里面没有一个字母 e。因为在英语中 e 是用的次数最多的字母，所以这很不容易的。事实上，不使用最常见的字符，都很难想出一个简单的想法。一开始很慢，不过仔细一些，经过几个小时的训练之后，你就逐渐能做到了。
好了，我不扯淡了。 写一个名字叫做 has_no_e 的函数，如果给定词汇不含有 e 就返回真，否则为假。
修改一下上一节的程序代码，让它只打印单词表中没有 e 的词汇，并且统计一下这些词汇在总数中的百分比例。
### 练习 3
写一个名叫 avoids 的函数，接收一个单词和一个禁用字母组合的字符串，如果单词不含有该字符串中的任何字母，就返回真。 修改一下程序代码，提示用户输入一个禁用字母组合的字符串，然后输入不含有这些字母的单词数目。你能找到 5 个被禁用字母组合，排除单词数最少吗？
### 练习 4
写一个名叫 uses_only 的函数，接收一个单词和一个字母字符串，如果单词仅包含该字符串中的字母，就返回真。你能仅仅用 acefhlo 这几个字母造句子么？或者试试『Hoe alfalfa』?
### 练习 5
写一个名字叫 uses_all 的函数，接收一个单词和一个必需字母组合的字符串，如果单词对必需字母组合中的字母至少都用了一次就返回真。有多少单词都用到了所有的元音字母 aeiou？aeiouy 的呢？
### 练习 6
写一个名字叫 is_abecedarian 的函数，如果单词中所有字母都是按照字母表顺序出现就返回真（重叠字母也是允许的）。有多少这样的单词？
## 9.3 搜索
刚刚的那些练习都有一些相似之处：都可以用我们在 8.6 学过的搜索来解决。下面是一个最简化的例子：
```py
def has_no_e(word):
for letter in word:
if letter == 'e':
return False
return True
```
这个 for 循环遍历了单词的所有字母。如果找到了字母 e，就立即返回假；否则就到下一个字母。如果正常退出了循环，意味着我们没找到 e，就返回真。
你可以使用 in 运算符，把这个函数写得更精简，我之所以用一个稍显麻烦的版本，是为了说明搜索模式的逻辑过程。
avoids 是一个更通用版本的 has_no_e 函数的实现，它的结构是一样的：
```py
def avoids(word, forbidden):
for letter in word:
if letter in forbidden:
return False
return True
```
只要找到了禁用字母就可以立即返回假；如果运行到了循环末尾，就返回真。
uses_only 与之相似，无非是条件与之相反了而已。
```py
def uses_only(word, available):
for letter in word:
if letter not in available:
return False
return True
```
这次不是有一个禁用字母列表，我们这次用一个可用字母列表。如果在单词中发现不在可用字母列表中的，就返回假了。
uses_all 这个函数与之也相似，不过我们转换了单词和字母字符串的角色：
```py
def uses_all(word, required):
for letter in required:
if letter not in word:
return False
return True
```
这次并没有遍历单词中的所有字母，循环遍历了所有指定的字母。如果有任何指定字母没有在单词中出新啊，就返回假。如果你已经像计算机科学家一样思考了，你就应该已经发现了 uses_all 是对之前我们解决过问题的一个实例，你已经写过这个代码了：
```py
def uses_all(word, required):
return uses_only(required, word)
```
、这就是一种新的程序开发规划模式，就是降低问题的复杂性和难度，还原到以前解决的问题，意思是你发现正在面对的问题是之前解决过的问题的一个实例，就可以用已经存在的方案来解决。
## 9.4 用索引循环
上面的章节中我写了各种用 for 循环的函数，因为当时只需要字符串中的字符；这就不需要理会索引。
但 is_abecedarian 这个函数中，我们需要对比临近的两个字母，所以用 for 循环就不那么好写了：
```py
def is_abecedarian(word):
previous = word[0]
for c in word:
if c < previous:
return False
previous = c
return True
```
一种很好的替代思路就是使用递归：
```py
def is_abecedarian(word):
if len(word) <= 1:
return True
if word[0] > word[1]:
return False
return is_abecedarian(word[1:])
```
另外一种方法是用 while 循环：
```py
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 个字符（就当作下一个字符）。
如果下一个字符比当前字符小（字母表排列顺序在当前字符前面），我们就发现这个不符合字母表顺序了，跳出返回假就可以了。
如果一直到循环结尾都没有发现问题，这个词就通过检验了。为了确信循环正确结束了，可以拿单词『flossy』作为例子来试试。单词长度是 6，所以循环终止的时候 i 应该是 4，也就是倒数第二个位置。在最后一次循环中，比较的是倒数第二个和最后一个字母，这正是符合我们设计的。
下面这个是练习 3 的 is_palindrome 的一个版本，使用了两个索引；一个从头开始一直到结尾；另外一个从末尾开始逆序进行。
```py
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
```
或者我们可以把问题解构成之前解决过的样式，然后这样写：
```py
def is_palindrome(word):
return is_reverse(word, word)
```
这里的 is_reverse 这个函数在第 8 章第 11 节讲过哈。
## 9.5 调试
测试程序很难的。本章的函数相对来说还算容易测试，因为你可以手动计算来检验结果。即便如此，选择一系列单词然后检测所有可能的错误，可能不仅是做起来困难，甚至都是不可能完成的任务。
比如以 has_no_e 为例，有两种情况用来检查：有 e 的单词应该返回假，不包含 e 的单词要返回真。你自己想出几个这样的单词来检验一下并不难。
在每个分支内，有一些不那么清晰的次级分支。在那些有 e 的单词中，你还要检测单词中的 e 是在开头结尾还是中间位置。你得试试长词、短词，甚至特别短的词，比如空字符串。空字符串是一个典型特例，这个情况很容易被忽视而成为潜伏的隐患。
（译者注：我知道，这段翻译的简直就是 shit，但是没办法，我这会眼睛特别疼，思路不太清楚，另外这几个练习也不是很难，大家很容易自己搞定。）
除了你自己设计的测试案例之外，你也可以用一个单词列表比如 words.txt 之类的来测试一下你的程序。通过扫描一下输出内容，你也许能够发现错误的地方，但一定要小心：你有可能发现某一种特定错误，但忽略了另外一个，比如包含了不应该包含的单词，但很难发现应该包含但遗漏了单词的情况。
总的来说，测试程序能帮助你找到错误地方，但很难找到一系列特别好的测试案例，或者即便你找了很多案例来测试，也不能确保程序就是正确的。一位传说级别的计算机科学家说：
>程序测试可以用来表明 bug 的存在，但永远不能表明 bug 不存在。
>— Edsger W. Dijkstra
## 9.6 Glossary 术语列表
file object:
A value that represents an open file.
>文件对象：代表了一份打开的文件的值。
reduction to a previously-solved problem:
A way of solving a problem by expressing it as an instance of a previously-solved problem.
>降低问题的复杂性和难度，还原到以前解决的问题：一种解决问题的方法，把问题表达成过去解决过问题的一个特例。
special case:
A test case that is a typical or non-obvious (and less likely to be handled correctly).
>特殊案例：很典型或者不明显的测试用的案例，往往都很不容易正确处理。
## 9.7 练习
### 练习 7
[这个问题](http://www.cartalk.com/content/puzzlers)基于一个谜语，这个谜语在广播节目 Car Talk 上面播放过：
给我一个有三个连续双字母的单词。我会给你一对基本符合的单词，但并不符合。例如， committee 这个单词，C O M M I T E。如果不是有单独的一个 i 在里面，就基本完美了，或者 Mississippi 这个词：M I S I S I P I。如果把这些个 i 都去掉就好了。但有一个词正好是三个重叠字母，而且据我所知这个词可能是唯一一个这样的词。当然有有可能这种单词有五百多个呢，但我只能想到一个。是哪个词呢？写个程序来找一下这个词吧。
[样例代码](http://thinkpython2.com/code/cartalk1.py)
### 练习 8
[这个](http://www.cartalk.com/content/puzzlers)又是一个 Car Talk 谜语：
有一天我在高速路上开着车，碰巧看了眼里程表。和大多数里程表一样，是六位数字的，单位是英里。加入我的车跑过 300，000 英里了，看到的结果就是 3-0-0-0-0-0.
我那天看到的很有趣，我看到后四位是回文的；就是说后四位正序和逆序读是一样的。例如 5-4-4-5 就是一个回文数，所以我的里程表可能读书就是 3-1-5-4-4-5.
过了一英里之后，后五位数字是回文的了。举个例子，可能读书就是 3-6-5-4-5-6。又过了一英里，六个数字中间的数字是回文数了。准备好更复杂的了么？又过了一英里，整个六位数都是回文的了！
那么问题俩了：我最开始看到的里程表的度数应该是多少？
写个 Python 程序来检测一下所有的六位数，然后输出一下满足这些要求的数字。 [样例代码](http://thinkpython2.com/code/cartalk2.py)
### 练习 9
[这个](http://www.cartalk.com/content/puzzlers)又是一个 Car Talk 谜语，你可以用搜索来解决：
最近我看忘了妈妈，然后我们发现我的年龄反过来正好是她的年龄。例如，假如他是 73 岁，我就是 37 岁了。我们好奇这种情况发生多少次，但中间叉开了话题，没有想出来这个问题的答案。
我回家之后，我发现到目前位置我们的年龄互为逆序已经是六次了，我还发现如果我们幸运的话过几年又会有一次，如果我们特别幸运，就还会再有一次这样情况。换句话说，就是总共能有八次。那么问题来了：我现在多大了？
写一个 Python 程序，搜索一下这个谜语的解。提示一下：你可能发现字符串的 zfill 方法很有用哦。
[样例代码](http://thinkpython2.com/code/cartalk3.py)
