程序员的梦想是
抽象、递归，以及
快速打字。

介绍

重要提交事项： 为了获得完整学分：

• 在 7 月 14 日（星期二）之前提交完成的第1阶段和第2阶段，占1分。
• 在 7 月 17 日（星期五）.

请尽量按顺序完成题目并运行 ok 测试，因为后面的题目可能依赖前面题目的正确实现。

整个项目都可以与搭档合作完成。下面是 结对编程 and using VS Code 与远程协作的指南。

您可以在 7 月 16 日（星期四）.

在这个项目中，您将编写一个程序来测量打字速度。此外，您将实现打字自动纠错功能，该功能尝试在用户键入一个单词后纠正该单词的拼写。这个项目的灵感来源于 typeracer.

最终产品

你可以在 cats.cs61a.org。现在就可以试用；项目完成时，你将亲手实现其中相当大的一部分，包括多人模式！

下载起始文件

你可以下载 zip 压缩包。本项目包含多个文件， 但你只需要修改 cats.py。压缩包中包含以下文件：

• cats.py：打字测试逻辑。
• utils.py：用于文件和字符串操作的实用函数。
• ucb.py：CS 61A 项目的实用函数。
• data/sample_paragraphs.txt：用于打字练习的文本示例。这些文本示例来源于维基百科上关于各种主题的文章，是通过 抓取 获得的。
• data/common_words.txt：按频率排序的常见 英语单词.
• data/words.txt：更多按频率排序的 英语单词.
• data/final_diff_words.txt：更多英语单词！
• data/testcases.out：Final Diff 扩展（可选）的测试用例。
• cats_gui.py：基于 Web 的图形用户界面 (GUI) 服务器。
• gui_files：图形用户界面 (GUI) 相关文件目录。
• multiplayer：支持多人模式的相关文件目录。
• favicons：图标目录。
• images：图像目录。
• ok, cats.ok, tests：测试文件。
• score.py：可选的 Final Diff 扩展的一部分。

后勤

项目共 10 分：正确性占 9 分，在检查点前提交第 1、2 阶段占 1 分。

你需要提交以下文件：

• Provenance .zip file

完成本项目不需要修改或提交其他文件。提交项目时，请 把要求的文件提交到对应的 Gradescope 作业入口。

完成本项目时，不得使用人工智能工具提供帮助，也不得参考网上找到的答案。

对于需要你实现的函数，我们提供了一些初始代码。你可以选择直接使用，也可以删除后从头开始编写。你也可以根据需要添加新的函数定义。

但是，请勿修改上述未列出的任何其他函数或文件。否则，您的代码可能无法通过自动评分器的测试。 此外，请勿更改任何函数签名（包括名称、参数顺序或参数数量）。

在整个项目过程中，你应该经常测试代码的正确性。经常测试有助于快速定位问题，但也不要测试 过于频繁 ，要留出时间思考问题。

我们提供了一个名为 autograder called ok 的自动评分器，帮助你测试代码并记录进度。第一次运行时，系统会要求你 在浏览器中登录 Ok 账户。请按提示完成登录。此后每次运行 ok时，它都会把你的作业和进度备份到服务器。

的主要用途是 ok 测试你的实现。

如果您想以交互模式测试您的代码，可以运行

 python3 ok -q [question number] -i 

你还可以使用 Ok 的调试输出功能：在 print 语句前加上“DEBUG:”。例如，要查看变量 x的值，可以这样写：

 print(f"DEBUG: x is {x}") 

使用 Provenance Recorder 记录工作过程

本次作业需要使用 Provenance Recorder。这是一个 VS Code 扩展，会保存防篡改日志，记录 how 代码在工作过程中如何逐步形成。完成后，扩展会把作业文件和日志打包成一个密封的 .zip ；这个文件就是你的提交物，使作业能够按过程而不只是最终文件接受审核。

该扩展只会在课程授权的作业文件夹中运行。在其他文件夹中它完全不工作：不记录、不发网络请求，也不改变 VS Code 的行为。设置约需两分钟，只需做一次。

