Cats：打字速度分析ok 1036 项通过

0. 这份作业在练什么

Cats 是一个真的能跑起来的打字测速网站的后端。官方把完整版部署在 cats.cs61a.org 上：你在浏览器里看到一段文字，照着敲，页面实时给你算速度、算正确率、自动纠正你刚刚敲错的单词，还能和另一个人同场竞速。这个项目要你亲手写出其中最核心的那部分逻辑。

但你打开 cats.py 会发现一件让人意外的事：没有一行代码和网络、和浏览器、和界面有关。你要填的十个空全都是纯函数——给定输入、返回输出、不碰外部状态（唯一的例外是 report_progress 要调用传进来的 upload，而那个 upload 也是参数，不是全局变量）。GUI、HTTP 服务器、多人对战的服务器通信全都写好了，它们只是在某个时刻调用你的函数。

这件事本身就是这个项目最想教的东西：一个复杂系统之所以能被写出来，是因为它被拆成了一堆各自能独立验证的小函数。「计算正确率」不需要知道文字是从哪来的；「找出最接近的单词」不需要知道用户是不是在打字。每个函数只做一件事，接口用参数说清楚，于是每个函数都能被一行 doctest 单独测。你在 lab 里练的那些「写一个函数」，到这里第一次被组装成一个系统。

四个阶段各练什么

做之前你至少要熟练三件事：(a) 函数是值，可以放进变量、传进参数、从函数里返回；(b) 列表的索引、切片、len、range；(c) 递归的写法——先写 base case，再写「把问题缩小一点然后信任递归」的那一步。第三件事在 Q6 和 Q7 里会被推到极限。

---------------------------------------------------------------------
Test summary
    1036 test cases passed! No cases failed.

1. Problem 1：pick

题目要什么

打字测试要先给用户一段文字。用户可能说「我想打关于猫的段落」，于是程序需要从一大堆候选段落里，按某个条件筛出合格的，再取其中第 k 个。pick 就干这件事。

三个参数：paragraphs 是候选段落组成的列表（每个元素是字符串）；select 是一个函数，喂给它一个段落，它返回 True 或 False；k 是一个非负整数。返回值是「所有让 select 返回 True 的段落中，第 k 个」。

>>> ps = ['hi', 'how are you', 'fine']
>>> s = lambda p: len(p) <= 4
>>> pick(ps, s, 0)
'hi'
>>> pick(ps, s, 1)
'fine'
>>> pick(ps, s, 2)
''

把这三行读懂，题目就基本清楚了。s 判断「长度不超过 4」，三个候选里 'hi'（长度 2）和 'fine'（长度 4）合格，'how are you'（长度 11）不合格。合格的段落按原顺序排成 ['hi', 'fine']，于是第 0 个是 'hi'，第 1 个是 'fine'。

关键的边界情况有两条，都要点明：

还有一条隐含信息，题面用了一句 Hint 特意点出来：不要去猜 select 内部怎么实现。你只知道它接受一个段落、返回布尔值。这不是「你不需要知道」，而是「你不能知道」——ok 测试会传各种奇怪的 lambda 进来，比如 lambda p: p == 'VQwSwNX'。你的代码必须对任何符合这个接口的函数都成立。

怎么想到的

第一反应大概是这样：「先把合格的全挑出来，然后取第 k 个。」这个想法完全正确，写出来是：

ok_ones = []
for p in paragraphs:
    if select(p):
        ok_ones.append(p)
return ok_ones[k]

然后你会立刻撞上第一个问题：ok_ones[k] 在 k 越界时会抛 IndexError: list index out of range，而题目要求返回 ''。补一句判断就能解决：

if k < len(ok_ones):
    return ok_ones[k]
return ''

这版是对的，能过所有测试。但停在这里就浪费了这道题。值得多问一句：我真的需要把所有合格段落都存下来吗？

不需要。我要的只是第 k 个。一旦找到它，后面的段落我一眼都不用看。列表只是被我用来「计数」的——我关心的其实是「到目前为止已经见过几个合格的」，这是一个整数，不是一个列表。

转换之后的逻辑是：维护一个 matches_so_far，初始为 0。遍历段落，遇到合格的就先问「我现在数到的这个，是不是第 k 个？」——注意先判断再自增。因为 matches_so_far 的语义是「在我之前已经有几个合格的」，所以当它等于 k 时，眼前这一个恰好就是下标为 k 的那个。

这里有个特别容易写反的地方。如果你先自增再判断：

if select(paragraph):
    matches_so_far += 1
    if matches_so_far == k:      # 错！
        return paragraph

那么第一个合格段落会让 matches_so_far 变成 1，于是 k = 1 时返回的是第一个合格段落——而正确答案是第二个。整个结果偏移一位，k = 0 则永远返回 ''。这就是「下标从 0 开始」这条边界的具体杀伤方式。

代码

def pick(paragraphs: list[str], select, k: int) -> str:
    # BEGIN PROBLEM 1
    # Walk through the paragraphs, counting only the ones that pass SELECT.
    matches_so_far = 0
    for paragraph in paragraphs:
        if select(paragraph):
            if matches_so_far == k:
                return paragraph
            matches_so_far += 1
    return ''  # fewer than k + 1 paragraphs qualified
    # END PROBLEM 1

逐行看：

• matches_so_far = 0：计数器的语义必须先定死——「在当前这个段落之前，已经遇到过几个合格段落」。想清楚这句话，后面的判断顺序就不会写反。
• for paragraph in paragraphs:：直接遍历元素，不用 range(len(paragraphs))。因为我从头到尾没用到「这是第几个段落」这个信息——我只关心「这是第几个合格段落」，而那由计数器负责。用不到下标就不要取下标，这能少一整类 off-by-one 错误。
• if select(paragraph):：把判断权完全交给参数。注意这里写的是 select(paragraph) 而不是 select(paragraph) == True——后者不但啰嗦，而且当 select 返回的是「真值但不是 True」的东西时还会出错。
• if matches_so_far == k: return paragraph：先判断，后自增。命中就立刻返回，函数就此结束，剩下的段落连 select 都不会被调用。
• matches_so_far += 1：没命中，说明这个合格段落的下标小于 k，把它记进账里继续往后找。
• return ''：这一行只有在 for 循环自然跑完时才会执行到——也就是所有段落都看过了，合格的数量却不足 k + 1 个。这个位置很重要：它必须在 for 外面。写在 for 里面（哪怕是 else 分支）会让第一个不合格段落就直接返回 ''。

for paragraph in paragraphs:
    if select(paragraph):
        ...
    return ''      # 缩进错了

# Error: expected
#     ''
# but got
#     None

验证

拿 doctest 的第二组调用 pick(ps, s, 1) 手动追一遍。此时 paragraphs = ['hi', 'how are you', 'fine']，select = lambda p: len(p) <= 4，k = 1。

第三次迭代直接 return，函数结束，最后那句 return '' 根本没被执行到。输出 'fine'，与 doctest 一致。

再追一遍 pick(ps, s, 2)。前两次迭代和上面完全一样（计数器走到 1）；第三次 'fine' 合格，判断 1 == 2 为假，于是不返回，计数器变成 2。循环没有更多元素了，自然结束，执行 return ''。输出 ''，与 doctest 一致。

注意这里 matches_so_far 最终值是 2，恰好等于合格段落的总数——这印证了计数器的语义定义是自洽的：循环结束时它就是「一共见过几个合格的」，而 k = 2 要求至少有 3 个才行。

i = 0
while True:
    source = pick(paragraphs, select, i)
    if not source:
        print("No more paragraphs about", topics, "are available.")
        return
    ...
    i += 1

2. Problem 2：about

题目要什么

Q1 的 pick 需要一个 select 函数，但 Q1 并没有教你怎么造一个。about 就是造 select 的工厂。

about(keywords) 接受一个关键词列表，返回一个函数。这个返回的函数接受一个段落，判断段落里是否出现了 keywords 中的任何一个词，是则 True，否则 False。

>>> about_dogs = about(['dog', 'dogs', 'pup', 'puppy'])
>>> pick(['Cute Dog!', 'That is a cat.', 'Nice pup!'], about_dogs, 0)
'Cute Dog!'
>>> pick(['Cute Dog!', 'That is a cat.', 'Nice pup.'], about_dogs, 1)
'Nice pup.'

注意第二行发生了什么：about(...) 的返回值被存进 about_dogs，然后整个塞进 pick 当参数。这就是 Q1 和 Q2 的接缝——两道题合起来才是一个完整的「按话题挑段落」功能。

题面用三条要求把「什么叫段落里出现了这个词」定义得很死：

ok 测试里有几组用例把这三条要求同时施加，值得逐个看清楚它们各自在考什么：

>>> dogs = about(['dogs', 'hounds'])
>>> dogs('A paragraph about cats.')
False
>>> dogs('Release the Hounds!')
True
>>> dogs('"DOGS" stands for Department Of Geophysical Science.')
True
>>> dogs('Do gs and ho unds don\'t count')
False
>>> dogs("AdogsParagraph")
False

• 'Release the Hounds!'：'Hounds!' 要先去掉 !、再小写成 'hounds'，两步都做才命中。
• '"DOGS" stands for ...'：'"DOGS"' 两侧都有引号，去标点后是 'DOGS'，小写成 'dogs'，命中。
• 'Do gs and ho unds don\'t count'：'Do'、'gs'、'ho'、'unds' 都是独立的词，没有一个等于 'dogs' 或 'hounds'。这条用例专门打「直接在整段字符串里搜子串」的写法——如果你写 'dogs' in paragraph，这句照样不会命中（因为中间有空格），但下一条就会出事。
• "AdogsParagraph"：整段只有一个词 'AdogsParagraph'，它包含子串 'dogs'，但它本身不等于 'dogs'。这一条是专门给 in 判子串的写法准备的坟墓。

还有一行不起眼但重要的代码，官方已经写在函数开头：

