# Chapter 9 Case study: word play 案例學習：單詞游戲
This chapter presents the second case study, which involves solving word puzzles by searching for words that have certain properties. For example, we’ll find the longest palindromes in English and search for words whose letters appear in alphabetical order. And I will present another program development plan: reduction to a previously-solved problem.
> 本章我們進行第二個案例學習，這一案例中涉及到了用搜索具有某些特征的單詞來猜謎。比如，我們會發現英語中最長的回文詞，然后搜索那些按照單詞表順序排列字母的單詞。我還會給出一種新的程序開發計劃：降低問題的復雜性和難度，還原到以前解決的問題。
## 9.1 Reading word lists 讀取字符列表
For the exercises in this chapter we need a list of English words. There are lots of word lists available on the Web, but the one most suitable for our purpose is one of the word lists collected and contributed to the public domain by Grady Ward as part of the Moby lexicon project (see [Here](http://wikipedia.org/wiki/Moby_Project)). It is a list of 113,809 official crosswords; that is, words that are considered valid in crossword puzzles and other word games. In the Moby collection, the filename is 113809of.fic; you can download a copy, with the simpler name words.txt, from [Here](http://thinkpython2.com/code/words.txt).
> 本章練習中，咱們需要用一個英語詞匯列表。網上有很多，不過最適合我們的列表并且是共有領域的，莫過于 Grady Ward這份詞匯表，這是Moby詞典計劃的一部分（點擊[此鏈接訪問詳情](http://wikipedia.org/wiki/Moby_Project)）。這是一份113，809個公認的字謎表；也就是公認可以用于字謎游戲以及其他文字游戲的單詞。在 Moby 的詞匯項目中，該詞表的文件名為113809of.fic；你可以下載一份副本，這里名字簡化成 words.txt 了，下載地址[在這里](http://thinkpython2.com/code/words.txt)。
This file is in plain text, so you can open it with a text editor, but you can also read it from Python. The built-in function open takes the name of the file as a parameter and returns a file object you can use to read the file.
> 這個文件就是純文本，所以你可以用文本編輯器打開一下，不過也可以用 Python 來讀取。Python 內置了一個叫open 的函數，接收文件名做參數，返回一個文件對象，你可以用它來讀取文件。
```Python
>>> fin = open('words.txt')
>>> fin = open('words.txt')
```
fin is a common name for a file object used for input. The file object provides several methods for reading, including readline, which reads characters from the file until it gets to a newline and returns the result as a string:
> fin 是一個用來表示輸入的文件的常用名字。這個文件對象提供了好幾種讀取的方法，包括逐行讀取，這種方法是讀取文本中的一整行直到結尾，然后把讀取的內容作為字符串返回：
```Python
>>> fin.readline()
>>> fin.readline()
'aa\r\n'
```
The first word in this particular list is “aa”, which is a kind of lava. The sequence \r\n represents two whitespace characters, a carriage return and a newline, that separate this word from the next.
The file object keeps track of where it is in the file, so if you call readline again, you get the next word:
> 這一列當中的第一個詞就是『aa』了，這是一種**熔巖**（譯者注：“aa”是夏威夷詞匯，音“阿阿”，用來描述表面粗糙的熔巖流。譯者本人就是地學專業的，都很少接觸這個詞，本教材作者真博學啊）。后面跟著的\r\n 的意思代表著有兩個轉義字符，一個是回車，一個是換行，這樣把這個單詞從下一個單詞分隔開來。
> 文件對象會記錄這個單詞在源文件中的位置，所以下次你再調用 readline 的時候，就能得到下一個詞了：
```Python
>>> fin.readline()
>>> fin.readline()
'aah\r\n'
```
The next word is “aah”, which is a perfectly legitimate word, so stop looking at me like that. Or, if it’s the whitespace that’s bothering you, we can get rid of it with the string method strip:
> 下一個詞是『aah』，這完全是一個正規的詞匯，不要怪異眼神看我哦。另外如果轉義字符讓你很煩，咱們可以稍加修改來去掉它，用字符串的 strip 方法即可：
```Python
>>> line = fin.readline()
>>> line = fin.readline()
>>> word = line.strip()
>>> word = line.strip()
>>> word
>>> word
'aahed'
```
You can also use a file object as part of a for loop. This program reads words.txt and prints each word, one per line:
> 在 for 循環中也可以使用文件對象。下面的這個程序讀取整個 words.txt 文件，然后每行輸出一個詞：
```Python
fin = open('words.txt')
for line in fin:
word = line.strip()
print(word)
```
## 9.2 Exercises 練習
There are solutions to these exercises in the next section. You should at least attempt each one before you read the solutions.
> 下面這些練習都有樣例代碼。不過你最好在看答案之前先自己對每個練習都嘗試一下。
### Exercise 1 練習1
Write a program that reads words.txt and prints only the words with more than 20 characters (not counting whitespace).
> 寫一個程序讀取 words.txt，然后只輸出超過20個字母長度的詞（這個長度不包括轉義字符）。
### Exercise 2 練習2
In 1939 Ernest Vincent Wright published a 50,000 word novel called Gadsby that does not contain the letter “e”. Since “e” is the most common letter in English, that’s not easy to do.
> 在1939年，作家厄爾尼斯特·文森特·萊特曾經寫過一篇5萬字的小說《葛士比》，里面沒有一個字母e。因為在英語中 e 是用的次數最多的字母，所以這很不容易的。
In fact, it is difficult to construct a solitary thought without using that most common symbol. It is slow going at first, but with caution and hours of training you can gradually gain facility.
> 事實上，不使用最常見的字符，都很難想出一個簡單的想法。一開始很慢，不過仔細一些，經過幾個小時的訓練之后，你就逐漸能做到了。
All right, I’ll stop now.
Write a function called has_no_e that returns True if the given word doesn’t have the letter “e” in it.
> 好了，我不扯淡了。
> 寫一個名字叫做 has_no_e 的函數，如果給定詞匯不含有 e 就返回真，否則為假。
Modify your program from the previous section to print only the words that have no “e” and compute the percentage of the words in the list that have no “e”.
> 修改一下上一節的程序代碼，讓它只打印單詞表中沒有 e 的詞匯，并且統計一下這些詞匯在總數中的百分比例。
### Exercise 3 練習3
Write a function named avoids that takes a word and a string of forbidden letters, and that returns True if the word doesn’t use any of the forbidden letters.
Modify your program to prompt the user to enter a string of forbidden letters and then print the number of words that don’t contain any of them. Can you find a combination of 5 forbidden letters that excludes the smallest number of words?
> 寫一個名叫 avoids 的函數，接收一個單詞和一個禁用字母組合的字符串，如果單詞不含有該字符串中的任何字母，就返回真。
> 修改一下程序代碼，提示用戶輸入一個禁用字母組合的字符串，然后輸入不含有這些字母的單詞數目。你能找到5個被禁用字母組合，排除單詞數最少嗎？
### Exercise 4 練習4
Write a function named uses_only that takes a word and a string of letters, and that returns True if the word contains only letters in the list. Can you make a sentence using only the letters acefhlo? Other than “Hoe alfalfa”?
> 寫一個名叫uses_only的函數，接收一個單詞和一個字母字符串，如果單詞僅包含該字符串中的字母，就返回真。你能僅僅用 acefhlo 這幾個字母造句子么？或者試試『Hoe alfalfa』?
### Exercise 5 練習5
Write a function named uses_all that takes a word and a string of required letters, and that returns True if the word uses all the required letters at least once. How many words are there that use all the vowels aeiou? How about aeiouy?
> 寫一個名字叫uses_all的函數，接收一個單詞和一個必需字母組合的字符串，如果單詞對必需字母組合中的字母至少都用了一次就返回真。有多少單詞都用到了所有的元音字母 aeiou？aeiouy的呢？
### Exercise 6 練習6
Write a function called is_abecedarian that returns True if the letters in a word appear in alphabetical order (double letters are ok). How many abecedarian words are there?
> 寫一個名字叫is_abecedarian的函數，如果單詞中所有字母都是按照字母表順序出現就返回真（重疊字母也是允許的）。有多少這樣的單詞？
## 9.3 Search 搜索
All of the exercises in the previous section have something in common; they can be solved with the search pattern we saw in Section 8.6. The simplest example is:
> 剛剛的那些練習都有一些相似之處：都可以用我們在8.6學過的搜索來解決。下面是一個最簡化的例子：
```Python
def has_no_e(word):
for letter in word:
if letter == 'e':
return False
return True
```
The for loop traverses the characters in word. If we find the letter “e”, we can immediately return False; otherwise we have to go to the next letter. If we exit the loop normally, that means we didn’t find an “e”, so we return True.
> 這個 for 循環遍歷了單詞的所有字母。如果找到了字母e，就立即返回假；否則就到下一個字母。如果正常退出了循環，意味著我們沒找到 e，就返回真。
You could write this function more concisely using the in operator, but I started with this version because it demonstrates the logic of the search pattern.
avoids is a more general version of has_no_e but it has the same structure:
> 你可以使用 in 運算符，把這個函數寫得更精簡，我之所以用一個稍顯麻煩的版本，是為了說明搜索模式的邏輯過程。
> avoids 是一個更通用版本的has_no_e函數的實現，它的結構是一樣的：
```Python
def avoids(word, forbidden):
for letter in word:
if letter in forbidden:
return False
return True
```
We can return False as soon as we find a forbidden letter; if we get to the end of the loop, we return True.
uses_only is similar except that the sense of the condition is reversed:
> 只要找到了禁用字母就可以立即返回假；如果運行到了循環末尾，就返回真。
> uses_only與之相似，無非是條件與之相反了而已。
```Python
def uses_only(word, available):
for letter in word:
if letter not in available:
return False
return True
```
Instead of a list of forbidden letters, we have a list of available letters. If we find a letter in word that is not in available, we can return False.
uses_all is similar except that we reverse the role of the word and the string of letters:
> 這次不是有一個禁用字母列表，我們這次用一個可用字母列表。如果在單詞中發現不在可用字母列表中的，就返回假了。
> uses_all這個函數與之也相似，不過我們轉換了單詞和字母字符串的角色：
```Python
def uses_all(word, required):
for letter in required:
if letter not in word:
return False
return True
```
Instead of traversing the letters in word, the loop traverses the required letters. If any of the required letters do not appear in the word, we can return False.
If you were really thinking like a computer scientist, you would have recognized that uses_all was an instance of a previously-solved problem, and you would have written:
> 這次并沒有遍歷單詞中的所有字母，循環遍歷了所有指定的字母。如果有任何指定字母沒有在單詞中出新啊，就返回假。如果你已經像計算機科學家一樣思考了，你就應該已經發現了uses_all是對之前我們解決過問題的一個實例，你已經寫過這個代碼了：
```Python
def uses_all(word, required):
return uses_only(required, word)
```
This is an example of a program development plan called reduction to a previously-solved problem, which means that you recognize the problem you are working on as an instance of a solved problem and apply an existing solution.
> 這就是一種新的程序開發規劃模式，就是降低問題的復雜性和難度，還原到以前解決的問題，意思是你發現正在面對的問題是之前解決過的問題的一個實例，就可以用已經存在的方案來解決。
## 9.4 Looping with indices 帶索引循環
I wrote the functions in the previous section with for loops because I only needed the characters in the strings; I didn’t have to do anything with the indices.
For is_abecedarian we have to compare adjacent letters, which is a little tricky with a for loop:
> 上面的章節中我寫了各種用 for 循環的函數，因為當時只需要字符串中的字符；這就不需要理會索引。
> 但is_abecedarian這個函數中，我們需要對比臨近的兩個字母，所以用 for 循環就不那么好寫了：
```Python
def is_abecedarian(word):
previous = word[0]
for c in word:
if c < previous:
return False
previous = c
return True
```
An alternative is to use recursion:
> 一種很好的替代思路就是使用遞歸：
```Python
def is_abecedarian(word):
if len(word) <= 1:
return True
if word[0] > word[1]:
return False
return is_abecedarian(word[1:])
```
Another option is to use a while loop:
> 另外一種方法是用 while 循環：
```Python
def is_abecedarian(word):
i = 0
while i < len(word)-1:
if word[i+1] < word[i]:
return False
i = i+1
return True
```
The loop starts at i=0 and ends when i=len(word)-1. Each time through the loop, it compares the ith character (which you can think of as the current character) to the i+1th character (which you can think of as the next).
> 循環開始于 i 等于0，然后在 i 等于len(word)-1的時候結束。每次通過循環的時候，都對比第 i 個字符（你可以就當是當前字符）與第 i+1個字符（就當作下一個字符）。
If the next character is less than (alphabetically before) the current one, then we have discovered a break in the abecedarian trend, and we return False.
> 如果下一個字符比當前字符小（字母表排列順序在當前字符前面），我們就發現這個不符合字母表順序了，跳出返回假就可以了。
If we get to the end of the loop without finding a fault, then the word passes the test. To convince yourself that the loop ends correctly, consider an example like 'flossy'. The length of the word is 6, so the last time the loop runs is when i is 4, which is the index of the second-to-last character. On the last iteration, it compares the second-to-last character to the last, which is what we want.
> 如果一直到循環結尾都沒有發現問題，這個詞就通過檢驗了。為了確信循環正確結束了，可以拿單詞『flossy』作為例子來試試。單詞長度是6，所以循環終止的時候 i 應該是4，也就是倒數第二個位置。在最后一次循環中，比較的是倒數第二個和最后一個字母，這正是符合我們設計的。
Here is a version of is_palindrome (see Exercise 3) that uses two indices; one starts at the beginning and goes up; the other starts at the end and goes down.
> 下面這個是練習3的is_palindrome的一個版本，使用了兩個索引；一個從頭開始一直到結尾；另外一個從末尾開始逆序進行。
```Python
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
```
Or we could reduce to a previously-solved problem and write:
> 或者我們可以把問題解構成之前解決過的樣式，然后這樣寫：
```Python
def is_palindrome(word):
return is_reverse(word, word)
```
Using is_reverse from Section 8.11.
> 這里的is_reverse這個函數在第8章第11節講過哈。
## 9.5 Debugging 調試
Testing programs is hard. The functions in this chapter are relatively easy to test because you can check the results by hand. Even so, it is somewhere between difficult and impossible to choose a set of words that test for all possible errors.
> 測試程序很難的。本章的函數相對來說還算容易測試，因為你可以手動計算來檢驗結果。即便如此，選擇一系列單詞然后檢測所有可能的錯誤，可能不僅是做起來困難，甚至都是不可能完成的任務。
Taking has_no_e as an example, there are two obvious cases to check: words that have an ‘e’ should return False, and words that don’t should return True. You should have no trouble coming up with one of each.
> 比如以has_no_e為例，有兩種情況用來檢查：有 e 的單詞應該返回假，不包含 e 的單詞要返回真。你自己想出幾個這樣的單詞來檢驗一下并不難。
Within each case, there are some less obvious subcases. Among the words that have an “e”, you should test words with an “e” at the beginning, the end, and somewhere in the middle. You should test long words, short words, and very short words, like the empty string. The empty string is an example of a special case, which is one of the non-obvious cases where errors often lurk.
> 在每個分支內，有一些不那么清晰的次級分支。在那些有 e 的單詞中，你還要檢測單詞中的 e 是在開頭結尾還是中間位置。你得試試長詞、短詞，甚至特別短的詞，比如空字符串。空字符串是一個典型特例，這個情況很容易被忽視而成為潛伏的隱患。
> （譯者注：我知道，這段翻譯的簡直就是 shit，但是沒辦法，我這會眼睛特別疼，思路不太清楚，另外這幾個練習也不是很難，大家很容易自己搞定。）
In addition to the test cases you generate, you can also test your program with a word list like words.txt. By scanning the output, you might be able to catch errors, but be careful: you might catch one kind of error (words that should not be included, but are) and not another (words that should be included, but aren’t).
> 除了你自己設計的測試案例之外，你也可以用一個單詞列表比如 words.txt 之類的來測試一下你的程序。通過掃描一下輸出內容，你也許能夠發現錯誤的地方，但一定要小心：你有可能發現某一種特定錯誤，但忽略了另外一個，比如包含了不應該包含的單詞，但很難發現應該包含但遺漏了單詞的情況。
In general, testing can help you find bugs, but it is not easy to generate a good set of test cases, and even if you do, you can’t be sure your program is correct. According to a legendary computer scientist:
Program testing can be used to show the presence of bugs, but never to show their absence!
— Edsger W. Dijkstra
> 總的來說，測試程序能幫助你找到錯誤地方，但很難找到一系列特別好的測試案例，或者即便你找了很多案例來測試，也不能確保程序就是正確的。一位傳說級別的計算機科學家說：
> 程序測試可以用來表明 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 Exercises 練習
### Exercise 7 練習7
[This question](http://www.cartalk.com/content/puzzlers)is based on a Puzzler that was broadcast on the radio program Car Talk :
Give me a word with three consecutive double letters. I’ll give you a couple of words that almost qualify, but don’t. For example, the word committee, c-o-m-m-i-t-t-e-e. It would be great except for the ‘i’ that sneaks in there. Or Mississippi: M-i-s-s-i-s-s-i-p-p-i. If you could take out those i’s it would work. But there is a word that has three consecutive pairs of letters and to the best of my knowledge this may be the only word. Of course there are probably 500 more but I can only think of one. What is the word?
Write a program to find it.
[Solution](http://thinkpython2.com/code/cartalk1.py)
> [這個問題](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)
### Exercise 8 練習8
[Here](http://www.cartalk.com/content/puzzlers)’s another Car Talk Puzzler :
“I was driving on the highway the other day and I happened to notice my odometer. Like most odometers, it shows six digits, in whole miles only. So, if my car had 300,000 miles, for example, I’d see 3-0-0-0-0-0.
“Now, what I saw that day was very interesting. I noticed that the last 4 digits were palindromic; that is, they read the same forward as backward. For example, 5-4-4-5 is a palindrome, so my odometer could have read 3-1-5-4-4-5.
“One mile later, the last 5 numbers were palindromic. For example, it could have read 3-6-5-4-5-6. One mile after that, the middle 4 out of 6 numbers were palindromic. And you ready for this? One mile later, all 6 were palindromic!
“The question is, what was on the odometer when I first looked?”
Write a Python program that tests all the six-digit numbers and prints any numbers that satisfy these requirements. [Solution](http://thinkpython2.com/code/cartalk2.py)
> [這個](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)
### Exercise 9 練習9
[Here](http://www.cartalk.com/content/puzzlers)’s another Car Talk Puzzler you can solve with a search :
“Recently I had a visit with my mom and we realized that the two digits that make up my age when reversed resulted in her age. For example, if she’s 73, I’m 37. We wondered how often this has happened over the years but we got sidetracked with other topics and we never came up with an answer.
“When I got home I figured out that the digits of our ages have been reversible six times so far. I also figured out that if we’re lucky it would happen again in a few years, and if we’re really lucky it would happen one more time after that. In other words, it would have happened 8 times over all. So the question is, how old am I now?”
Write a Python program that searches for solutions to this Puzzler. Hint: you might find the string method zfill useful.
[Solution](http://thinkpython2.com/code/cartalk3.py)
> [這個](http://www.cartalk.com/content/puzzlers)又是一個 Car Talk 謎語，你可以用搜索來解決：
> 最近我看忘了媽媽，然后我們發現我的年齡反過來正好是她的年齡。例如，假如他是73歲，我就是37歲了。我們好奇這種情況發生多少次，但中間叉開了話題，沒有想出來這個問題的答案。
> 我回家之后，我發現到目前位置我們的年齡互為逆序已經是六次了，我還發現如果我們幸運的話過幾年又會有一次，如果我們特別幸運，就還會再有一次這樣情況。換句話說，就是總共能有八次。那么問題來了：我現在多大了？
> 寫一個 Python 程序，搜索一下這個謎語的解。提示一下：你可能發現字符串的 zfill 方法很有用哦。
> [樣例代碼](http://thinkpython2.com/code/cartalk3.py)
- 介紹
- Think Python
- Chapter 0 Preface 前言
- Chapter 1 The way of the program 編程之路
- Chapter 2 Variables, expressions and statements 變量，表達式，語句
- Chapter 3 Functions 函數
- Chapter 4 Case study: interface design 案例學習：交互設計
- Chapter 5 Conditionals and recursion 條件循環
- Chapter 6 Fruitful functions 有返回值的函數
- Chapter 7 Iteration 迭代
- Chapter 8 Strings 字符串
- Chapter 9 Case study: word play 案例學習：單詞游戲
- Chapter 10 Lists 列表
- Chapter 11 Dictionaries 字典
- Chapter 12 Tuples 元組
- Chapter 13 Case study: data structure selection 案例學習：數據結構的選擇
- Chapter 14 Files 文件
- Chapter 15 Classes and objects 類和對象
- Chapter 16 Classes and functions 類和函數
- Chapter 17 Classes and methods 類和方法
- Chapter 18 Inheritance 繼承
- Chapter 19 The Goodies 額外補充