第九章 案例学习：单词游戏

本章我们进行第二个案例学习，这一案例中涉及到了用搜索具有某些特征的单词来猜谜。比如，我们会发现英语中最长的回文词，然后搜索那些按照单词表顺序排列字母的单词。我还会给出一种新的程序开发计划：降低问题的复杂性和难度，还原到以前解决的问题。

9.1 读取字符列表

本章练习中，咱们需要用一个英语词汇列表。网上有很多，不过最适合我们的列表并且是共有领域的，莫过于 Grady Ward这份词汇表，这是Moby词典计划的一部分（点击此链接访问详情）。这是一份113，809个公认的字谜表；也就是公认可以用于字谜游戏以及其他文字游戏的单词。在 Moby 的词汇项目中，该词表的文件名为113809of.fic；你可以下载一份副本，这里名字简化成 words.txt 了，下载地址在这里。

这个文件就是纯文本，所以你可以用文本编辑器打开一下，不过也可以用 Python 来读取。Python 内置了一个叫open 的函数，接收文件名做参数，返回一个文件对象，你可以用它来读取文件。

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

fin 是一个用来表示输入的文件的常用名字。这个文件对象提供了好几种读取的方法，包括逐行读取，这种方法是读取文本中的一整行直到结尾，然后把读取的内容作为字符串返回：

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

这一列当中的第一个词就是『aa』了，这是一种熔岩（译者注：“aa”是夏威夷词汇，音“阿阿”，用来描述表面粗糙的熔岩流。译者本人就是地学专业的，都很少接触这个词，本教材作者真博学啊）。后面跟着的\r\n 的意思代表着有两个转义字符，一个是回车，一个是换行，这样把这个单词从下一个单词分隔开来。

文件对象会记录这个单词在源文件中的位置，所以下次你再调用 readline 的时候，就能得到下一个词了：

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

下一个词是『aah』，这完全是一个正规的词汇，不要怪异眼神看我哦。另外如果转义字符让你很烦，咱们可以稍加修改来去掉它，用字符串的 strip 方法即可：

  1. >>> line = fin.readline()
  2. >>> word = line.strip()
  3. >>> word
  4. 'aahed'

在 for 循环中也可以使用文件对象。下面的这个程序读取整个 words.txt 文件，然后每行输出一个词：

  1. fin = open('words.txt')
  2.     for line in fin:
  3.         word = line.strip()
  4.         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学过的搜索来解决。下面是一个最简化的例子：

  1. def has_no_e(word):
  2.     for letter in word:
  3.         if letter == 'e':
  4.             return False
  5.     return True

这个 for 循环遍历了单词的所有字母。如果找到了字母e，就立即返回假；否则就到下一个字母。如果正常退出了循环，意味着我们没找到 e，就返回真。

你可以使用 in 运算符，把这个函数写得更精简，我之所以用一个稍显麻烦的版本，是为了说明搜索模式的逻辑过程。

avoids 是一个更通用版本的has_no_e函数的实现，它的结构是一样的：

  1. def avoids(word, forbidden):
  2.     for letter in word:
  3.         if letter in forbidden:
  4.             return False
  5.     return True

只要找到了禁用字母就可以立即返回假；如果运行到了循环末尾，就返回真。

uses_only与之相似，无非是条件与之相反了而已。

  1. def uses_only(word, available):
  2.     for letter in word:
  3.         if letter not in available:
  4.             return False
  5.     return True

这次不是有一个禁用字母列表，我们这次用一个可用字母列表。如果在单词中发现不在可用字母列表中的，就返回假了。

uses_all这个函数与之也相似，不过我们转换了单词和字母字符串的角色：

  1. def uses_all(word, required):
  2.     for letter in required:
  3.         if letter not in word:
  4.             return False
  5.     return True

这次并没有遍历单词中的所有字母，循环遍历了所有指定的字母。如果有任何指定字母没有在单词中出新啊，就返回假。如果你已经像计算机科学家一样思考了，你就应该已经发现了uses_all是对之前我们解决过问题的一个实例，你已经写过这个代码了：

  1. def uses_all(word, required):
  2.     return uses_only(required, word)