assert all([lower(x) == x for x in keywords]), "keywords should be lowercase."

它保证了 keywords 里的词一定已经是小写的。这条 assert 直接决定了你的设计：既然关键词侧已经小写，你就只需要把段落侧转成小写，不必两边都转。

怎么想到的

这道题的思维路径分两段，一段是「返回函数」这个结构，一段是「怎么比较词」这个细节。

第一段：为什么要返回函数

看到「实现 about，它返回一个函数」，第一反应通常是懵：为什么不直接写一个 contains(paragraph, keywords)？

答案在 pick 的签名里。pick(paragraphs, select, k) 规定了 select 只接受一个参数。你手里的 contains 要两个参数，塞不进去。要么改 pick 的签名（题目不许），要么想办法把 keywords 这个参数「提前固定住」，让剩下的函数只差一个 paragraph。

把这件事落到环境图上，才算真的懂了。执行 about_dogs = about(['dog', 'dogs', 'pup', 'puppy']) 之后：

Global 帧
    about       → func about(keywords)   [parent = Global]
    about_dogs  → func select(paragraph) [parent = f1]

f1: about 帧   [parent = Global]
    keywords → ['dog', 'dogs', 'pup', 'puppy']
    select   → func select(paragraph) [parent = f1]

重点在 about_dogs 指向的那个函数值上写着 parent = f1。about 已经返回了，但 f1 这个帧没有消失——因为还有一个函数值指着它。以后每次调用 about_dogs('Cute Dog!')，都会新建一个帧，它的父帧是 f1，于是在里面查 keywords 时能顺着父帧链找到那个列表。

调用 about_dogs('Cute Dog!') 时：

f2: select 帧  [parent = f1]        ← 注意 parent 不是 Global
    paragraph → 'Cute Dog!'

    查 paragraph → f2 里有，直接用
    查 keywords  → f2 里没有 → 去 parent f1 找 → 找到 ['dog', ...]

如果 select 的 parent 是 Global（比如你在全局定义了 select 再返回它），keywords 就查不到，会报 NameError: name 'keywords' is not defined。父帧是定义处所在的帧，不是调用处所在的帧——这是这门课反复强调的一条，Q2 是它第一次真正派上用场。

第二段：怎么比较词

结构定了，剩下的是「给定 paragraph 和 keywords，怎么判断」。最省事的写法是：

for word in keywords:
    if word in paragraph:      # 错：这是子串判断
        return True
return False

这版在 'A paragraph about dogs.' 上能过，在 "AdogsParagraph" 上直接翻车——'dogs' in "AdogsParagraph" 是 True，但答案应该是 False。而且它连大小写都处理不了：'dogs' in 'Release the DOGS' 是 False。

所以必须换个方向：不要在整段字符串里找关键词，而是先把段落切成一个个独立的词，再拿每个词去和关键词做「相等」比较。一旦从「子串包含」换成「元素相等」，「只匹配完整单词」这条要求就自动满足了——因为切出来的 'AdogsParagraph' 和 'dogs' 根本不相等。

那么切之前要做什么？段落里有标点和大写，得先归一化。utils.py 提供了三个现成的工具：

三个操作的顺序有讲究吗？lower 和 remove_punctuation 谁先谁后其实无所谓（转小写不产生标点，删标点不产生大写），但 split 必须放在最后——它返回的是列表，而前两个函数只吃字符串。写成 remove_punctuation(split(paragraph)) 会报 AttributeError: 'list' object has no attribute 'strip'。

代码

def about(keywords: list[str]):
    assert all([lower(x) == x for x in keywords]), "keywords should be lowercase."

    # BEGIN PROBLEM 2
    def select(paragraph):
        # Normalize the paragraph so comparisons ignore case and punctuation,
        # then compare whole words (not substrings) against the keywords.
        words = split(lower(remove_punctuation(paragraph)))
        for word in words:
            if word in keywords:
                return True
        return False

    return select
    # END PROBLEM 2

逐行看：

• def select(paragraph):：定义在 about 内部，因此它的 parent 帧就是 about 的帧，keywords 对它可见。参数只有一个，正好符合 pick 对 select 的要求。
• split(lower(remove_punctuation(paragraph)))：三层嵌套，从内往外执行。remove_punctuation 先把 'Cute Dog!' 变成 'Cute Dog'，lower 再变成 'cute dog'，split 最后切成 ['cute', 'dog']。注意这三步都没有修改 paragraph——字符串是不可变（immutable）的，每一步都返回新字符串。
• if word in keywords:：这里的 in 和刚才批判的 in 不是一回事。word in keywords 中 keywords 是列表，in 做的是「列表里有没有这个元素」的相等判断；而 word in paragraph 中 paragraph 是字符串，in 做的是子串判断。同一个运算符，因为右操作数类型不同而语义不同——这是 Python 里最容易被忽略的一处陷阱。
• return True：只要有一个词命中就够了，立刻返回，不必看完剩下的词。
• return False：循环跑完还没命中，说明一个都没有。位置同样必须在 for 外面。
• return select：返回函数对象本身，不加括号。写成 return select() 会立刻调用它，而调用需要 paragraph 参数，报 TypeError: select() missing 1 required positional argument: 'paragraph'。

验证

追一遍 ok 测试里那个最刁钻的用例：dogs = about(['dogs', 'hounds'])，然后 dogs('"DOGS" stands for Department Of Geophysical Science.')。

与 ok 期望的 True 一致。

再追一遍 dogs("AdogsParagraph")，看「只匹配完整单词」是怎么被自动满足的：

对比一下：如果第 4 步写的是 'dogs' in 'adogsparagraph'（字符串子串判断），结果会是 True，测试就挂了。「切成词再比相等」和「直接搜子串」的区别，全部体现在这一个用例上。

3. Problem 3：accuracy

题目要什么

用户照着 source 敲出了 entered，问：敲对了百分之几？

「敲对」的定义严格得有点反直觉：把两个字符串各自按空白切成词，然后逐位置比较——entered 的第 0 个词必须和 source 的第 0 个词完全相同，第 1 个对第 1 个，以此类推。「完全相同」包括大小写和标点。返回值是「对上的词数 ÷ entered 的词数 × 100」。

「一个词」的定义也要注意：任何被空白分隔的字符序列都算一个词，所以 "dog;" 是一个词，不是 "dog" 加一个分号。这和 Q2 完全相反——Q2 要去标点、要小写，Q3 什么都不做，原样比。

>>> accuracy('Cute Dog!', 'Cute Dog.')
50.0
>>> accuracy('A Cute Dog!', 'Cute Dog.')
0.0
>>> accuracy('cute Dog.', 'Cute Dog.')
50.0
>>> accuracy('Cute Dog. I say!', 'Cute Dog.')
50.0
>>> accuracy('Cute', 'Cute Dog.')
100.0
>>> accuracy('', 'Cute Dog.')
0.0
>>> accuracy('', '')
100.0

这七行几乎就是完整的规格说明书。逐条读：

题面还额外规定了一条 doctest 里没有的：entered 非空但 source 为空时返回 0.0。四条空串规则合起来是：

怎么想到的

核心是两个数字：分子「对上几个」和分母「除以几」。

分母先定：题目说的是「entered 中有多大比例的词是对的」，所以分母是 len(entered_words)。这一点从 accuracy('Cute', 'Cute Dog.') 返回 100.0 可以反推——如果分母是 source 的长度，答案会是 50.0。

分子稍微绕一点。最直接的想法是「遍历 entered_words，看每个词和 source_words 对应位置是否相同」：

correct = 0
for i in range(len(entered_words)):
    if entered_words[i] == source_words[i]:    # 越界风险
        correct += 1

这版在 accuracy('Cute Dog. I say!', 'Cute Dog.') 上会崩：i 走到 2 时，source_words[2] 越界，报 IndexError: list index out of range。

怎么修？想清楚多出来的那些词该算什么。题面说得很明确：「如果 entered 比 source 长，那些没有对应词的多余部分全都算错。」既然它们必然算错，那就根本不用去比——只需要比较两个列表都存在的那些位置，剩下的自动就是错的（因为它们不会给 correct 贡献，但会算进分母）。

这就是「打少了不算错」为什么能自动成立：accuracy('Cute', 'Cute Dog.') 中 min(1, 2) = 1，只比位置 0，对上了，correct = 1，分母也是 1，得 100.0。

剩下的就是空串。为什么必须单独处理？因为分母会变成 0。accuracy('', 'Cute Dog.') 里 entered_words 是 []，len 为 0，执行 correct / 0 * 100 会报 ZeroDivisionError: division by zero。所以在做除法之前必须先把空的情况拦下来。

「entered 非空但 source 空」这条要不要单独写？其实不写也对——min(n, 0) = 0，循环一次都不跑，correct = 0，返回 0 / n * 100 = 0.0，正好是要求的答案。但显式写出来更清楚地表达了意图，也让读代码的人一眼看到四种边界都被考虑过了。

代码

def accuracy(entered: str, source: str) -> float:
    entered_words = split(entered)
    source_words = split(source)
    # BEGIN PROBLEM 3
    if len(entered_words) == 0 and len(source_words) == 0:
        return 100.0
    if len(entered_words) == 0 or len(source_words) == 0:
        return 0.0
    # Only positions that exist in both lists can possibly match; any extra
    # word typed past the end of the source counts as incorrect.
    correct = 0
    for i in range(min(len(entered_words), len(source_words))):
        if entered_words[i] == source_words[i]:
            correct += 1
    return correct / len(entered_words) * 100
    # END PROBLEM 3

逐行看：