会记录什么？ 仅在作业文件夹内记录你的编辑、粘贴、保存、终端命令和编辑器焦点。在你上传密封文件前，所有内容都只保存在本机。 you 上传密封的 .zip。完整的逐项清单见 扩展的 Marketplace 页面.

开始之前

你需要：

• Visual Studio Code 1.94 或更高版本。 Check via Code → About Visual Studio Code (macOS) or Help → About （Windows/Linux）。若版本过旧，请从官网更新： 。
• 课程发放的作业文件夹 ，其中含有隐藏文件 provenance-manifest ；它用于授权记录。如果该文件缺失，记录无法启动，请重新下载起始文件。

1. 安装扩展

该扩展位于 Visual Studio Code Marketplace：

请在 VS Code 内安装：

1. 打开 VS Code。
2. Click the Extensions 图标（左侧栏的四个方块），或按 Command (⌘) + Shift (⇧) + X (macOS) / Ctrl + Shift + X （Windows/Linux）。
3. Search for Provenance Recorder.
4. 找到由 Aaryan Mehta（itsgeagle）, click Install发布的结果。最低需要 1.1.1 版，更高版本也可以。

一行命令安装： Press Command (⌘) + P / Ctrl + P, paste ext install itsgeagle.provenance-recorder, and press Enter.

无需登录或创建账户。扩展免费，记录会话期间不会发送网络请求。

2. 打开作业文件夹

Open the exact 课程发给你的作业文件夹本身，不要打开其父文件夹或子文件夹。

• File → Open Folder…，然后选择作业文件夹。

该文件夹必须包含 provenance-manifest 文件。VS Code 检测到它后，记录器会自动启用。

3. 确认正在记录

Look at the status bar 查看 VS Code 窗口底部的状态栏：

If you see Provenance: recording，就表示一切就绪。 这个指示器是唯一可见变化：没有弹窗、没有额外工具栏，也不会拖慢运行。照常编写、保存、运行和调试即可；IntelliSense、集成终端、快捷键和主题都不受影响。

If you don't 如果看不到，说明尚未记录，请参阅 故障排除 below.

A hidden .provenance/ 文件夹会出现在作业工作区中，日志保存在这里。不要删除、编辑或提交它；提交步骤会自动打包。

4. 正常完成作业

像平常一样做作业即可。日志会持续追加，因此你可以：

• 关闭 VS Code 后稍后继续；重新打开文件夹会启动一个与上次会话衔接的新会话，不会丢失内容。
• 可以使用集成终端、运行和调试代码，也可以安装其他扩展。

无需手动开始或停止；只要状态栏显示 Provenance: recording，记录就在正常工作。

第 1 阶段：打字

Reminder：整个项目中，我们只会修改该文件中的函数。 cats.py.

类型检查 开始项目前，请确保已启用类型检查！参见 here.

问题 1

实现 pick。该函数选择打字测试中用户要输入的段落，接收三个参数：

• paragraphs：候选段落（字符串）列表
• select：检查段落并返回布尔值的函数；满足条件时返回 True ，否则返回另一个布尔值 False otherwise
• k：非负整数，表示在所有符合条件的段落中要选取的索引

The pick 函数返回 k中第指定序号个 paragraphs 使得 select 函数返回真值的段落 True。若不存在这样的段落（因为 k 大于或等于符合条件的段落数），则 pick 返回空字符串。

提示：不必担心 select 函数的具体实现；只需假设它接收段落并返回布尔值。 True 或False. Reminder：索引从 0 开始。如果 k 为 0，就选取第一个 first 符合条件的段落。

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 01 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 01
Copy
✂️

问题 2

实现 about 函数，它接收名为 keywords的单词列表，并返回一个函数。返回的函数接收段落，检查其中是否包含列表里的任意单词。 keywords若包含，返回函数会返回 True ；若一个也没有，则返回另一个布尔值。 False otherwise.

Once about 实现后，可以把它返回的函数用作选择条件 select argument in pick，从而按照段落是否包含关键词列表中的词进行筛选。 about 这项功能会在后续开发打字测试时派上用场。

