我的天

前面还在沾沾自喜我写出来的脚本运行效率战胜了参考答案，但这道题目我是看着参考答案都不知道他们在说什么。如果只是一个词，我的确可以列举出它一次减少一个字母可以出现的所有可能，但怎么知道上一层可能和这一层的哪个配套？？？我花了2天时间去研究、消化答案。一边搞清楚答案为什么这样，另一边考虑有没有其它容易吃透的表达方式。这道题之所以让我非常纠结，根本的原因是我想不透到底我可以用什么手段实现。没有可以实现的逻辑，就不会有可行的编程。

Exercise 4: Here’s another Car Talk Puzzler (http://www.cartalk.com/content/puzzlers): What is the longest English word, that remains a valid English word, as you remove its letters one at a time? Now, letters can be removed from either end, or the middle, but you can’t rearrange any of the letters. Every time you drop a letter, you wind up with another English word. If you do that, you’re eventually going to wind up with one letter and that too is going to be an English word—one that’s found in the dictionary. I want to know what’s the longest word and how many letters does it have? I’m going to give you a little modest example: Sprite. Ok? You start off with sprite, you take a letter off, one from the interior of the word, take the r away, and we’re left with the word spite, then we take the e off the end, we’re left with spit, we take the s off, we’re left with pit, it, and I. Write a program to find all words that can be reduced in this way, and then find the longest one. This exercise is a little more challenging than most, so here are some suggestions: You might want to write a function that takes a word and computes a list of all the words that can be formed by removing one letter. These are the “children” of the word. Recursively, a word is reducible if any of its children are reducible. As a base case, you can consider the empty string reducible. The wordlist I provided, words.txt, doesn’t contain single letter words. So you might want to add “I”, “a”, and the empty string. To improve the performance of your program, you might want to memoize the words that are known to be reducible. Solution: http://thinkpython2.com/code/reducible.py.

最终，我觉得自己总算消化了，顺便画了个思维导图帮助大家理解到底分解到什么程度叫做完成，什么状态叫做分解失败。[”]和[]是两种不同的东西！！！！！！

is_reducible()是最关键的函数，memos用在这里，memos初始设置了known[”] = [”]也很关键，这是个守卫模式，没有守卫is_reducible()根本没法玩。这个脚本里的5个函数，除了一开始的创建字典函数，其余函数都可以单独测试，把一个固定单词放进去脚手架测试，可以帮助理解。cut_letter()，is_reducible()和all_reducible()这三个函数最终返回的都是列表，它们的样式都是类似的。希望我理解过程中的注释能帮助到有需要的人。PS一句：参考答案的打印效果让人很晕，我修改版的打印效果很美丽:)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

from time import time
def set_dict(fin):
    d = {}
    for line in fin:
        word = line.strip()
        d[word] = 0
    for word in ['a', 'i', '']:
        d[word] = 0
    return d
def cut_letter(word, d): # 生成子单词，返回列表
    l = []
    for i in range(len(word)):
        new_word = word[:i] + word[i+1:]
        if new_word in d:
            l.append(new_word)
    return l # ['']长度为1，[]长度为0，无子词不能分解时返回[]，'a'返回['']
def is_reducible(word, d): # 判断能否生成无限子单词，返回列表
    if word in known: # 守卫模式下，''空字符串被列入初始字典，不列入永远会被递归到[]，无果
        return known[word]
    # if word == '': # 不用memos的时候，需要加入这句守卫
    #     return ['']
    l = []
    for new_word in cut_letter(word, d):
        if len(is_reducible(new_word, d)) > 0:
            l.append(new_word)
    known[word] = l
    return l
def all_reducible(d): # 收集所有无限子单词的单词，返回列表
    l = []
    for word in d:
        if len(is_reducible(word, d)) > 0: # 有列表，即有无限子单词
            l.append((len(word), word)) # 列表含有N个元组，元组里有2个元素，1为单词的字母数量，2为单词本尊
    new_l = sorted(l, reverse = True) # 每次减少一个字母，单词的字母越多当然就能降解出越多层了
    return new_l
def word_list(word): # 打印单词及子单词
    if len(word) == 0: # 最后一个进入is_reducible()的是['']，对应l[0]为无，打印结束
        return
    print(word)
    l = is_reducible(word, d) # 因为是被鉴定过词汇表里的词，所以必定有无限子单词
    word_list(l[0]) # 子单词有多个时只选第1个