• entered_words = split(entered)、source_words = split(source)：这两行是官方给好的。用 split（即 str.split()）而不是 split(' ') 很关键——无参的 split 会按任意连续空白切分并丢掉空串，所以 ''.split() 得到 [] 而不是 ['']，'a b'.split() 得到 ['a', 'b'] 而不是 ['a', '', 'b']。如果它返回 ['']，空串检测就得改写成别的样子。
• if ... and ...: return 100.0：双空必须先判，而且必须用 and。顺序不能和下一行调换——如果先写 or 那行，双空的情况会先命中它返回 0.0，永远走不到 100.0 那行。
• if ... or ...: return 0.0：走到这里说明「不是双空」，那么 or 命中就意味着「恰好一个是空的」，无论哪一个空都返回 0.0。这两行的组合本质上是在做三分支判断，靠的是「先判更严格的条件」这个顺序。
• correct = 0：累加器，语义是「已确认相同的位置数」。
• for i in range(min(...)):：这里必须用下标遍历而不能用 for w in entered_words，因为比较是按位置进行的，我需要同时访问两个列表的同一个下标。这是「什么时候该用 range(len(...))」的典型答案：需要位置信息时才用。
• if entered_words[i] == source_words[i]:：直接用 == 比字符串，不做任何归一化。对比 Q2 的三层处理，这里的「什么都不做」正是题目要求的——大小写和标点都要严格对上。
• return correct / len(entered_words) * 100：/ 是真除法（true division），在 Python 3 里返回 float，所以 1 / 2 * 100 得到 50.0 而不是 50。doctest 期望的正是带小数点的 50.0，用 // 会得到 0，测试直接挂。

# Error: expected
#     50.0
# but got
#     0

验证

追第二个 doctest：accuracy('A Cute Dog!', 'Cute Dog.')，期望 0.0。这是最能说明「按位置对齐」有多严格的一个例子。

看清楚发生了什么：用户其实把 'Cute' 和 'Dog!' 都打出来了，只是在最前面多打了一个 'A'，结果整行的对齐全部错位，正确率从 50% 掉到 0%。这是逐位置比较的必然后果，也是真实打字测试的行为——少打一个空格就会导致后面全红。

再追一个反方向的：accuracy('Cute', 'Cute Dog.')，期望 100.0。

同一个 min，在两个方向上做的事完全不同：上一例里它保护了 source_words 不越界，这一例里它防止了把用户没打的词也算进来。一个表达式承担两个职责，这也是为什么值得花时间想清楚它的语义，而不是随手加个 try。

4. Problem 4：wpm

题目要什么

算打字速度，单位是「每分钟多少个词」（words per minute, WPM）。给定用户敲出的字符串 entered 和用掉的秒数 elapsed，返回速度。

但这里的「词」不是真的词。题面特意强调：WPM 里的一个「词」被定义为 5 个字符，空格也算字符。为什么这么定？因为如果按真实单词数算，打一段全是 "a I is" 的文字会比打 "antidisestablishmentarianism" 快得多，测出来的速度就没法横向比较了。用固定的 5 字符当一个「标准词」，测试结果才不被文章的词长分布带偏。

公式因此是两步：

分子是「折算成多少个标准词」，分母是「用了多少分钟」。

>>> wpm('hello friend hello buddy hello', 15)
24.0
>>> wpm('0123456789', 60)
2.0

题面自己给了一个更好懂的例子："I am glad!" 有 10 个字符（引号不算），折合 10 / 5 = 2 个词；如果花了 30 秒也就是半分钟，速度就是 2 / 0.5 = 4 WPM。

怎么想到的

这是全项目最简单的一题，但它值得认真对待的地方在于：怎么把一句自然语言描述的公式，翻译成不会出错的代码。

直接写成一行是很有诱惑力的：

return len(entered) / 5 / (elapsed / 60)

它是对的，但你得盯着它看两秒才能确认括号有没有问题。/ 是左结合的，a / 5 / b 等于 (a / 5) / b——恰好是想要的。可如果手一抖写成 len(entered) / 5 / elapsed / 60，就变成了 ((len / 5) / elapsed) / 60，答案小了 3600 倍，而且这个错误从代码外形上几乎看不出来。

另一个要想清楚的是：为什么不用 round？doctest 期望 24.0，而 30 / 5 / (15 / 60) 算出来正好是 24.0，不需要取整。但很多真实输入会算出 47.63157894736842 这种数——题目没要求取整，所以一律不要自作主张地 round。加了 round 反而会让 ok 里那些随机生成的用例挂掉，因为它们的期望值是完整精度的浮点数。

代码

def wpm(entered: str, elapsed: int) -> float:
    assert elapsed > 0, "Elapsed time must be positive"
    # BEGIN PROBLEM 4
    # A "word" is 5 characters, and elapsed is in seconds (60 seconds a minute).
    words_typed = len(entered) / 5
    minutes = elapsed / 60
    return words_typed / minutes
    # END PROBLEM 4

逐行看：

• assert elapsed > 0, ...：官方给好的。它的作用不是防御性编程，而是把前置条件写进代码——有了它，你在下面写除法时可以确信分母不为零。如果没有它，你就得自己想「elapsed 为 0 怎么办」，而题目其实没定义那种情况。看到 assert 就该意识到：这个分支不归我管。
• words_typed = len(entered) / 5：len 数的是字符（包括空格、标点、数字），这正是题目要的。用 / 而非 //：打了 7 个字符应该算 1.4 个词，不是 1 个词。整除会让短输入的速度被系统性低估。
• minutes = elapsed / 60：单位换算独立成行。同样用 /——打了 15 秒就是 0.25 分钟，用 // 会得到 0，下一行直接 ZeroDivisionError。
• return words_typed / minutes：两个已经是 float 的量相除，结果必然是 float，天然满足 doctest 里 24.0 那个小数点。

验证

追第一个 doctest：wpm('hello friend hello buddy hello', 15)，期望 24.0。

与 doctest 一致。顺手验证一下量纲：一刻钟打 6 个标准词，一分钟就是 4 倍即 24 个，合理。

再追第二个：wpm('0123456789', 60)，期望 2.0。字符串长度是 10（十个数字字符——这也顺便说明「字符」不限于字母）。words_typed = 10 / 5 = 2.0，minutes = 60 / 60 = 1.0，返回 2.0 / 1.0 = 2.0。

select = about(topics)              # Q2 造出筛选器
source = pick(paragraphs, select, i) # Q1 挑出第 i 段
start = datetime.now()
entered = input()                    # 用户敲字
elapsed = (datetime.now() - start).total_seconds()
print("Words per minute:", wpm(entered, elapsed))      # Q4
print("Accuracy:        ", accuracy(entered, source))  # Q3

5. Problem 5：autocorrect

题目要什么

Phase 2 开始做自动纠错：用户敲完一个词按空格，如果这个词不在词典里但很接近词典里的某个词，就替换成那个词。autocorrect 是这个功能的调度中心。

四个参数：entered_word（用户敲的词）、word_list（词典）、diff_function（一个衡量「两个词差多远」的函数）、limit（容忍上限）。规则三条：

还有一条平局规则，题面用 Important 标了出来：如果多个词的差异并列最小，返回在 word_list 里出现最早（下标最小）的那个。

diff function 的接口是固定的三参数：(entered_word, source_word, limit)，返回一个数。注意参数顺序——用户敲的词在前，词典里的词在后。这一点在 ok 测试里被专门检验过：

>>> length_ratio = lambda w1, w2, limit: len(w2) / len(w1)  # 一个不对称的 diff
>>> autocorrect("aaa", ["a"], length_ratio, 2)
'a'

如果你把参数顺序写反，length_ratio 会算成 len('aaa') / len('a') = 3.0，大于 limit = 2，于是返回 'aaa'；正确顺序算出来是 1/3，小于 2，返回 'a'。这个测试的存在本身就说明有很多人会写反。

再看几组 ok 用例，把三条规则各自的触发点看清楚：

>>> abs_diff = lambda w1, w2, limit: abs(len(w2) - len(w1))
>>> autocorrect("cul", ["culture", "cult", "cultivate"], abs_diff, 10)
'cult'
>>> autocorrect("cul", ["culture", "cult", "cultivate"], abs_diff, 0)
'cul'
>>> autocorrect("wor", ["worry", "car", "part"], abs_diff, 10)
'car'

• 第一组：三个候选与 'cul'（长 3）的长度差分别是 4、1、6，最小的是 'cult'，且 1 ≤ 10，返回 'cult'。
• 第二组：同样算出最小差是 1，但 limit = 0，1 > 0，触发第三条规则，返回原词 'cul'。同样的输入、同样的最优候选，只因为 limit 变了就完全不纠正。
• 第三组：'wor' 长 3，三个候选长 5、3、4，差为 2、0、1。最小的是 'car'（差 0）。注意 abs_diff 只看长度，它认为 'car' 比 'worry' 更像 'wor'——结果荒谬，但 autocorrect 照做不误。这正说明 autocorrect 不负责判断「像不像」，它只负责按 diff_function 的口径找最小值。

平局规则也有专门的用例：

>>> matching_diff = lambda w1, w2, limit: sum([w1[i] != w2[i] for i in range(min(len(w1), len(w2)))])
>>> autocorrect("bwe", ["awe", "bye"], matching_diff, 10)
'awe'
>>> autocorrect("bwe", ["bye", "awe"], matching_diff, 10)
'bye'

两个候选的差都是 1（'bwe' vs 'awe' 差第一个字符，vs 'bye' 差第二个字符）。同样的两个词，只是在列表里的顺序换了，答案就跟着换——这就是「平局取最靠前」。

怎么想到的

「在一堆候选里找出使某个函数值最小的那个」，这是一个模式，值得单独拎出来。手写版本长这样：

best_word = word_list[0]
best_diff = diff_function(entered_word, best_word, limit)
for w in word_list[1:]:
    d = diff_function(entered_word, w, limit)
    if d < best_diff:
        best_diff = d
        best_word = w

这版是对的，而且平局规则也自动满足了——因为条件写的是严格小于 <。当后面的词差异相等时，d < best_diff 为假，不更新，于是先来的词保住了位置。如果你手滑写成 <=，平局就变成「取最靠后」，那两个 "bwe" 用例会全挂。