为确保比较准确，需要：

1. 忽略大小写（把大写和小写视为相同）。
2. 忽略段落中的标点。
3. 只检查与关键词列表中单词的精确匹配，而不是子串。例如， keywords 中的“dogs” paragraph 不应匹配关键词“dog”。 keywords.

提示: Use the split, lower和 remove_punctuation 函数位于 utils.py.

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 02 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 02
Copy
✂️

问题 3

实现 accuracy，它接收用户输入和参考段落 entered 段落和一个 source 段落。它返回 entered 中与 source。大小写和标点也必须相同。“对应”表示输入中的每个词 entered 必须与参考段落中相同位置的词匹配。 source换句话说，输入的第一个词 entered 必须匹配参考的第一个词 source，输入的第二个词 entered 必须匹配参考的第二个词 source，依此类推。

A word 在这里，“单词”指由空白与其他内容分隔的任意字符序列，因此像“dog;”这样的序列也视为一个词。

在实际打字测试中， entered 表示玩家已经输入的内容， source 表示他们要照着输入的段落。

• If entered 如果输入比参考更长 source，那么输入中没有对应参考词的多余单词 entered 应算作错误。 source are all incorrect.
• If entered 如果输入比参考更短 source ，但输入中的所有词到目前为止都与参考词 entered 对应 source ，准确率为 100.0。
• If entered 为空且 source 也为空时，准确率为 100.0。
• If entered 为空但 source 不为空时，准确率为 0.0。
• If entered 不为空但 source 为空时，准确率为 0.0。

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 03 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 03
Copy
✂️

问题 4

实现 wpm，它计算 每分钟字数（衡量打字速度），接收字符串 entered 以及耗时 elapsed time in seconds。尽管名称如此， 每分钟字数 并不按实际单词数计算，而是把每 5 个字符视为一个词，避免单词长度影响测试。计算公式为： 每分钟字数 输入字符总数（含空格）除以 5（平均词长），再除以以分钟计的耗时。 minutes.

例如，字符串 "I am glad!" 包含 10 个字符（不计引号），因此按 2 个词计算（10 / 5 = 2）。若用 30 秒（半分钟）输入，速度就是每分钟 4 词。

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 04 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 04
Copy
✂️

是时候测试您的打字速度了！ 您可以使用命令行来测试您在关于特定主题的段落上的打字速度。例如，以下命令将加载关于猫或小猫的段落。如果您好奇，请参阅 run_typing_test 函数的实现（但它是为您定义的）。

python3 cats.py -t cats kittens

也可以用下面的命令试用网页图形界面（GUI；某些系统可能需要使用 Ctrl+C 或 Cmd+C 退出GUI。

python3 cats_gui.py

第 2 阶段：自动更正

网页 GUI 中有“Enable Auto-Correct”选项，但目前尚未生效。我们来实现自动纠错：用户每次按空格时，若刚输入的词不在词典中，但与某个词足够接近，就用那个相似词替换输入。

问题 5

实现 autocorrect，它接收待纠正的单词、有效单词列表、差异函数和限制值。 entered_word, a word_list, a diff_function, and a limit其目标是寻找最合适的纠正结果。 autocorrect 的目标是返回 word_list 中与提供的 entered_word，相似程度由差异函数判断。 diff_function.

具体来说， autocorrect 执行以下操作：

• 如果 entered_word 存在于 word_list, autocorrect 则返回该单词。
• Otherwise, autocorrect 从有效单词列表中返回 word_list 与输入词差异最小的单词。 entered_word差异值由 diff_function.
• 但是，如果 entered_word 与 word_list 若最小差异大于 limit, then entered_word ，就返回原输入词。换句话说， limit 设定了仍允许纠正的最大拼写错误程度。

Assume that entered_word 和 word_list 的所有元素都是小写的，并且没有标点符号。

重要：如果 word_list 中的多个字符串与 entered_word, autocorrect 若多个词并列最小差异，应返回列表中出现最早（索引最小）的那个。 word_list.