、这就是一种新的程序开发规划模式，就是降低问题的复杂性和难度，还原到以前解决的问题，意思是你发现正在面对的问题是之前解决过的问题的一个实例，就可以用已经存在的方案来解决。

9.4 用索引循环

上面的章节中我写了各种用 for 循环的函数，因为当时只需要字符串中的字符；这就不需要理会索引。

但is_abecedarian这个函数中，我们需要对比临近的两个字母，所以用 for 循环就不那么好写了：

  1. def is_abecedarian(word):
  2.     previous = word[0]
  3.     for c in word:
  4.         if c < previous:
  5.             return False
  6.         previous = c
  7.     return True

一种很好的替代思路就是使用递归：

  1. def is_abecedarian(word):
  2.     if len(word) <= 1:
  3.         return True
  4.     if word[0] > word[1]:
  5.         return False
  6.     return is_abecedarian(word[1:])

另外一种方法是用 while 循环：

  1. def is_abecedarian(word):
  2.     i = 0
  3.     while i < len(word)-1:
  4.         if word[i+1] < word[i]:
  5.         return False
  6.         i = i+1
  7.     return True

循环开始于 i 等于0，然后在 i 等于len(word)-1的时候结束。每次通过循环的时候，都对比第 i 个字符（你可以就当是当前字符）与第 i+1个字符（就当作下一个字符）。

如果下一个字符比当前字符小（字母表排列顺序在当前字符前面），我们就发现这个不符合字母表顺序了，跳出返回假就可以了。

如果一直到循环结尾都没有发现问题，这个词就通过检验了。为了确信循环正确结束了，可以拿单词『flossy』作为例子来试试。单词长度是6，所以循环终止的时候 i 应该是4，也就是倒数第二个位置。在最后一次循环中，比较的是倒数第二个和最后一个字母，这正是符合我们设计的。

下面这个是练习3的is_palindrome的一个版本，使用了两个索引；一个从头开始一直到结尾；另外一个从末尾开始逆序进行。

  1. def is_palindrome(word):
  2.     i = 0
  3.     j = len(word)-1
  4.     while i<j:
  5.         if word[i] != word[j]:
  6.             return False
  7.         i = i+1
  8.         j = j-1
  9.     return True

或者我们可以把问题解构成之前解决过的样式，然后这样写：

  1. def is_palindrome(word):
  2.     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

这个问题基于一个谜语，这个谜语在广播节目 Car Talk 上面播放过：

给我一个有三个连续双字母的单词。我会给你一对基本符合的单词，但并不符合。例如， committee 这个单词，C O M M I T E。如果不是有单独的一个 i 在里面，就基本完美了，或者Mississippi 这个词：M I S I S I P I。如果把这些个 i 都去掉就好了。但有一个词正好是三个重叠字母，而且据我所知这个词可能是唯一一个这样的词。当然有有可能这种单词有五百多个呢，但我只能想到一个。是哪个词呢？写个程序来找一下这个词吧。

样例代码

练习8

这个又是一个 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 程序来检测一下所有的六位数，然后输出一下满足这些要求的数字。 样例代码

练习9

这个又是一个 Car Talk 谜语，你可以用搜索来解决：

最近我看忘了妈妈，然后我们发现我的年龄反过来正好是她的年龄。例如，假如他是73岁，我就是37岁了。我们好奇这种情况发生多少次，但中间叉开了话题，没有想出来这个问题的答案。

我回家之后，我发现到目前位置我们的年龄互为逆序已经是六次了，我还发现如果我们幸运的话过几年又会有一次，如果我们特别幸运，就还会再有一次这样情况。换句话说，就是总共能有八次。那么问题来了：我现在多大了？

写一个 Python 程序，搜索一下这个谜语的解。提示一下：你可能发现字符串的 zfill 方法很有用哦。

样例代码