但题面给了一条 Note，提示了更短的写法：min 带 key 参数。

用 min 就得提供一个 key。key 必须是单参数函数，而 diff_function 要三个参数。怎么办？和 Q2 遇到的问题一模一样：把不变的参数固定住。这次用 lambda：

diff_from_entered = lambda source_word: diff_function(entered_word, source_word, limit)

entered_word 和 limit 在整个 autocorrect 调用期间都不变，把它们「焊」进 lambda 里，剩下的就只有一个待填的槽 source_word。这和 about 返回 select 是同一个手法——只不过那次用的是 def，这次用的是 lambda。

剩下两条规则的顺序需要想一下。

第一条为什么必须放在最前面？假设 entered_word 就在词典里，你跳过第一条直接去算 min。理论上它和自己的差异应该是 0，肯定最小，结果也对。但这有两个问题：一是白算了一整轮 diff_function（词典有上万个词时这很贵）；二是没有任何规定说 diff_function(w, w, limit) 一定返回 0。ok 里就有这种 diff：

>>> ten_diff = lambda w1, w2, limit: 10  # 永远返回 10
>>> autocorrect("hwllo", ["butter", "hello", "potato"], ten_diff, 20)
'butter'

这个 diff 对所有词都返回 10，全体平局，于是返回下标最小的 'butter'。如果测的是 autocorrect("butter", [...], ten_diff, 20)，没有第一条规则的实现会返回 'butter'（碰巧对），但换成 autocorrect("hello", ["butter", "hello"], ten_diff, 20) 就会返回 'butter' 而不是 'hello'——把用户打对的词给改错了。ok 里确实有这类用例：autocorrect('bridgemaking', ['seeds', 'bridgemaking', ...], ..., 0) 期望 'bridgemaking'，而 limit = 0 会让第三条规则把所有纠正都否掉——只有第一条规则能救它。

第三条为什么必须放在最后？因为你得先知道「最小差异是多少」才能判断它是否超限。逻辑顺序是：先找出最优候选 → 再看它够不够好 → 不够好就放弃纠正。

代码

@memo
def autocorrect(entered_word: str, word_list: list[str], diff_function, limit: int) -> str:
    # BEGIN PROBLEM 5
    if entered_word in word_list:
        return entered_word

    # How far each candidate source word is from what the user typed.
    diff_from_entered = lambda source_word: diff_function(entered_word, source_word, limit)
    # min returns the *first* item achieving the smallest key, which is exactly
    # the tie-breaking rule we want (earliest index in word_list wins).
    closest_word = min(word_list, key=diff_from_entered)
    if diff_from_entered(closest_word) > limit:
        return entered_word  # even the best match is too far off to be a typo
    return closest_word
    # END PROBLEM 5

逐行看：

• @memo：这是选做题 Problem EC 要求加的装饰器（第 11 节详细讲）。做 Q5 时这一行还不存在，加了它 Q5 也照样通过——它只是把结果缓存起来，不改变返回值。
• if entered_word in word_list: return entered_word：第一条规则。word_list 是列表，这个 in 做的是元素相等判断（回顾 Q2 里对 in 两种语义的辨析）。
• diff_from_entered = lambda source_word: ...：把三参数函数包成单参数函数。写成具名变量而不是直接内联进 min(...)，是因为它下面还要再用一次——if diff_from_entered(closest_word) > limit。
• closest_word = min(word_list, key=diff_from_entered)：min 会对 word_list 的每个元素调用一次 key，然后返回让 key 最小的那个元素本身。不是返回最小的 diff 值——这一点极易搞混。
• if diff_from_entered(closest_word) > limit:：第三条规则。注意这里又调了一次 diff_function。理论上可以让 min 同时给出值和词（比如对 (diff, word) 元组取 min），但那样会破坏平局规则——元组比较在 diff 相等时会去比字符串的字典序，导致返回的不是下标最小的那个而是字母序最小的那个。多调一次函数，换来平局规则的正确，这笔交易是划算的。
• return closest_word：走到这里说明最小差异 ≤ limit，纠正成立。

>>> first_diff = lambda w1, w2, limit: 1 if w1[0] != w2[0] else 0
>>> autocorrect("inside", ["idea", "insider"], first_diff, 0.5)
'idea'

验证

追一遍 autocorrect("bwe", ["bye", "awe"], matching_diff, 10)，期望 'bye'。其中 matching_diff 数的是「前 min(len) 个位置上有几个字符不同」。

第 4 步是全题的题眼。把列表换成 ["awe", "bye"] 重跑一遍：第 3 步先算 'awe' 得 1，第 4 步算 'bye' 得 1，同样 1 < 1 为假不更新，于是最优是 'awe'。结果只由入场顺序决定，这就是 min 的严格小于比较在起作用。

再追一个触发第三条规则的：autocorrect("cul", ["culture", "cult", "cultivate"], abs_diff, 0)，期望 'cul'。

closest_word = 'cult'，再算一次它的 diff 得 1，判断 1 > 0 → 真，于是执行 return entered_word，返回 'cul'。与期望一致。

6. Problem 6：furry_fixes

题目要什么

Q5 造好了调度中心，但真正判断「两个词差多远」的活还没人干。furry_fixes 是第一个 diff function。

它的规则很朴素：把 entered 和 source 左对齐，逐位置比较，数出有几个位置的字符不同；如果两个词长度不等，把长度差也加进去。

>>> big_limit = 10
>>> furry_fixes("nice", "rice", big_limit)    # Substitute: n -> r
1
>>> furry_fixes("range", "rungs", big_limit)  # Substitute: a -> u, e -> s
2
>>> furry_fixes("pill", "pillage", big_limit) # Don't substitute anything, length difference of 3.
3
>>> furry_fixes("goodbye", "good", big_limit) # Don't substitute anything, length difference of 3.
3
>>> furry_fixes("roses", "arose", big_limit)  # Substitute: r -> a, o -> r, s -> o, e -> s, s -> e
5
>>> furry_fixes("rose", "hello", big_limit)   # Substitute: r->h, o->e, s->l, e->l, length difference of 1.
5

看第五行。"roses" 和 "arose" 在人眼里非常像——把 a 插到最前面再删掉最后的 s 就行了。但 furry_fixes 严格左对齐逐位比：r/a、o/r、s/o、e/s、s/e，五个位置全不同，答案是 5。ok 里还有更极端的：furry_fixes("hash", "ash", big_limit) 是 4，虽然这两个词只差一个开头的 h。

题目还有两条硬性约束：

为什么允许返回不精确的值？回看 Q5：autocorrect 只用 diff 值做两件事——找最小、和 limit 比大小。一旦某个候选的差异超了 limit，它就注定被淘汰，此时「超了 1」和「超了 100」对结果没有任何区别。继续算下去是纯浪费。题面用一组对照说明了这个要求有多严格：

>>> limit = 4
>>> furry_fixes("roses", "arose", limit) > limit
True
>>> furry_fixes("rosesabcdefghijklm", "arosenopqrstuvwxyz", limit) > limit
True

第二个调用的字符串长了 13 倍，但耗时必须差不多——因为在第 5 个字符处就已经超预算，后面 13 个字符根本不该被看。

怎么想到的

第一步：从循环翻译成递归

如果允许写循环，这题两行就完了：数出前 min(len) 个位置有几个不同，加上 abs 长度差。但题目不许。

递归的思路完全不同：不要想「怎么把所有位置都数一遍」，要想「怎么把问题变小一点点，然后把剩下的交给自己」。

对字符串来说，「变小一点点」的标准动作是切片：s[1:] 是去掉第一个字符后的字符串。于是问题变成：

这就是全部的递归结构。注意两边同时切掉第一个字符——因为 furry_fixes 只允许替换，位置 i 永远对着位置 i，不存在错位。（Q7 会打破这一点，那时切片方式才是真正的难点。）

第二步：base case 是什么

递归总要停。切到什么时候停？其中一个字符串变空的时候。此时剩下的另一个字符串有多长，就要付多少钱——这正是题目说的「长度差」。

怎么写？一个漂亮的技巧是 return len(entered) + len(source)。因为进入这个分支时至少有一个是空串，它的 len 是 0，所以这个和实际上就等于「非空那个的长度」。不用写 if entered == '': return len(source) else: return len(entered)，一个加法同时覆盖了两种情况，还顺带覆盖了「两个都空」（返回 0）。

第三步：limit 剪枝放在哪

这是这道题真正需要动脑的地方，题面的 Hint 也在提示它：「you will need more than one base case」。

先想清楚 limit 在递归中怎么传。每次发生替换（花掉 1 块钱），剩余预算就该减 1，所以递归调用传 limit - 1；字符相同时没花钱，预算不变，传 limit。

于是「超预算」的信号就是 limit 变成了负数。为什么是负数而不是 0？因为 limit = 0 意味着「还剩 0 块钱，但还没超支」——如果此时两个串正好都空了，答案是 0，完全合法（ok 里就有 furry_fixes("awesome", "awesome", 0) 期望 0）。只有花掉的钱严格超过预算，才算失败。

剪枝必须放在函数最开头，在做任何其他判断之前。这就是「stop making recursive calls」的字面执行：一进门就发现没钱了，立刻掉头，连 entered[0] 都不看。

代码

def furry_fixes(entered: str, source: str, limit: int) -> int:
    # BEGIN PROBLEM 6
    if limit < 0:
        # We have already spent more changes than allowed; stop recursing and
        # report a value that is guaranteed to exceed the original limit.
        return limit + 1
    elif entered == '' or source == '':
        # One word ran out: every leftover character is a length difference.
        return len(entered) + len(source)
    elif entered[0] == source[0]:
        # Characters line up, so no substitution is needed here.
        return furry_fixes(entered[1:], source[1:], limit)
    else:
        # Substitute this character and continue with one less of the budget.
        return 1 + furry_fixes(entered[1:], source[1:], limit - 1)
    # END PROBLEM 6

