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

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

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 方法很有用哦。

样例代码