diff 函数 (diff function) 接受三个参数。第一个是 entered_word，第二个是源单词（在本例中，是 word_list中的一个单词），第三个参数是 limit。diff 函数的输出是一个数字，表示两个字符串之间的差异量。

以下是一个 diff 函数的示例，该函数计算 1 + limit 和两个输入字符串长度之差的最小值：

>>> def length_diff(w1, w2, limit):
...     return min(limit + 1, abs(len(w2) - len(w1)))
>>> length_diff('mellow', 'cello', 10)
1
>>> length_diff('hippo', 'hippopotamus', 5)
6

注意：为简洁起见，一些解锁测试在定义 lambda 时使用三元表达式，也就是单行的条件表达式。 if statement.

例如，某个 Ok 测试这样定义差异函数： first_diff = lambda w1, w2, limit: 1 if w1[0] != w2[0] else 0。如果两个字符串的首字符不同，该 lambda 返回 1；否则返回 0。 w1 and w2

下面是实现时的一条提示： autocorrect:

注意：若想写成一行，可以尝试使用 max 或 min 与可选的 key 参数（接受单参数函数）一起使用。例如， max([-7, 2, -1], key=abs) 将返回 -7 ，因为 abs(-7) 若最小差异大于 abs(2) and abs(-1).

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 05 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 05
Copy
✂️

问题 6

实现 furry_fixes，它可以作为差异函数传给 diff_function 参数。 autocorrect该函数接收两个字符串，返回把起始词变为目标词至少需要修改的字符数。 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

重要：您不得在实现中使用 while, for或列表推导式。请使用递归。

如果必须修改的字符数大于限制值，可以提前停止递归。 limit, then furry_fixes 应返回任何大于 limit 的数字，并应尽量减少执行此操作所需的计算量。

为什么需要限制？从问题 5 可知， autocorrect 会拒绝任何与有效词差异超过限制的 source 输入词。 entered limit差异超过限制 1 还是 100 都没有区别，自动纠错都会拒绝。 limit 因此，一旦确定差异高于 limit，就应停止递归以节省时间，即使返回的具体差异值不完全准确。

以下两个对 furry_fixes 的调用应该花费大致相同的时间来评估：

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

自动评分器会统计函数调用次数，检查你是否在达到限制后停止递归。 limit 如果无法通过，请考虑加入与限制值有关的基本情况。 limit.

提示：本题需要不止一个基本情况。

>>> a = 'strap'
>>> a[0]
's'
>>> a[1:]
'trap'
>>> a[2:]
'rap'
>>> a[1:][1:]
'rap'

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 06 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 06
Copy
✂️

尝试在 GUI 中启用自动纠错。它能让你打得更快吗？纠正准确吗？

问题 7

实现 minimum_mewtations，这是一个可用于自动纠错的更高级差异函数。 autocorrect它返回把起始词变为目标词所需的 minimum 最少编辑操作次数。 entered 单词转换为 source 单词所需的最少编辑操作步骤。

有三种编辑操作步骤，以下是一些示例：

1. 向 entered.

   • Adding "k" to "itten" gives us "kitten".

2. 从 entered.

   • Removing "s" from "scat" gives us "cat".

3. 将 entered 中的一个字母替换为另一个字母。

   • 替换 "z" with "j" in "zaguar" gives us "jaguar".

每次编辑操作都会让两个词之间的差异增加 1。

>>> 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

我们已经在 cats.py中提供了一个代码模板。你可以修改或删除它，从头开始编写。

提示： 其中一次递归调用会类似 minimum_mewtations 。 furry_fixes不过，由于 minimum_mewtations 要考虑三种 specific 编辑（添加、删除、替换），因此还需额外的递归调用分别处理这些情况。