四个分支，顺序不能动。逐条说为什么：

• if limit < 0: return limit + 1——必须是第一个分支。如果把它放到第二位（先判空串），那么在 furry_fixes("", "abcdefgh", -1) 这种情况下会返回 8 而不是 0，虽然都大于原 limit，但它多做了一次 len；更严重的是，如果放到最后，剪枝就完全失效了——因为前面的分支已经把递归发出去了。
• elif entered == '' or source == '':——第二个 base case。用 or 而不是两个独立的 if，因为 len(entered) + len(source) 这个表达式对两种情况通吃。注意它也覆盖了「两个都是空串」，此时返回 0。
• elif entered[0] == source[0]:——能安全取下标 [0]，全靠上一个分支已经排除了空串。如果把空串检查删掉，这里会报 IndexError: string index out of range。分支顺序在这里承担了「守卫」职责。
• return furry_fixes(entered[1:], source[1:], limit)——注意没有 1 +，limit 也没减。字符相同是免费的。
• else: return 1 + furry_fixes(entered[1:], source[1:], limit - 1)——1 + 和 limit - 1 必须成对出现。它们是同一件事的两面：花了一块钱（结果加 1），预算少一块（limit 减 1）。只写一个就会出错：漏了 1 + 结果永远偏小；漏了 limit - 1 剪枝永不触发，性能测试挂掉。

验证：完整展开调用栈

追 furry_fixes("rose", "hello", 10)，期望 5。"rose" 长 4，"hello" 长 5，没有一个位置的字符相同，所以是「4 次替换 + 1 个长度差」。

furry_fixes("rose", "hello", 10)
  limit=10 不小于 0；两串都非空；'r' != 'h' → 走 else
  = 1 + furry_fixes("ose", "ello", 9)
        │
        │ limit=9 不小于 0；都非空；'o' != 'e' → else
        = 1 + furry_fixes("se", "llo", 8)
              │
              │ limit=8 不小于 0；都非空；'s' != 'l' → else
              = 1 + furry_fixes("e", "lo", 7)
                    │
                    │ limit=7 不小于 0；都非空；'e' != 'l' → else
                    = 1 + furry_fixes("", "o", 6)
                          │
                          │ limit=6 不小于 0；entered == '' → base case
                          = len("") + len("o") = 0 + 1 = 1

现在逐层回代：

furry_fixes("", "o", 6)      = 1
furry_fixes("e", "lo", 7)    = 1 + 1 = 2
furry_fixes("se", "llo", 8)  = 1 + 2 = 3
furry_fixes("ose", "ello", 9)= 1 + 3 = 4
furry_fixes("rose", "hello", 10) = 1 + 4 = 5   ← 答案

4 个 1 + 对应 4 次替换，最后的 1 来自「hello 比 rose 多出的那个 o」。和 doctest 注释里写的「Substitute: r->h, o->e, s->l, e->l, length difference of 1」完全对上。

再看一个字符相同的例子

追 furry_fixes("pill", "pillage", 10)，期望 3：

furry_fixes("pill", "pillage", 10)   'p'=='p' → 免费
= furry_fixes("ill", "illage", 10)   'i'=='i' → 免费
= furry_fixes("ll", "llage", 10)     'l'=='l' → 免费
= furry_fixes("l", "lage", 10)       'l'=='l' → 免费
= furry_fixes("", "age", 10)         entered == '' → base
= 0 + 3 = 3

注意这条链上一个 1 + 都没有，limit 也始终是 10——四次全是免费分支。最后 base case 一把算出长度差 3。这说明「长度差」在这个实现里不需要单独处理，它自然地落在 base case 里。

剪枝真的省了计算吗

追 furry_fixes("roses", "arose", 4)，题面要求它 > 4。

furry_fixes("roses", "arose", 4)    'r'!='a' → 1 + f("oses","rose",3)
  furry_fixes("oses", "rose", 3)    'o'!='r' → 1 + f("ses","ose",2)
    furry_fixes("ses", "ose", 2)    's'!='o' → 1 + f("es","se",1)
      furry_fixes("es", "se", 1)    'e'!='s' → 1 + f("s","e",0)
        furry_fixes("s", "e", 0)    limit=0 不小于 0；都非空；'s'!='e'
                                    → 1 + f("","",-1)
          furry_fixes("", "", -1)   limit < 0 → 立刻返回 -1 + 1 = 0
                                    ★ 一步都没往下走

回代：0 → 1 → 2 → 3 → 4 → 5。返回 5，确实 > 4。这里 \(L = 4\)、\(k = 5\)，按前面的推导应该得 \(L + 1 = 5\)——对上了。

现在把字符串加长到 furry_fixes("rosesabcdefghijklm", "arosenopqrstuvwxyz", 4)。前 5 个字符的比较过程与上面完全一样，limit 同样降到 -1，同样在第 6 层立刻返回。后面那 13 个字符一次都没被访问。这就是题面说的「两个调用耗时应该差不多」。

反过来，如果没有 limit < 0 这个 base case，第二个调用会一路递归 18 层才碰到空串。字符串再长十倍，代价就再涨十倍。而 autocorrect 要对词典里每一个词都调一次 diff——data/words.txt 有几万个词，这个差距是致命的。

# Error: Illegal use of 'for' in furry_fixes

7. Problem 7：minimum_mewtations

题目要什么

Q6 的 furry_fixes 只会替换，于是 "hash" 和 "ash" 这种只差一个开头字母的词被判成差 4。minimum_mewtations 要修好这件事：它计算编辑距离（edit distance）——把 entered 变成 source 最少需要几次编辑操作。

允许三种操作，每种算一次：

>>> big_limit = 10
>>> minimum_mewtations("cats", "scat", big_limit)       # cats -> scats -> scat
2
>>> minimum_mewtations("purng", "purring", big_limit)   # purng -> purrng -> purring
2
>>> minimum_mewtations("ckiteus", "kittens", big_limit) # ckiteus -> kiteus -> kitteus -> kittens
3

对比一下 Q6 的答案就能看出提升有多大：

最后一行最能说明问题：这是一个真实的拼写错误，Q6 的 autocorrect("speling", small_words_list, furry_fixes, 10) 会纠成 'peeling'（荒谬），Q7 则纠成 'spelling'（正确）。ok 里有一对并列的测试专门展示这个对比。

约束和 Q6 一样但更严：超 limit 要立刻停，有 call count 测试；另外题面加了一条 Important——不许用任何辅助函数，因为评分器会 trace 你的调用栈，看到额外的函数名就判失败。

怎么想到的

第一步：三个操作分别对应哪个切片

这是全项目最容易搞混的一步，值得慢慢来。

递归的框架和 Q6 一样：看 entered[0] 和 source[0]。如果不同，现在有三条路可走，每条路都花 1 次编辑，然后把「剩下的」交给递归。问题是：走完这一步之后，「剩下的」分别是什么？

三条路都走一遍，取代价最小的，再加上自己花的这 1 次：

return 1 + min(add, remove, substitute)

这就是所谓的树形递归（tree recursion）——一次调用分裂成三次，调用图不再是一条链而是一棵树。Q6 每层只有一个分支，Q7 有三个，代价从线性变成指数级。这也是为什么剪枝在这题变得性命攸关。

第二步：字符相同的时候，要不要也试三条路

如果 entered[0] == source[0]，最自然的做法是「免费划掉，继续」：mm(entered[1:], source[1:], limit)。但严格来说，此时也可以选择做一次插入或删除——万一那样更划算呢？

答案是不可能更划算。这是编辑距离的一条经典性质：如果两个串的首字符相同，那么存在一个最优编辑方案，其中这两个字符是互相匹配的。直觉是：假设某个最优方案没有让它们匹配，那它一定花了钱去动其中一个；把那笔钱省下来、改成让它们匹配，得到的方案不会更差。

第三步：两个剪枝 base case

第一个和 Q6 完全一样：limit < 0 时返回 limit + 1。前面推导过的「回代后恰好得到 \(L+1\)」在这里同样成立。

第二个是 Q7 独有的，也是最容易漏的：长度差超过 limit 就直接放弃。

为什么这条成立？想想三种操作对长度的影响：插入让长度 +1，删除让长度 −1，替换不改变长度。所以每一次编辑最多把长度差缩小 1。如果现在 entered 和 source 的长度差是 5，那么至少要 5 次编辑才可能让它们长度相等，遑论相同。若此时 limit 只有 2，这条路彻底没戏，立刻返回 limit + 1。

题面的 Common Mistakes 用一个具体例子逼问这一点：minimum_mewtations("maooo", "mao", 0)。长度差是 2，预算是 0——不需要做任何递归就能断定不可能。没有这条 base case 的实现会先匹配掉 m、a、o，再展开三条支路，白白多跑一堆调用。

第四步：base case 的顺序

三个提前返回的条件写成什么顺序？

代码

@memo_diff
def minimum_mewtations(entered: str, source: str, limit: int) -> int:
    if limit < 0:
        # Out of budget: any value above the original limit will do, and
        # returning right away keeps us from exploring a hopeless branch.
        return limit + 1
    elif entered == '' or source == '':
        # Only insertions (or only deletions) are left, one per leftover char.
        return len(entered) + len(source)
    elif abs(len(entered) - len(source)) > limit:
        # Fixing a length gap of N costs at least N edits, so this is hopeless.
        return limit + 1
    # Recursive cases go below here
    elif entered[0] == source[0]:
        # The first characters already agree, so no edit is needed here and
        # trying add/remove/substitute could never beat skipping both.
        return minimum_mewtations(entered[1:], source[1:], limit)
    else:
        add = minimum_mewtations(entered, source[1:], limit - 1)         # insert source[0]
        remove = minimum_mewtations(entered[1:], source, limit - 1)      # delete entered[0]
        substitute = minimum_mewtations(entered[1:], source[1:], limit - 1)
        return 1 + min(add, remove, substitute)