known = {} # memos实际上只在is_reducible()起作用，除了提高效率，还能用作守卫
known[''] = [''] # 因为is_reducible()返回的是列表，所以即便是空字符串，键值也必须是列表！
fin = open('words.txt')
start = time()
d = set_dict(fin) # 普通的字典，键为单词，键值为0
words = all_reducible(d) # 列表，元组，2元素
for i in range(5):
    word_list(words[i][1]) # 列表里第某个元组的第2个元素
end = time()
print(end - start)
# complecting
# completing
# competing
# compting
# comping
# coping
# oping
# ping
# pig
# pi
# i
# twitchiest
# witchiest
# withiest
# withies
# withes
# wites
# wits
# its
# is
# i
# stranglers
# strangers
# stranger
# strange
# strang
# stang
# tang
# tag
# ta
# a
# staunchest
# stanchest
# stanches
# stances
# stanes
# sanes
# anes
# ane
# ae
# a
# restarting
# restating
# estating
# stating
# sating
# sting
# ting
# tin
# in
# i
# 0.6459996700286865
# 无memos 1.5830001831054688， 有memos 0.6459996700286865

一开始，我自己写的脚本能运行，但慢到怀疑人生。吃了个饭，折腾了半个小时后，字母表才处理到b而已，显然这是个失败的操作。我的做法是常规地为词汇表建立字典，然后历遍字典里的每个单词，单词进入函数后跟字典的另一个单词比较，比较方法是把单词（即字符串）打散为字符列表然后排列，如果排列一致，且被比较的单词小于拿去比的单词，它们就是一伙的，贴在被比较的单词列表下。列表长度大于2就返回列表然后打印。这样是可以选出异构词的，但非常非常慢！

看过参考答案之后我跳起来了，他们用了一句”.join(lists)，这等于是把列表str重新粘成一个字符串，我那个去！他们把单词用列表打散重排再粘回去，最关键的是，这个唯一的重排字符串他们在建立字典的时候就作为key，所有与之有一样字符的全部被看作小弟被放置这个键的键值里。字典还是字典，但字典的键成了规则字符串，键值则是排列组合过的词汇表。我根本没想到啊，怎么可能想得到呢！！！！！

题目要求倒序打印，然后要求找出能组成最多异构词的8个字母。但实际上参考答案的输出问非所答，比如没有倒序，比如只是把8个字母的异构词摆出来，没确切告诉你最多的是什么。

Exercise 2: More anagrams! Write a program that reads a word list from a file (see Section 9.1) and prints all the sets of words that are anagrams. Here is an example of what the output might look like:
[‘deltas’, ‘desalt’, ‘lasted’, ‘salted’, ‘slated’, ‘staled’]
[‘retainers’, ‘ternaries’]
[‘generating’, ‘greatening’]
[‘resmelts’, ‘smelters’, ‘termless’]
Hint: you might want to build a dictionary that maps from a collection of letters to a list of words that can be spelled with those letters. The question is, how can you represent the collection of letters in a way that can be used as a key? Modify the previous program so that it prints the longest list of anagrams first, followed by the second longest, and so on. In Scrabble a “bingo” is when you play all seven tiles in your rack, along with a letter on the board, to form an eight-letter word. What collection of 8 letters forms the most possible bingos? Solution: http://thinkpython2.com/code/anagram_sets.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

from time import time
def sorted_anagram(d):
    l = []
    for key in d:
        if len(d[key]) > 1:
            l.append((len(d[key]), d[key])) # 这是个由列表创建的元组？
    return sorted(l, reverse = True) # 倒序神马真折腾
def eight_letters(d, num):
    global length # 全局变量都用上了，就为了记录个最大值
    new_l = []
    for key in d:
        if len(key) == num and len(d[key]) > 1:
           new_l.append((len(d[key]), d[key]))
           if len(d[key]) >= length:
               length = len(d[key])
    return sorted(new_l)
def sorted_letters(word):
    list_word = sorted(list(word)) # 先把字符串打散为字符列表，然后排序
    reword =''.join(list_word) # 再把字符列表回粘成字符串
    return reword
def set_dict(fin):
    d = {}
    for line in fin:
        word = line.strip()
        reword = sorted_letters(word) # 打散重排相当关键，必须在建立字典时就做！！！
        if reword not in d:
            d[reword] = [word] # 字典的键已经不是单词，是纯粹的规律字符串
        else:
            d[reword].append(word) # 字典的键值才是词汇表里的单词
    return d
