# 第九章 案例學習：單詞游戲
本章我們進行第二個案例學習，這一案例中涉及到了用搜索具有某些特征的單詞來猜謎。比如，我們會發現英語中最長的回文詞，然后搜索那些按照單詞表順序排列字母的單詞。我還會給出一種新的程序開發計劃：降低問題的復雜性和難度，還原到以前解決的問題。
## 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)