# Ignore the line below
minimum_mewtations = count(minimum_mewtations)

几处需要专门解释：

• @memo_diff：Problem EC 加的记忆化装饰器（第 11 节讲）。做 Q7 时没有它，代码照样对，只是慢很多。
• minimum_mewtations = count(minimum_mewtations)：这行是官方给好的，注释写着 Ignore the line below，但它其实值得看一眼。count 定义在 utils.py 里，它把函数包一层，每调用一次就给 counted.call_count 加 1。因为这行赋值改的是全局名字 minimum_mewtations，而函数体内的递归调用查的也是这个全局名字，所以每一次递归调用都会被计数。这正是评分器数调用次数的机制。
• 三个递归调用都写在 else 里，且都提前算好再取 min。这意味着三条支路无论如何都会被完整探索一遍——Python 不会因为 add 已经等于 0 就跳过 remove。这是这个实现的代价，也是 EC 那道题要靠记忆化来救的原因。
• 三个变量名 add / remove / substitute 不是装饰，它们是防止切片写错的最后一道防线。写下 add = mm(entered, source[1:], ...) 时，名字会逼你确认「插入到底动的是哪一边」。

验证：展开 minimum_mewtations("cats", "scat", 10)

期望 2，doctest 注释给的路径是 cats -> scats -> scat（先在前面插 s，再删掉末尾的 s）。看看递归是怎么找到它的。

mm("cats", "scat", 10)
  limit=10 ≥ 0 ✓
  两串都非空 ✓
  |4 - 4| = 0，不大于 10 ✓
  'c' != 's' → 展开三条支路（每条预算降到 9）

  add        = mm("cats", "cat",  9)   ← source 掉头（插入 's'）
  remove     = mm("ats",  "scat", 9)   ← entered 掉头（删掉 'c'）
  substitute = mm("ats",  "cat",  9)   ← 两边都掉头（把 'c' 换成 's'）

先把 add 这一支完整走完，因为它就是最优解所在：

mm("cats", "cat", 9)
  |4 - 3| = 1，不大于 9 ✓
  'c' == 'c' → 免费划掉，limit 保持 9
= mm("ats", "at", 9)
  'a' == 'a' → 免费
= mm("ts", "t", 9)
  't' == 't' → 免费
= mm("s", "", 9)
  source == '' → base case
= len("s") + len("") = 1 + 0 = 1

⇒ add = 1

这条链上没有任何一次三路分叉：插入 s 之后，"cats" 和 "cat" 前三个字符全对上，最后剩一个 "s" 要删掉——正是「scats -> scat」那一步。

另外两支的值（自行展开会分别再分叉出去，这里给结果）：

min(add, remove, substitute) = min(1, 3, 2) = 1
return 1 + 1 = 2          ← 与 doctest 一致

那个 1 + 就是「插入 s」这一次操作本身的代价，min 里的 1 是「插完之后还要删掉末尾的 s」。两步，正好对应注释里的 cats -> scats -> scat。

再看长度差剪枝怎么起作用

追题面 Common Mistakes 里那个例子：minimum_mewtations("maooo", "mao", 0)。

如果没有第三个 base case 会怎样？'m' == 'm' 免费划掉、'a' == 'a' 免费划掉、'o' == 'o' 免费划掉，到 mm("oo", "", 0) 才因为 source 空而返回 2。答案还是「大于 limit」，但白跑了三层。放在几万个词的词典上，这种浪费是以百万次调用计的。

调用次数实测

在 proj/cats/ 目录下跑：

>>> import cats
>>> cats.minimum_mewtations.call_count = 0
>>> cats.minimum_mewtations("rlogcul", "logical", 10)
3
>>> cats.minimum_mewtations.call_count
296

296 次调用（这个数字包含了 EC 记忆化生效后的效果），EC 测试的门槛是 <= 350，通过。把首字符相同时的贪心分支去掉、或者把长度差剪枝去掉，这个数字会立刻冲破门槛。

8. Problem 8：report_progress

题目要什么

Phase 3 做多人对战。你和对手各自跑一个 cats_gui.py，两边都往 CS 61A 的服务器上报进度，服务器再把对方的进度转发给你，于是屏幕上能看到两只猫在赛跑。report_progress 就是「上报进度」这一步。

每当用户敲完一个词，这个函数被调用一次。四个参数：entered（到目前为止敲出的词组成的列表）、source（原文的词列表）、user_id（你的编号）、upload（一个用来上报的函数）。

「进度」的定义是关键：从头开始连续敲对的词数，除以原文总词数。注意「连续」——一旦某个词错了，后面即使全对也不算。

report_progress(["Hello", "ths", "is"], ["Hello", "this", "is", "wrong"], ...)

题面给的这个例子进度是 0.25。用户敲了三个词，第一个 "Hello" 对，第二个 "ths" 错（原文是 "this"），于是从这里截断，第三个 "is" 虽然和原文对上了也不算。所以连续正确数是 1，原文有 4 个词，1/4 = 0.25。

函数要做两件事：

>>> print_progress = lambda d: print('ID:', d['id'], 'Progress:', d['progress'])
>>> entered = ['how', 'are', 'you']
>>> source = ['how', 'are', 'you', 'doing', 'today']
>>> report_progress(entered, source, 2, print_progress)
ID: 2 Progress: 0.6
0.6
>>> report_progress(['how', 'aree'], source, 3, print_progress)
ID: 3 Progress: 0.2
0.2

这个 doctest 的输出有两行，而且它们的性质完全不同：

题面还给了一条重要保证：entered 里的词数永远不会多于 source。这条保证让边界处理简单了不少。另外 ok 里有一批用例测 entered 为空的情形：

>>> report_progress([], ['smopple'], 22, print_progress)
ID: 22 Progress: 0.0
0.0

怎么想到的

「从头开始数连续对的个数」，这个动作用 for 循环写会有点别扭：

correct = 0
for i in range(len(entered)):
    if entered[i] == source[i]:
        correct += 1
    else:
        break        # 遇错即停

能用，但 break 的存在说明「循环条件」其实不只是「走完列表」——还有一个「一直对着」的条件。当一个 for 循环里出现 break，往往意味着 while 更贴切：把两个终止条件都写进循环条件里，读代码的人一眼就能看到什么时候会停。

循环变量 correct 同时扮演两个角色：它既是「已经确认对了几个」，又是「下一个要检查的下标」。这两件事能合一，正是因为「连续从头开始」这个条件——前 correct 个都对，那么下一个要看的就是下标 correct。想清楚这一点，循环体里只需要 correct += 1 一行。

为什么不用担心 source[correct] 越界？靠题面那条保证：len(entered) <= len(source)。既然 correct < len(entered)，那必然 correct < len(source)。这就是「读题面给的保证」的价值——它让你少写一个条件。

最后是 upload。它是参数，不是全局函数——这又是一次高阶函数的应用。真实运行时传进来的是往 CS 61A 服务器发 HTTP 请求的函数；测试时传进来的是 print_progress 这个只打印的 lambda。report_progress 完全不知道也不需要知道区别，于是它能在没有网络的环境里被 doctest 测试。这就是整个项目的设计哲学在 Phase 3 的体现。

代码

def report_progress(entered: list[str], source: list[str], user_id: int, upload) -> float:
    # BEGIN PROBLEM 8
    # Count how many words are correct before the first mistake.
    correct = 0
    while correct < len(entered) and entered[correct] == source[correct]:
        correct += 1
    progress = correct / len(source)
    upload({'id': user_id, 'progress': progress})
    return progress
    # END PROBLEM 8

逐行看：

• correct = 0：既是计数器又是游标。
• while correct < len(entered) and ...：先边界后内容，靠短路保护索引。循环在两种情况下退出——走完了 entered（全对），或者撞上第一个错词。退出时 correct 恰好是「连续正确的词数」，两种退出方式共用同一个语义。
• progress = correct / len(source)：分母是 source 的长度，不是 entered 的。这和 Q3 accuracy 恰好相反，值得停下来想一秒：accuracy 问的是「你敲的东西里对了多少」，progress 问的是「整篇文章你走了多远」。两个指标回答不同的问题，分母自然不同。
• upload({'id': user_id, 'progress': progress})：字典字面量直接内联。键名是字符串 'id' 和 'progress'，服务器和 GUI 都按这两个名字取值，写错一个字母就传不过去。
• return progress：不能漏。把它删掉 doctest 会少一行输出。

验证

追第二个 doctest：report_progress(['how', 'aree'], ['how', 'are', 'you', 'doing', 'today'], 3, print_progress)，期望打印 ID: 3 Progress: 0.2 并返回 0.2。

两行输出，顺序也对：先有 upload 的打印，后有返回值的回显。

再追一个「全对但没打完」的：report_progress(['how', 'are', 'you'], source, 2, print_progress)，期望 0.6。

correct=0: 0 < 3 真, 'how'=='how' 真   → correct=1
correct=1: 1 < 3 真, 'are'=='are' 真   → correct=2
correct=2: 2 < 3 真, 'you'=='you' 真   → correct=3
correct=3: 3 < 3 假 → 短路，右边 entered[3] 不求值 → 退出

progress = 3 / 5 = 0.6

最后一轮是短路的功劳。如果 and 两边写反，第四轮会先算 entered[3]——而 entered 只有 3 个元素，当场 IndexError。这个 bug 只在「全部敲对」时才触发，前几个测试都能过，非常隐蔽。

最后看空列表：report_progress([], ['smopple'], 22, print_progress)。correct = 0，循环条件左边 0 < 0 为假，一次都不进循环。progress = 0 / 1 = 0.0，打印 ID: 22 Progress: 0.0，返回 0.0。空列表不需要任何特殊处理——因为 while 的条件在循环开始之前就检查了，这是 while 相对 do-while 的好处。