fin = open('words.txt')
length = 0
count = 0
start = time()
d = set_dict(fin)
for item in sorted_anagram(d):
    print(item)
    count += 1
print(count)
for item in eight_letters(d, 8):
    if item[0] == length:
        print(item)
end = time()
print(end - start)
# ......
# (2, ['abacas', 'casaba'])
# (2, ['aba', 'baa'])
# (2, ['aals', 'alas'])
# (2, ['aal', 'ala'])
# (2, ['aahed', 'ahead'])
# (2, ['aah', 'aha'])
# 10157 # 全体异构词
# (7, ['angriest', 'astringe', 'ganister', 'gantries', 'granites', 'ingrates', 'rangiest'])
# 异构词最多的8字母单词（共7个异构词）
# 0.6079998016357422

不搞复杂的，不用超纲的方法做感觉上很简单的事其实不简单。搞明白这个练习后，列表、字典、元组的相爱相杀我算是有点明白了。感谢那个我觉得过于复杂的参考答案，逼我折腾出了我自己的版本。

开心！居然习题1就用上了zip这个这章书最后才提到的大招。字典的键值对互换变得如此简单，我的脑洞又开大了。

Exercise 1: Write a function called most_frequent that takes a string and prints the letters in decreasing order of frequency. Find text samples from several different languages and see how letter frequency varies between languages. Compare your results with the tables at http://en.wikipedia.org/wiki/Letter_frequencies. Solution: http://thinkpython2.com/code/most_frequent.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def most_frequent(sth):
    d = {}
    for letter in sth: # 字符串转为字符映射到频率的字典
        d[letter.lower()] = d.get(letter.lower(), 0) + 1 # 大写的你给我降为小写
    t = tuple(zip(d.values(), d.keys())) # 用zip互换字典的键和键值，生成元组（也可以生成列表，但生成新字典你会哭死）
    return sorted(t, reverse = True) # 以第一元素降序输出
sth = 'This chapter presents one more built-in type, the tuple, and then shows how lists, dictionaries, and tuples work together. I also present a useful feature for variable-length argument lists, the gather and scatter operators.'
t = most_frequent(sth)
for item in t:
    print(item) # 原汁原味输出元组好，因为空格不用''圈着都不知道那里有东西
# (33, ' ')
# (25, 'e')
# (23, 't')
# (16, 's')
# (15, 'r')
# (14, 'a')
# (11, 'o')
# (11, 'n')
# (10, 'i')
# (10, 'h')
# (9, 'l')
# (7, 'u')
# (7, 'p')
# (5, ',')
# (4, 'g')
# (4, 'd')
# (3, 'w')
# (3, 'f')
# (3, 'c')
# (2, 'm')
# (2, 'b')
# (2, '.')
# (2, '-')
# (1, 'y')
# (1, 'v')
# (1, 'k')

我觉得必定把我搞死的筛选词汇表里的二锁三锁单词，居然不怎么费劲就做出来了。

第一次，我在里面用了一个很傻的循环，其实根本就没有必要。可以不用自己的循环就千万不要在词汇表搜索时多用，但我的第一次尝试并不是毫无意义的，，因为已经能得出结果了，而且结果是对的，虽然非常慢，慢到我无法忍受程序继续运行下去。然后，我把要搜索的东西全部都丢到二分法搜索里面，循环只剩下一个必须做的，因为要把词汇表过一遍。第一次做二词互锁的时候，我在一个循环里套了两个if，然后我又把那两个if做成平行的，其实也就是把两个本来嵌套起来的条件用一个and连接起来，很多时候我们都需要这么干。因为除了要二锁，还要考虑三锁，显然人肉去做这些判断，写一大堆一模一样的东西实在太无聊，所以我又自定义了一个新函数，把需要判断的东西全部都丢掉里面，最终返回True或者False。其实，之前我已经考虑过要直接这么干，但因为前天在做搜索回文词的时候我已经得出了回文词的索引，所以直接用就好。我个人觉得，效果是差不多的。

在搜索互锁单词的时候，输出时我用的是字符串的变体。因为二分法搜索被我丢到了一个多条件复合的判断函数里面，所以返回的东西，只有True与False。如果全部都是True的话，就意味着那些单词辩题应该全部都OK没问题。也正是因为输出的东西已经没有索引返回，所以结果我直接使用单词的变体表示。这样的效果很惊人。之前我套用了两个if，然后我写了一个判断函数把条件都含进去了，这样的改进让脚本的运行时间缩短了一半。如果一开始我没有见过两秒多的那个效果，我肯定不会为一秒多的那个惊叹。这是我一步一步琢磨出来了的。