如果所需的编辑次数大于 limit, then minimum_mewtations 应返回 any number larger than limit (such as limit + 1），并在达到限制时停止递归以节省时间。

以下两个对 minimum_mewtations 的调用应该花费大致相同的时间来评估：

>>> limit = 2
>>> minimum_mewtations("ckiteus", "kittens", limit) > limit
True
>>> minimum_mewtations("ckiteusabcdefghijklm", "kittensnopqrstuvwxyz", limit) > limit
True

为确保达到限制后确实停止递归，请不要在实现中使用辅助函数。 limit 后执行的额外计算量，我们有一个自动评分器测试，它根据函数调用的次数来衡量您解决方案的性能。

重要: You should not minimum_mewtations否则自动评分器测试可能失败。

重要：准备测试实现时，记得删除下面这行代码：

assert False, 'Remove this line'

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 07 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 07
Copy
✂️

再次启用自动纠错并输入文字，纠正是否更准确了？

python3 cats_gui.py

（选做）扩展：Final Diff

你可以选择设计你自己的差异函数，称为 final_diff。这里有一些让自动更正更准确的建议：

• 考虑一下哪些添加或删除操作更有可能发生。例如，如果你不小心遗漏了一个字母，如果它连续出现两次，则更有可能。
• 如果两个相邻字母的位置颠倒了，算作一次修改，而不是两次。
• 尝试合并常见的拼写错误。
• 键盘上相邻的字母更容易互相误按。

还可以修改变量值，设置差异函数使用的限制。 FINAL_DIFF_LIMIT in cats.py.

您可以通过运行以下命令来检查 final_diff在给定常见拼写错误数据集上的成功率：

 python3 score.py

如果你不知道从哪里开始，请尝试将 furry_fixes and minimum_mewtations 的代码复制粘贴到 final_diff 并评分。观察它能纠正和不能纠正的错误，或许会带来灵感！

检查点提交

请检查是否已经完成第 1、2 阶段的所有题目：

python3 ok --score

运行 ok 命令时仍会看到部分测试被锁定，因为整个项目还没完成。只要正确完成此前所有题目，就能获得检查点满分。

Provenance：准备提交包

完成作业后：

1. 打开命令面板： Command(⌘) + Shift(⇧) + P (macOS) / Ctrl + Shift + P （Windows/Linux）。
2. Type Prepare Submission Bundle and select Provenance：准备提交包.

A sealed .zip 文件会保存在作业文件夹旁边，VS Code 会显示具体位置。提交包中同时包含作业文件和过程日志。

Submit

Upload only that .zip 上传到 Gradescope，除此之外不要上传其他内容。提交包已经包含作业文件，无需另行提交代码。

确认无误后，把 Provenance zip 文件上传到 Cats Checkpoint 作业入口 （Gradescope）。 务必在 7 月 14 日（星期二）的检查点截止时间前提交。若要回顾 Gradescope 提交流程，请参阅 Lab 00.

可以在 Gradescope 提交页面点击 Edit Group 并输入搭档邮箱来添加搭档。只需一名搭档提交。

第 3 阶段：多人游戏

和朋友联机比赛打字更有趣！接下来，你要实现多人游戏功能。这样，当你在电脑上运行 cats_gui.py 的时候，它就会连接到 cats.cs61a.org 的服务器，寻找其他玩家一起比赛。

要和朋友联机比赛，需要同时运行五个程序：

• 你的GUI，负责处理网页浏览器里的文字颜色和显示。
• 你的 cats_gui.py，是一个Web服务器，它使用你在 cats.py.
• 你的对手的 cats_gui.py.
• 你的对手的 GUI。
• CS 61A 多人游戏服务器，它将玩家匹配在一起并传递消息。

当您键入时，您的 GUI 会将您键入的内容上传到您的 cats_gui.py 服务器；它会计算你的进度并返回更新，同时把进度上传到 CS 61A 多人服务器，让对手的 GUI 也能显示你的进度。

与此同时，你的 GUI 会不断从服务器请求对手的进度更新，以保持最新状态。 cats_gui.py后者再从多人服务器取得信息。

每个玩家都有一个 id 号，服务器使用该号码来跟踪打字进度。

问题 8

实现 report_progress，每次用户完成键入一个单词时都会调用它。这个函数接收你输入的单词列表 entered 到目前为止的输入，以及参考文本中的单词列表 source 。用户的 user_id, and an upload 函数，用来把进度报告上传到多人游戏服务器。 entered 中的单词永远不会多于 source.

你的进度是这样计算的：在 source 定义为从开头连续正确输入的单词数除以参考单词总数。 source 例如，下面示例的进度为 0.25:

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

你的 report_progress 函数应当：

1. 调用上传函数，向多人服务器发送包含两个键的字典： upload 'id' and 'progress'. The 'id' 键应设为用户的 user_id, and the 'progress' 键应保存按上述定义计算的用户进度。
2. 返回计算出的用户进度。

提示： 下面的字典展示该函数可能接收的输入示例。 upload 函数的潜在输入示例。此字典表示 user_id 4 and progress 为 0.6 的玩家。

{'id': 4, 'progress': 0.6}

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 08 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 08
Copy
✂️

问题 9

实现 time_per_word，它接收两个参数：

1. words：玩家正在输入的单词列表。
2. timestamps_per_player：列表的列表；每个内部列表记录一名玩家完成每个单词时的时间戳。 words.

函数应返回具有以下结构的字典：

• 'words'：玩家正在输入的单词列表。
• 'times'：一个列表的列表 times ，保存每位玩家输入每个词所用的时间。具体来说，位置 times[i][j]处的值应表示玩家 i 输入索引为 words[j]的单词所花时间，即完成当前词与完成前一个词的时间戳之差。 words[j] words[j-1]. For words[0]对于第一个词，则是完成该词与开始输入的时间之差。 words[0]

参数中的时间戳 timestamps_per_player 是累计且始终递增的，而结果中的值是各词耗时。 times 列表中的数值代表 每个玩家连续时间戳之间的差值.

举例来说，如果 timestamps_per_player = [[1, 3, 5], [2, 5, 6]], then times would be [[2, 2], [3, 1]].

这是因为第一位玩家完成各词的时间戳为 1, 3和 5，第二位玩家的时间戳为 2, 5和 6。因此第一位玩家的时间差为 (3-1), (5-3) ，第二位玩家为 (5-2), (6-5) 。每个内部列表的第一个值表示该玩家的初始开始时间。 timestamps_per_player

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 09 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 09
Copy
✂️

问题 10

实现 fastest_words，它判断每个单词由哪位玩家输入得最快。所有玩家完成输入后调用该函数，它接收前一函数返回的字典。 time_per_word.

The fastest_words 函数返回单词列表的列表，每位玩家对应一个内部列表，其索引表示玩家编号。每个列表包含该玩家比所有其他玩家输入更快的词；若并列，则索引最小的玩家视为最快。

例如，考虑两位玩家输入 Just have fun的比赛。玩家 0 输入 'fun' 最快（3 秒），玩家 1 输入 'Just' 最快（4 秒），他们在单词 'have' （都用了 1 秒）。此时玩家 0 被视为该词输入最快者 'have' ，因为其索引更小。

>>> player_0 = [5, 1, 3]
>>> player_1 = [4, 1, 6]
>>> fastest_words({'words': ['Just', 'have', 'fun'], 'times': [player_0, player_1]}) # player 0 -> ['have', 'fun'], player 1 -> ['Just']
[['have', 'fun'], ['Just']]

使用已提供的辅助函数 get_time 从结果中取得某个单独耗时 times。若访问不存在的时间，它会给出有用的错误信息。

def get_time(times, player_num, word_index):
    """Return the time it took player_num to type the word at word_index,
    given a list of lists of times returned by time_per_word."""

重要：确保实现不会改变给定的玩家输入列表。对于上面的示例，调用函数后原输入应保持不变。 fastest_words on [player_0, player_1] should 不要 mutate player_0 或 player_1.

玩家不一定总是两人，因此请让函数能够处理任意数量的玩家。

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q 10 -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q 10
Copy
✂️

恭喜！现在可以与课程中的其他学生对战。请设置 enable_multiplayer to True （位于文件底部附近），然后快速输入吧！ cats.py

python3 cats_gui.py

项目提交

运行 ok 以检查所有问题，确保所有测试都已解锁并通过：

python3 ok

你还可以检查项目每个部分的得分：

python3 ok --score

Provenance：准备提交包

完成作业后：

1. 打开命令面板： Command(⌘) + Shift(⇧) + P (macOS) / Ctrl + Shift + P （Windows/Linux）。
2. Type Prepare Submission Bundle and select Provenance：准备提交包.

A sealed .zip 文件会保存在作业文件夹旁边，VS Code 会显示具体位置。提交包中同时包含作业文件和过程日志。

Submit

Upload only that .zip 上传到 Gradescope，除此之外不要上传其他内容。提交包已经包含作业文件，无需另行提交代码。

可以在 Gradescope 提交页面点击 Edit Group 并输入搭档邮箱来添加搭档。只需一名搭档提交。

第 4 阶段：效率（额外挑战）

（选做）额外挑战

注意：本题 optional and 不计分，面向希望进一步提升代码效率的同学。 只有完成项目所有其他题目后，才建议尝试本题。

答疑时间和项目活动中，课程团队会优先帮助必做题；只有答疑队列为空时才会为本题提供帮助。 queue 本题将实现记忆化装饰器，通过“记住”开销较大的运算结果来提升程序效率。

请先熟悉装饰器和记忆化；若需复习，可展开下面的内容。

>>> def do_twice(original_function):
...     def repeat(x):
...             original_function(x)
...             original_function(x)
...     return repeat

# Printing a value twice
>>> @do_twice
... def print_value(x):
...     print(x)
...
>>> print_value(5)
5
5
# Adding an item to a list twice
>>> lst = []
>>> @do_twice
... def add_to_list(item):
...     lst.append(item)
...
>>> add_to_list(5)
>>> lst
[5, 5]

我们将使用两个记忆化装饰器。 memo 是通用装饰器，用来记忆被装饰函数。如果 memo 遇到未见过的输入，就计算结果并存入缓存；如果 cache. If memo 再次收到见过的输入，就从缓存取出值 cache 并直接返回，不再计算。该装饰器的完整实现已经提供。 memo.

你的任务是实现 memo_diff. memo_diff 。它是高阶函数，接收一个差异函数 diff_function 并返回另一个名为 memoized 的差异函数；与其他差异函数一样，它接收起始词、目标词和限制值。 entered, source和 limit. memoized 应完成以下工作：

• When memoized sees a (entered, source首次遇到某个词对时，使用原差异函数计算差异 diff_function ，并把结果与限制值一起缓存到该词对下。 limit used as a (value, limit
• If memoized 再次遇到同一个词对时，entered, source若本次限制值小于或等于缓存时使用的限制值，就返回已记忆的差异； value 若提供的限制值 limit 更大，则重新计算、更新缓存并返回。

Important: 实现时请用元组而不是列表，把一对值作为缓存键。 不要 字典的键必须是 immutable （因此元组可以，列表不行）。如果想了解 memo_diff 为何不同于 memo 并这样实现，请展开下面的说明：

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

实现后，完成最后的接入步骤： memo_diff

1. Decorating autocorrect with memo.
2. Decorating minimum_mewtations with memo_diff.

Running autocorrect and minimum_mewtations 现在应该快得多！

注意：如果无法通过涉及记忆化的自动评分测试，很可能是问题 7 的实现没有使用 call_count minimum_mewtations 最紧凑的基本情况 ，仍需优化。问题 7 的测试较宽松，即使通过，也可能存在多余递归。本题更严格，因为最紧凑的基本情况对效率至关重要。

重要：请先自己尝试！只有在某个测试卡住较久时再看下面的常见错误，否则学习效果会打折扣。

注意：自动评分器需要一点时间运行，但不应超过 10 秒。

编写代码前，请先解锁测试，以确认自己正确理解了题意：

python3 ok -q EC -u
Copy
✂️

解锁完成后开始实现答案。你可以用以下命令检查实现是否正确：

python3 ok -q EC
Copy
✂️