# Error: expected
#     ID: 2 Progress: 0.6
#     0.6
# but got
#     ID: 2 Progress: 0.6

9. Problem 9：time_per_word

题目要什么

比赛结束后要出一份战报：每个玩家打每个词各花了多久。服务器记录的是时间戳——玩家在第几秒完成了第几个词。要把它转换成时长。

两个参数：words 是大家一起打的词列表；timestamps_per_player 是一个「列表的列表」，第 i 个内层列表记录第 i 个玩家的时间戳。返回一个字典 {'words': words, 'times': times}，其中 times[i][j] 是「玩家 i 打 words[j] 花的时间」。

题面给的例子是理解的关键：

timestamps_per_player = [[1, 3, 5], [2, 5, 6]]
times                 = [[2, 2], [3, 1]]

注意长度变了：内层列表从 3 个元素变成 2 个。为什么？因为题面这句话：「The first value of each list within timestamps_per_player represents the initial starting time for each player.」

看 ok 里的一个用例，把这个关系坐实：

>>> p = [[75, 81, 84, 90, 92], [19, 29, 35, 36, 38]]
>>> result = time_per_word(['collar', 'plush', 'blush', 'repute'], p)
>>> result['times']
[[6, 3, 6, 2], [10, 6, 1, 2]]

4 个词，每个玩家 5 个时间戳，输出 4 个时长。玩家 0：81-75=6、84-81=3、90-84=6、92-90=2。对上了。

还有一条隐含要求：'words' 键原样存回去，不做任何加工。这看起来多余，但它让返回值成为一个自洽的数据包——Q10 只需要拿到这一个字典就能干活，不必再要一份 words。这就是数据抽象：把相关的数据打包成一个整体，用键名而不是位置来访问。

怎么想到的

核心是「把累积量转成增量」——数学上就是一阶差分。这个模式在数据处理里到处都是：里程表读数转成每段路程、账户余额转成每笔流水、时间戳转成时长。

写法上有两层循环：外层遍历玩家，内层遍历这个玩家的时间戳。内层是关键，得想清楚下标怎么走。

第一反应可能是：

for i in range(len(timestamps)):
    durations.append(timestamps[i + 1] - timestamps[i])    # 越界

最后一轮 i 等于 len - 1，timestamps[i + 1] 越界，报 IndexError。修法有两种：

两种都对，产生的列表完全相同。本实现选了 B。

外层循环则可以直接遍历元素而不用下标：for timestamps in ts_by_player。因为构造 times 时我是按顺序 append 的，玩家的顺序自动保持，不需要显式的玩家编号。

代码

def time_per_word(words: list[str], timestamps_per_player: list[list[int]]) -> dict:
    ts_by_player = timestamps_per_player  # A shorter name (for convenience)
    # BEGIN PROBLEM 9
    times = []
    for timestamps in ts_by_player:
        # timestamps[0] is when this player started; every later entry is when
        # they finished a word, so consecutive differences are the durations.
        durations = []
        for i in range(1, len(timestamps)):
            durations.append(timestamps[i] - timestamps[i - 1])
        times.append(durations)
    # END PROBLEM 9
    return {'words': words, 'times': times}

逐行看：

• times = []：新建列表，不复用任何入参。这一点在 Q10 会变成硬性要求，这里先养成习惯。
• for timestamps in ts_by_player:：每次拿到一个玩家的时间戳列表。注意 timestamps 是对内层列表的引用（alias），不是拷贝——但因为下面只读不写，没有问题。
• durations = []：必须在外层循环内部。放到外面的话所有玩家的时长会堆进同一个列表，而且 times 里的每个元素都指向同一个列表对象——这是别名（aliasing）造成的经典事故，输出会变成 [[6,3,6,2,10,6,1,2], [6,3,6,2,10,6,1,2]] 这种诡异的东西。
• for i in range(1, len(timestamps)):：从 1 开始，跳过起始时刻。循环 len(timestamps) - 1 次，正好产出 len(words) 个时长。
• durations.append(timestamps[i] - timestamps[i - 1])：当前时刻减上一个时刻。题面保证时间戳「cumulative and always increasing」，所以结果必为正，不用取绝对值。
• times.append(durations)：把这个玩家的结果放进总表。放在内层循环外面——放里面会每算一个时长就 append 一次，得到一堆半成品。
• return {'words': words, 'times': times}：官方给好的。words 原样放回。

第 1 轮外层循环结束后：
    times ──→ [ ● ]
                │
                └──→ [6, 3, 6, 2]      ← 对象 A

第 2 轮：durations = [] 创建了一个全新对象 B
    times ──→ [ ● , ● ]
                │   │
                │   └──→ [10, 6, 1, 2]  ← 对象 B
                └──→ [6, 3, 6, 2]       ← 对象 A（没被动过）

    times ──→ [ ● , ● ]
                │   │
                └───┴──→ [6, 3, 6, 2, 10, 6, 1, 2]   ← 同一个对象！

验证

追 ok 的第一个用例：time_per_word(['This', 'is', 'fun'], [[1, 4, 6, 7], [0, 4, 6, 9]])，期望 times 是 [[3, 2, 1], [4, 2, 3]]。

读一读这个结果的含义：玩家 0 第 1 秒起步，打 'This' 用 3 秒、'is' 用 2 秒、'fun' 用 1 秒；玩家 1 从 0 秒起步，分别用 4、2、3 秒。虽然玩家 1 更早开始，但他打第一个词更慢——这正是为什么必须用差分而不能直接比时间戳。

10. Problem 10：fastest_words

题目要什么

拿到 Q9 产出的字典，统计每个词是谁打得最快，然后按玩家分组返回。

返回值是「列表的列表」，第 i 个内层列表装的是玩家 i 打得比所有其他人都快的那些词。平局时，下标小的玩家算赢。

>>> p0 = [5, 1, 3]
>>> p1 = [4, 1, 6]
>>> fastest_words({'words': ['Just', 'have', 'fun'], 'times': [p0, p1]})
[['have', 'fun'], ['Just']]
>>> p0  # input lists should not be mutated
[5, 1, 3]
>>> p1
[4, 1, 6]

逐词分析：

所以玩家 0 拿到 ['have', 'fun']，玩家 1 拿到 ['Just']。输出列表里词的顺序，必须和 words 里的顺序一致——'have' 在 'fun' 前面。

三条额外要求，每一条都对应着 ok 里的具体用例：

题面还指定要用官方给的 get_time(times, player_num, word_index) 取值，它内部有断言，越界时会给出可读的错误信息而不是干巴巴的 IndexError。

怎么想到的

第一步：先想清楚循环的方向

输出是「按玩家分组」，很自然会想「外层遍历玩家」：对每个玩家，看看哪些词是他最快的。但这样内层还要再遍历所有词、对每个词再和所有其他玩家比一遍——三层循环。

反过来想：「谁最快」这个问题是按词提出的。每个词有且只有一个赢家。所以外层应该遍历词，对每个词找出赢家，然后把这个词塞进赢家的篮子里。两层循环就够了。

fastest = [[] for _ in pl_idxs]

这里的列表推导式 [[] for _ in pl_idxs] 有个绝对不能替换的细节：不能写成 [[]] * len(pl_idxs)。

>>> a = [[]] * 3
>>> a[0].append('x')
>>> a
[['x'], ['x'], ['x']]

>>> b = [[] for _ in range(3)]
>>> b[0].append('x')
>>> b
[['x'], [], []]

第二步：找赢家

「在若干玩家中找出用时最小的那个的编号」——又是 min 加 key，而且这次要的正是「返回元素本身」这个性质：对玩家编号的序列取 min，key 是「这个玩家在这个词上的用时」，返回的就是赢家的编号。

winner = min(pl_idxs, key=lambda p: get_time(times, p, w))

平局规则又一次白送：min 用严格小于比较，编号小的玩家先入场、后来的等值者顶不掉他。Q5 用过一次，这里再用一次，同一条性质解决了两道题的平局问题。

lambda 里的 w 是外层循环变量。这没问题，因为 lambda 在本次迭代内就被 min 调用完了，用的就是当前的 w。（如果把这些 lambda 存起来留到循环结束后再调用，就会全部拿到最后一个 w——那是另一个经典陷阱，但这里不会发生。）

第三步：确认没碰入参

这个实现只做两件事：get_time（读 times）和 fastest[winner].append(...)（写自己新建的列表）。times 里的那些内层列表从头到尾没被写过。「不许修改入参」这条要求，是靠「压根不写它」来满足的，而不是靠某种保护措施。

代码

def fastest_words(words_and_times: dict) -> list[list[str]]:
    check_words_and_times(words_and_times)  # verify that the input is properly formed
    words, times = words_and_times['words'], words_and_times['times']
    pl_idxs = range(len(times))  # contains an *index* for each player
    w_idxs = range(len(words))    # contains an *index* for each word
    # BEGIN PROBLEM 10
    # Build a fresh list of lists so the caller's times are never mutated.
    fastest = [[] for _ in pl_idxs]
    for w in w_idxs:
        # min returns the first player achieving the smallest time, which
        # gives the lowest-index player the win on ties.
        winner = min(pl_idxs, key=lambda p: get_time(times, p, w))
        fastest[winner].append(words[w])
    return fastest
    # END PROBLEM 10

逐行看：