首先是实现得出结果，然后是对语句进行重构，接下要让这个程序适用于二、三词互锁，所以我做的东西是泛化。一开始我把所有判断都写在主程序里，后来我又把它分出一个函数，也就是封装。无意之中，我在执行着Think Python第四章里说到的开发方法：写小程序、封装、泛化、重构。无论是大程序还是小程序，其实都会经历这些。我会从一些我最熟悉的东西开始实现功能。但是我最熟悉的东西不意味着效率一定会高。循环再循环以后，得出一个词都要好几秒时间，实在让人难以接受，尤其当这个词到下个时中间要相隔几秒甚至是十几秒才有反应的时候。这就逼迫着我一定要改进，不同的语句能实现同样的功能，但是它们之间的效率是非常不一样。

大家都在用着二分法的思路去搜索，但是我的脚本就比参考答案快接近30倍。单词一蹦出来，我就知道我一定会比参考答案快。因为我的程序里，单词是噼里啪啦完全没有停顿就全部出来的，而参考答案的词语出来的时候虽然不会一直有，但总有一些顿卡现象，那相对于我的程序来说，就像是慢镜头。

我从来没有想过自己能做得比参考答案还要好，或许他们要做到的并不是有多快。相比于不是二分法的搜索，二分法已经很快了。他们想做到的，大概是用最简练的语言，用模块化的方法实现功能，效率倒不是他们最看重的，因为做搜索词汇表这种事在列表里完成肯定比不上直接上字典。但是，如果不曾在列表里面死去活来，又怎么会体验到字典的神奇。

无论我的二分法搜索写得多么高效，肯定还是不如字典的。我体验过用词典进行斐波那契常数计算。当要计算第40个的时候，一般的递归和字典递归简直就是天渊之别。

如果不曾经历，不曾被整得很惨，我大概就不能说自己真学会了那个东西。

战胜参考答案从昨晚开始貌似就成了我最大的快乐。互锁词的生成要比昨天的回文词复杂一些，因为这意味着搜索的次数更多了。虽然都是用二分法搜索的思路，但我就是要比参考答案快接近30倍肿么破。至于为什么会这样，我没有研究，或许我应该仔细研究一下。

10万条的单词表里：二词互锁1254条，我用时1.4秒，参考答案用时39.1秒；三词互锁991条，我用时1.5秒，参考答案用时43.4秒。一箩筐的成就感啊啊啊啊啊啊啊～～～

Exercise 12: Two words “interlock” if taking alternating letters from each forms a new word. For example, “shoe” and “cold” interlock to form “schooled”. Solution: http://thinkpython2.com/code/interlock.py. Credit: This exercise is inspired by an example at http://puzzlers.org. Write a program that finds all pairs of words that interlock. Hint: don’t enumerate all pairs! Can you find any words that are three-way interlocked; that is, every third letter forms a word, starting from the first, second or third?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import time
def in_bisect(library, first, last, myword): # 二分法搜索，10万数据查询最多只需不到20步
    if first > last: # 这是一句拯救了我的条件
        return -1
    else:
        mid = (first + last)//2
        if myword == library[mid]:
            return mid
        elif library[mid] > myword:
            return in_bisect(library, first, mid-1, myword)
        else:
            return in_bisect(library, mid+1, last, myword)
def interlock(library, i, num):
    m = 0
    n = num
    while m < num:
        if in_bisect(library, 0, len(library)-1, library[i][m::n]) == -1:
            return False
        else:
            m += 1
            n -+ 1
    return True
count = 0
library = []
fin = open('words.txt')
for line in fin:
    word = line.strip()
    library.append(word)
library.sort()
start = time.time()
# for i in range(len(library)-1): # 二词互锁
#     if interlock(library, i, 2):
#         print(library[i], library[i][::2], library[i][1::2])
#         count += 1
for i in range(len(library)-1): # 三词互锁
    if interlock(library, i, 3):
        print(library[i], library[i][::3], library[i][1::3], library[i][2::3])
        count += 1
print(count)
end = time.time()
print(end - start)
# 1254, 1.3558001518249512 # 二词互锁 xrspook解法
# 1254, 39.10080027580261  # 二词互锁 参考答案
# 991, 1.4504001140594482  # 三词互锁 xrspook解法
# 991, 43.366000175476074  # 三次互锁 参考答案