• 前四行是官方给的。check_words_and_times 会断言字典结构合法（每个玩家的时长数等于词数等等）；pl_idxs 和 w_idxs 是两个 range，分别是玩家编号和词编号。注意 len(times) 是玩家数（外层长度），len(words) 是词数——这两个别搞反。
• fastest = [[] for _ in pl_idxs]：_ 表示「这个变量我不用，只是要迭代这么多次」。pl_idxs 有几个元素就建几个空列表。
• for w in w_idxs:：按词遍历，这是整个设计的枢纽。用下标而不是 for word in words，因为 get_time 需要 word_index。
• winner = min(pl_idxs, key=lambda p: get_time(times, p, w))：对玩家编号取 min。key 把编号 p 映射成用时。返回的 winner 是编号（整数），不是用时。
• fastest[winner].append(words[w])：fastest[winner] 取出赢家的篮子（这是引用，不是拷贝），append 就地把词加进去。这是全函数唯一一处 mutation，改的是自己刚建的对象。因为按 w 递增的顺序 append，篮子里词的顺序自动和 words 一致。
• return fastest。

验证

追 doctest：fastest_words({'words': ['Just', 'have', 'fun'], 'times': [[5, 1, 3], [4, 1, 6]]})，期望 [['have', 'fun'], ['Just']]。

第 2 步是平局规则的现场：两个玩家用时都是 1，min 因为用严格小于而保留了先入场的 p=0。如果 min 内部用的是 <=，赢家会变成 1，输出成 [['fun'], ['Just', 'have']]，测试挂。

入参真的没被动过吗

用一张对象图确认。调用前：

Global 帧
    p0 ──→ [5, 1, 3]     ← 对象 A
    p1 ──→ [4, 1, 6]     ← 对象 B

传进去的字典：{'words': [...], 'times': [ ●, ● ]}
                                      │  │
                                      │  └──→ B
                                      └──→ A

函数体内 times 就指向那个 [A, B] 列表。get_time(times, p, w) 做的是 times[p][w]——纯读取。而 fastest 是全新建的：

fastest ──→ [ ●, ● ]
              │  │
              │  └──→ ['Just']         ← 新对象 D
              └──→ ['have', 'fun']     ← 新对象 C

A 和 B 自始至终没有出现在任何赋值语句的左边。

所以 doctest 里 >>> p0 仍然打印 [5, 1, 3]。关键在于：fastest[winner] 取出的是 C 或 D，永远不是 A 或 B。

空词表的情形

fastest_words({'words': [], 'times': [[], [], []]})，期望 [[], [], []]。

len(times) = 3，所以 pl_idxs = range(3)，fastest = [[], [], []]。len(words) = 0，所以 w_idxs = range(0)，for 循环一次都不执行。直接返回那三个空列表。「玩家数由 times 决定、词数由 words 决定」这个分工，让这个边界情况不需要任何特殊代码。

11. Problem EC（选做）：memo_diff 与装饰器

Phase 4 是官方标注的「Extra Challenge」，不计分。但它把这门课后半程最重要的两个概念——装饰器（decorator）和记忆化（memoization）——放在一个你已经完全熟悉的场景里，非常值得做。本仓库的 1036 个通过用例里包含了这一题。

先过概念题

tests/EC.py 的第一个测试套件是三道选择题（'type': 'concept'），跑 python3 ok -q EC -u 时会先问你这三道。它们不计分，但答不对就说明后面的代码你八成写不对。逐题讲清楚为什么是那个答案：

@memo_diff
def minimum_mewtations(entered, source, limit):
    ...

# 等价于

def minimum_mewtations(entered, source, limit):
    ...
minimum_mewtations = memo_diff(minimum_mewtations)

两道 What-Would-Python-Display

概念题之后是两个 doctest 形式的求值题。它们在考「@ 到底做了什么」，必须能在脑子里跑出来。

>>> def my_decorator(func):
...   def wrapper():
...       print("Say Hello")
...       func()
...       print("Say Goodbye")
...   return wrapper

>>> @my_decorator
... def say_hello():
...     print("Hello World")

>>> say_hello()
Say Hello
Hello World
Say Goodbye

装饰完成后的绑定：

Global
    my_decorator → func my_decorator(func)      [parent=Global]
    say_hello    → func wrapper()               [parent=f1]  ← 不再是原函数！

f1: my_decorator 帧  [parent=Global]
    func    → func say_hello()  ← 原来那个，只有这里还记得它
    wrapper → func wrapper()    [parent=f1]

>>> def magic_decorator(func):
...   def wrapper(x):
...     return func(x * 2)
...   return wrapper

>>> @magic_decorator
... def myfunc(x):
...   return x * 3

>>> print(myfunc(4))
24

题目要什么：memo_diff

官方已经给了通用的 memo：

def memo(f):
    """A general memoization decorator."""
    cache = {}

    def memoized(*args):
        immutable_args = deep_convert_to_tuple(args)
        if immutable_args not in cache:
            result = f(*immutable_args)
            cache[immutable_args] = result
            return result
        return cache[immutable_args]

    return memoized

思路很直接：用一个字典把「参数 → 结果」记下来，见过的参数直接查表。deep_convert_to_tuple 是必要的——字典的键必须可哈希（hashable），而列表不可哈希（因为它可变）。autocorrect 的第二个参数是 word_list，是个列表，不转成元组的话会报 TypeError: unhashable type: 'list'。

你要写的是 memo_diff：一个专门给 diff 函数用的记忆化装饰器。它和 memo 的区别全在 limit 上。

>>> minimum_mewtations("hello", "hasldfasdfsffsfasdf", 100)
17
>>> minimum_mewtations("hello", "hasldfasdfsffsfasdf", 2)
3

代码

def memo_diff(diff_function):
    """A memoization function."""
    cache = {}

    def memoized(entered, source, limit):
        # BEGIN PROBLEM EC
        key = (entered, source)
        if key in cache:
            cached_value, cached_limit = cache[key]
            # A result computed with a larger budget is at least as informative
            # as one computed with a smaller budget, so it is safe to reuse.
            if limit <= cached_limit:
                return cached_value
        value = diff_function(entered, source, limit)
        cache[key] = (value, limit)
        return value
        # END PROBLEM EC

    return memoized

逐行看：

• cache = {}：定义在 memo_diff 里、memoized 外。这个位置至关重要——它意味着 cache 属于 memo_diff 的那一帧，而 memoized 的 parent 正是那一帧，所以每次调用 memoized 都访问同一个字典。如果把它挪进 memoized 里面，每次调用都会新建一个空字典，缓存永远命中不了，性能测试全挂但答案还是对的（最难查的那类 bug）。
• key = (entered, source)：元组，不是列表。题面用 Important 特意强调了这一点。两个字符串都是不可变的，所以由它们组成的元组可哈希，能当字典的键。
• if key in cache:：字典的 in 查的是键，不是值。
• cached_value, cached_limit = cache[key]：元组解包（unpacking），一行拆出两个名字。这也是为什么存的时候要存成元组——一个键只能对一个值，把两样东西打包成元组是最省事的做法。
• if limit <= cached_limit: return cached_value：核心判断。用 <= 而不是 <——limit 完全相同当然可以直接复用，那正是最常见的命中情形。
• value = diff_function(entered, source, limit)：走到这里说明缓存没有、或者缓存的 limit 不够大。老老实实算一遍。注意调的是 diff_function（被装饰的原函数），不是 memoized 自己——写错就是无限递归。
• cache[key] = (value, limit)：覆盖式写入。因为能走到这一行，要么原来没记录，要么原来的 limit 更小、信息更少，新的一定不差。
• return value：三条路径（缓存命中、缓存失效重算、首次计算）每一条都有 return，一条都不能漏。

验证

tests/EC.py 里最能说明问题的是这一串（common_words 从 data/common_words.txt 读入）：

>>> minimum_mewtations.call_count = 0
>>> autocorrect("woll", common_words, minimum_mewtations, 4)
'well'
>>> minimum_mewtations.call_count <= 72000
True
>>> minimum_mewtations.call_count = 0
>>> autocorrect("woll", common_words, minimum_mewtations, 4)  # identical to the first call
'well'
>>> minimum_mewtations.call_count
0
>>> minimum_mewtations.call_count = 0
>>> autocorrect("woll", common_words, minimum_mewtations, 3)
'well'
>>> minimum_mewtations.call_count < 2500
True

三次调用，三种不同的缓存行为，正好把两个装饰器都验了：

第 3 步就是 limit <= cached_limit 这条规则的全部价值所在。如果你把键写成 (entered, source, limit)（也就是照搬 memo 的思路），第三次调用会因为 limit 不同而全部落空，call_count 重新回到几万，测试挂。「什么时候一个旧答案还能用」这个判断，是这道题真正要教的东西。

整份作业回顾

Cats 表面上是十一道零散的题，实际上它把这门课前半程的每一个核心概念都安排了一次「在真实场景里用一遍」的机会。抽掉题目本身，剩下的思维方法是这些：

三条贯穿全项目的主线

第一条：函数是值。这个项目里有五处把函数当数据用——pick 收 select、about 返回 select、autocorrect 收 diff_function 并现场造一个 lambda、report_progress 收 upload、memo_diff 收一个函数并返回一个函数。它们的共同目的都是解耦：让一个函数不必知道另一件事怎么做，只需要知道「有人会做」。这个能力直接换来了可测试性——report_progress 之所以能被 doctest 测，就是因为 upload 可以被换成一个只 print 的 lambda。

第二条：递归就是「把问题切小一点，然后信任自己」。Q6 和 Q7 的整个设计过程可以浓缩成三个问题：怎么让问题变小（切掉第一个字符）、什么时候不能再小了（某一边空了）、这一步花了多少钱（0 或 1）。Q7 比 Q6 难，难就难在「变小」有三种方式而不是一种。把每种编辑操作和对应的切片方式一一对上，是整个项目最需要在纸上画一遍的地方。

第三条：可变性要么是工具，要么是事故。Q9 和 Q10 一共设了三个陷阱：durations = [] 的位置、[[]] * n、以及对入参调用 sort()。三个都是同一件事的不同面孔——你以为有 N 个对象，实际只有 1 个；或者你以为在改自己的东西，实际在改别人的。判断方法始终一样：画出对象图，看谁指着谁。

动手检查自己是不是真的懂了