作业要求

作业要求分为三部分：

1. 60 分的基础要求，这一部分的目的在于考察上课学习的内容，有少量需要自习的内容
2. 20 分的提高要求，这一部分难度较大，需要自己学习课上不会讲到的内容
3. 20 分的非功能要求，即代码规范和报告

本文提供两个版本：简洁版本和详细版本，可以使用下面的按钮进行切换：

切换版本

• 简洁版本去掉了提示，只保留作业要求
• 详细版本包括所有内容

建议在刚开始做大作业的时候，选择详细版本；在对内容比较熟悉后，切换到简洁版本，方便检查自己的实现是否满足要求。

当前版本：简洁版本

当前版本：详细版本

基础要求（60‘）

此部分功能按点给分，并且必须按顺序实现（也就是说，某个功能点得分的必要条件是它与之前的所有功能均正确实现）。除特殊说明外，最终结果以程序在助教环境中测试的结果为准。

作业的基础要求部分将使用 Rust 的测试框架进行自动化集成测试。为了便于测试，根据标准输出是否为交互式终端（项目模板中提供了 is_tty 用于判断），你的程序必须实现两种输出模式：

• 如果是，则使用较为友好和直观的输出（称为交互模式）。
• 如果不是，则严格遵守下面定义的输出格式（称为测试模式）。如果有任何不可恢复的错误（如参数格式错误、文件不存在等），程序必须以非正常返回值退出。

如果因为电脑性能较差导致了自动测试超时，可以适当地增大测例的超时限制（如增大到 10s）。

运行测试的方式详见项目模板。每个测试的名称类似 test_01_20_pts_basic_one_game，对应第一个基础要求，分值是 20。

关于测试的注意事项

• 通过测试点只代表在你的程序在测试模式下的表现是符合预期的，并不代表一定能获得该点的分数。
• 每个测试点均有运行时间限制，超时将会直接认为失败。
• 你的程序在 debug 与 release 模式下的测试结果通常应该相同。如果不同，则取较差的结果。

如无特别说明，下面所有涉及到 Wordle 游戏中字母的打印都必须全部大写。

• （20 分）程序启动时，从标准输入读取一个词作为答案，开始一局游戏（一局游戏最多 6 次猜测）。候选词与可用词内嵌在程序中（分别对应代码 src/builtin_words.rs 中的 FINAL 和 ACCEPTABLE）。从标准输入读取一行用户的猜测词：
  • 在每次猜测（获得可用词列表中的输入）后打印猜测结果和以及所有字母的状态：
    • 测试模式：程序启动后，不进行任何输出，等待用户的输入。在测试模式下可以认为输入的答案词符合要求。每次猜测后，如果输入符合要求，则打印一行，形如 SSSSS AAAAAAAAAAAAAAAAAAAAAAAAAA，前面五个字母是用户的猜测结果，后面 26 个字母是所有字母的状态（类似 Wordle 游戏中的输入键盘）。S 和 A 允许的取值包括 R（Red，数量过多的字母）、Y（Yellow，位置不正确的字母）、G（Green，正确的字母）、X（Unknown，未知状态的字母），语义与作业背景中描述的一致。如果读入的一行不符合要求，则打印 INVALID，重新猜测，不消耗猜测次数。在打印所有字母状态时，如果某个字母在猜测中有多个不同的状态，则选择最「好」的一种，即优先级为 G>Y>R>X。
    • 交互模式：每次猜测后向标准输出打印到本次为止的所有猜测结果，以及所有字母的状态（模拟 Wordle 网页的状态）。必须使用带颜色的输出，R 用红色，Y 用黄色，G 用绿色，X 不需要设置颜色。
  • 在游戏结束（用完六次猜测机会或者猜对）后打印猜测次数（包括猜对的最后一次），如果失败，则还需打印正确答案：
    • 测试模式：打印 CORRECT n（其中 n 为猜测次数）/ FAILED ZZZZZ（其中 ZZZZZ 为答案）
    • 游戏结束后正常退出程序

• （5 分）记上面从标准输入指定答案的模式为指定答案模式。在指定答案模式下，增加命令行参数 -w/--word 用于指定答案，如 -w build 或者 --word build 表示指定答案为 build，不再需要从标准输入读入答案；如果不指定，则依旧从标准输入读入答案。增加命令行参数 -r/--random 用于启动随机模式，在随机模式下，不再采用指定答案模式，而是从候选词库中（项目模版中给定）随机抽取问题。随机模式和指定答案模式只能二选一，默认情况下是指定答案模式。程序在测试模式下的输出格式不变。

  解析命令行参数的方法

  解析命令行参数有两种方法：

  1. 遍历 std::env::args() 返回的迭代器，逐个解析命令行参数，当遇到 -w/--word 参数的时候，记录状态，把遇到的下一个命令行参数保存下来；当遇到 -r/--random 参数的时候，启动随机模式。伪代码：

     meet_word_argument = 0
     random_mode = 0
     for each command line argument
         if meet_word_argument is 1
             word_argument = current_argument
             meet_word_argument = 0
         else if current_argument is -w or --word
             meet_word_argument = 1
         else if current_argument is -r or --random
             random_mode = 1
         end if
     end for
     if meet_word_argument is 1
         error! missing word argument
     end if
     

  2. 自学第三方库 clap 的使用：阅读 Clap Derive Tutorial 或者 Clap Builder Tutorial，两种写法二选一；推荐阅读 Command Line Applications in Rust

• （10 分）增加命令行参数 -D/--difficult 表示启动困难模式。在此模式下，新的猜测中所有已知位置正确（绿色，即 G）的字母不能改变位置，也必须用到所有存在但位置不正确（黄色，即 Y）的字母，但是允许在新的猜测中重复使用数量过多（红色，即 R）的字母，也允许存在但位置不正确（黄色，即 Y ）的字母再次出现在相同的错误位置。此选项不改变程序在测试模式下的输出格式。

• （5 分）如果没有使用 -w/--word 参数指定答案，则每局游戏结束后开始询问是否继续下一局。如果是随机模式，则在用户退出前，要求随机的答案不能与已经玩过的单词重复；如果是指定答案模式（且没有使用 -w/--word 通过命令行参数指定答案），每局重新从标准输入读入一个新的答案词。增加命令行参数 -t/--stats 表示在每局后，统计并输出截至目前的游戏成功率（成功局数 / 已玩局数）、平均尝试次数（仅计算成功的游戏，如果没有成功的游戏则为 0）、所有猜测中（按次数降序和字典序升序排序）最频繁使用的五个词和次数。

  • 测试模式：每局结束后，如果指定 -t/--stats 则额外进行以下操作：
    • 打印一行 X Y Z，分别为成功局数、失败局数（均为整数）和成功游戏的平均尝试次数（浮点数，截断到小数点后两位）；
    • 打印一行 W_1 i_1 ... W_5 i_5，分别是最频繁使用的五个词和次数；如果不足五个，则有多少输出多少；
    • 如果没有用 -w/--word 参数指定答案，则询问是否继续下一局：读入一行，如果为 Y 则继续，如果是 N 或者 EOF 标志（read_line 返回 Ok(0)）则退出；
  • 交互模式：以自定义方式显示信息

  多关键字排序

  多关键字排序（这里涉及到两个关键字，分别是猜测次数和猜测词）有两种实现方法：

  1. 使用稳定排序算法，先排序一个关键字，再排序另一个关键字。想想应该先排哪一个，后排哪一个？为什么需要稳定排序算法？
  2. 自定义一个比较函数，比较的时候，把两个关键字都考虑进来，然后一次性排好序

• （5 分）在随机模式中，增加命令行参数 -d/--day 用于指定开始时的局数（如 -d 5 表示跳过前四局，从第五局开始；默认值为 1，且不能超过答案词库的大小 A），-s/--seed 用于指定随机种子（类型是 u64，可选，默认为一个自选的确定值）。在候选词库不变的情况下，游戏应该被这两个参数唯一确定。随机模式下不允许使用 -w/--word 参数，指定答案模式下不允许使用 -d/--day 和 -s/--seed 参数，如果出现了冲突，则报告错误并以非正常返回值退出。这些选项不改变程序在测试模式下的输出格式。形式上来说，需要构造一个函数 \(w = \text{ans}[f(d,s)]\) 用来确定答案 \(w\) 在答案词库中的下标，满足：

  • 对于任何固定的 \(s\)，\(f(1,s)\dots f(A,s)\) 应该恰好是 \(\{1 \dots A\}\) 的一个无重复排列
  • 对于任意固定的 \(d\)，\(f\) 不允许是恒等变换（即不同的种子必须对应不同的排列）
  • 为了方便检查，规定在实现中，必须使用 rand crate（版本为 0.8.5）提供的 shuffle 方法，随机数引擎必须使用 rand::rngs::StdRng，并把 s 作为种子传入。具体来说，你需要先用 s 作为种子初始化一个 rand::rngs::StdRng（使用 seed_from_u64(u64)），再用这个 StdRng 去 shuffle 候选词库，最后以 day - 1 作为下标访问打乱后的数组。

  数组打乱的方法

  为了保证多次随机出来的数不重复，把所有可能的值放在一个数组中，随机打乱以后，按顺序取出来，这样做既保证了随机性，又保证了不重复性。

  shuffle 函数实现了 Fisher-Yates 算法，这是一个很经典的数组打乱算法，值得学习。

• （5 分）增加命令行参数 -f/--final-set 以及 -a/--acceptable-set 用于指定候选词库和可用词库文件（如 -f final.txt -a acceptable.txt）。如果不指定，则使用内置的词库。文件的格式均为按行分割的单词列表（不区分大小写）。加载时需要检查是否符合格式要求、是否存在重复，并且候选词库必须严格是可用词库的子集。如果在指定答案模式中，则也要检查用户给定的答案是否在候选词库中。在读入词库后，需要将其全部转为大写，并按字典序排序。

  提示

  读取文件内容，可以用 Rust 标准库中的函数，如：

  • std::fs::File::open：打开一个文件
  • std::io::Read::read_to_string：从已经打开的文件里，读取整个文件的内容到 String
  • std::fs::read：跳过打开文件的步骤，直接从文件读取数据到 Vec<u8>
  • std::fs::read_to_string：跳过打开文件的步骤，直接从文件读取数据为 String

  检查是否存在重复的元素，以及判断两个集合之间是否为子集的关系，可以用 Rust 中对应集合的数据结构来实现。

• （5 分）增加命令行参数 -S/--state 用于保存和加载随机模式的游戏状态（如 -S state.json），格式为如下的 JSON 文件：

{
  "total_rounds": 1, // 已经玩过的总游戏局数
  "games": [ // 所有对局，长度应该恰好为 total_rounds
    {
      "answer": "PROXY", // 此局答案
      "guesses": ["CRANE", "PROUD", "PROXY"] // 此局猜测情况
    }
  ]
}

提示

向文件写入内容，可以用 Rust 标准库中的函数，如：

• std::fs::File::create：以写模式打开或新建一个文件
• std::io::Write::write：向已经打开的文件写入数据（&[u8]）
• std::fs::write：跳过打开文件的步骤，直接向文件写入数据

JSON 是一种数据交换格式，支持数组、字典（Map）、字符串、数字、bool 和 null。具体的表达方式如下：

1. 数组：以 [ 开头，接着是以 , 分隔的数组元素，最后以 ] 结尾。元素可以是任意类型。
2. 字典（Map）：以 { 开头，接着是若干个键（Key）值（Value）对最后以 } 结尾。键值对之间用 , 分隔，键和值之间用 : 分隔。键必须是字符串，值可以是任意类型。
3. 字符串：用两个 " 括起来的字符串，支持转义字符。
4. 数字：十进制数，支持小数。
5. bool：true 或者 false。
6. null

读写 JSON 有两种方法：

1. 自行解析 JSON，例如：找到第一个 { 字符，然后找到前两次出现的 " 字符，提取出双引号之间的字符串，判断它是 total_rounds 还是 games；如果是 total_rounds，找到 : 和 , 的位置，提取出中间的数字；如果是 games，那么找到 [，再找到 {，重复类似前面的过程，分别解析出 answer 和 guesses 的内容。最后把数据放在一个自定义的 struct 中。注意字典里面键（Key）的顺序是不固定的，不保证 total_round 一定出现在 games 之前。
2. 使用 serde_json 或 json 库来操作 JSON。推荐阅读 How to Work With JSON in Rust 和 Rust - Serde Json By Example。

在游戏启动时，如果状态文件存在，则加载此前的状态，不存在则忽略。加载时需要检验文件格式的合法性（但无需检验内容，即无需考虑这些词是不是在本次的词库中；如果一些键值不存在，也视为合法），并在不合法时报告错误并以非正常返回值退出。

提示

这样设计，一方面防止错误地加载了来自其他软件的 JSON，如果出现了不认识的键值，那大概率说明加载错了 JSON。另一方面，考虑到兼容性，为了读取旧版本程序生成的状态文件，此时状态文件可能会缺少一些新版本才有的键值，所以缺少键值是允许的。

每次结束一局游戏后，需要将当前状态写入文件中。注意在上面打印的游戏统计中，需要包含此前所有的游戏，而非仅本次启动后的；每次启动均视为新的一局，即 total_rounds 不影响 day 的效果，仅用于计算统计数据。

提示

这其实就是游戏的实时存档功能。你当然不希望在玩了很久游戏以后，忽然电脑死机，存档都丢失了吧。当然了，Wordle 比较简单，不需要恢复没有完成的游戏，只是需要记录历史成绩，所以实现起来更加简单。

如果没有指定 -S/--state 参数，则既不加载游戏状态，也不保存。

提示

在自动测试中，-S/--state 选项在 common.rs 中添加并传递给 Wordle 程序，因此在对应的 .args 文件中不出现 -S/--state 选项是正常的。如果要手动测试，请参考快速入门文档中相关内容。

• （5 分）增加命令行参数 -c/--config 用于指定启动配置文件（如 -c config.json），格式为如下的 JSON 文件：

{
  "random": true,
  "difficult": false,
  "stats": true,
  "day": 5,
  "seed": 20220123,
  "final_set": "fin.txt",
  "acceptable_set": "acc.txt",
  "state": "state.json",
  "word": "cargo"
}

其中每个字段的含义和上面的命令行选项相同，并且所有字段都是可选的。如果同时在配置文件和命令行参数中指定了同一个参数（例如配置文件设置 "seed": 20220123 同时命令行参数设置了 --seed 20220234），则以后者为准，相当于配置文件设定了默认的命令行参数。

提示

为了让命令行参数优先级更高，即命令行参数可以覆盖配置文件的设置，建议把配置文件和命令行参数分别解析成自定义的 struct，然后合并两个 struct 得到最终的结果，这样可以简化实现。

也可以用现成的第三方库来做这件事情：config。

提高要求（20’）

此部分功能没有具体的要求，助教将视完成情况酌情给分。其中有些项目存在依赖关系，无法单独完成。所有项目得到的分数综合不超过 20 分。标记有“⚠️”的功能是助教认为复杂度较高的功能，请谨慎上手。

任何提高要求的实现不应该影响已有的自动化测试。你可以编写额外的可执行文件（在 Cargo.toml 中添加 [[bin]] 段即可，并注意尽量用 crate 的形式复用已有代码），或者通过额外的编译选项（不同的 feature）或命令行参数来区分，也可以使用更高级的 Cargo workspace 等方式组织项目。此部分具体要求可见项目模板的说明。

提示

实现提高要求时，经常会发现需要重构之前的代码：把一些常用的代码抽象成函数，方便复用，同时用于不同的场景。如果已经确定好要做哪些提高要求，可以在实现基础要求时提前想好要做哪些接口。当然了，也可以等写完了基础要求再进行重构，毕竟重构本身也是很重要的提高代码能力的一个方法。只是需要花更多时间。

• 设计用户界面（不能替代上面的交互模式）：

  • （10 分）基于 TUI 绘制用户界面（需要在 Linux 下正常工作），至少应有输入区、键盘区

    提示

    如果对 TUI 是什么没有概念，可以尝试用一下 htop（查看 CPU 和内存占用，正在运行的进程）、s-tui（查看 CPU 占用，温度和风扇转速）和 tig（TUI 版的 Git 客户端）等工具。

  • （15 分 ⚠️）基于 GUI 绘制用户界面（可使用任意平台的任意 GUI 框架，推荐使用 Rust 原生框架），效果类似 Wordle 原版体验

  • （20 分 ⚠️⚠️）将程序编译到 WebAssembly（可使用 Rust Web 前端框架和 rustwasm），基于 Web 绘制用户界面（DOM / Canvas 均可），非必要不使用 JavaScript

• Wordle 求解（此部分均可直接通过标准输入输出交互，不依赖于 UI，候选词列表对于求解器来说是未知的，只能使用可用词列表）：

  • （5 分）基于现有的猜测结果给出提示，即根据用户提供的所有的已用过的字母和状态（或者游戏的当前状态），从可用词列表（ACCEPTABLE）中筛选出所有可能的答案
  • （5 分）在这些剩余可用词的基础上，给出若干个推荐词，只考虑单步最优，给每个词打分，选出最高的几个，例如按照 3Blue1Brown 视频中的算法，计算信息熵并排序；也可以自己设计合理的算法

  • （5 分）设计一个考虑全局最优的算法（例如猜测次数最少），要求这个算法是确定性的。然后对整个候选词库测试你算法的平均猜测次数，即对于所有可能的候选词，按照设计的算法进行模拟和统计。注意这不代表算法可以使用候选词库，只是在评估算法效果的时候，用候选词库评估。最后给出若干个全局最优的起始猜测词。由于可能耗时较长，验收时可不当面运行，给出结果即可

    提示

    可使用 rayon 等库进行数据并行加速。合理的优化后，可以做到几分钟内完成计算。

  • （5 分）实现类似 WORDLESolver 的交互解决 Wordle 功能。具体地，玩家可以同时开两个程序，一个是正在游玩的 Wordle 程序，另一个是交互式解决 Wordle 的程序。当玩家在游玩时遇到困难，可以求助于交互式解决 Wordle 的程序，即把自己的猜测历史，以及每次猜测的结果输入给交互式解决 Wordle 的程序，然后它会给出推荐的猜测词。推荐猜测词的算法要使用前面自己设计的全局最优算法。

• 其他任何未提及的功能：请先与助教确认可行性，并评估应得分数，如未经确认直接实现则不得分

非功能要求（20‘）

• （10 分）代码规范
  • （5 分）正确使用 Git 管理代码、使用 Cargo 组织项目（尤其是在实现提高功能时需要尽量复用已有代码）
  • （5 分）代码风格良好，有合理的注释
• （10 分）提交 PDF 格式的大作业报告到网络学堂，包含：
  • 简单的程序结构和说明（不必过长，尤其不要逐句/函数解释代码）
  • 游戏主要功能说明和截图（不必面面俱到）
  • 提高要求的实现方式（如有，尤其是如果使用了自行设计的算法）
  • 完成此作业感想（可选）
• HONOR-CODE.md: 以 Markdown 格式记录你参考网上的文章或者代码、与同学的交流情况
  • 参考 抄袭与查重

提示

下面列举了一些推荐使用的第三方 crate，你也可以自行寻找。

• 终端打印与 TUI：console, colored, terminal, crossterm, termion, tui, crosscurses
• 命令行参数解析：clap
• 随机相关：rand
• JSON 序列化与反序列化：serde_json, json
• GUI：egui, rust-qt, iced
• Web 框架：yew, seed

这次大作业不希望对你的思路做过多限制，因此这里就不提供更多第三方库的帮助了。如果你在使用第三方库过程中遇到了问题，例如需要使用还没有学到的 Rust 语言特性，可以尝试预习。在难以解决时利用各种渠道寻求帮助。

在完成大作业过程中，可以经常回顾快速入门文档中的相关内容。

下面是一些可以参考的 Wordle 实现：

• https://medium.com/pragmatic-programmers/rustle-5c15d1c153a1
• https://github.com/conradludgate/wordle

参考代码时不要忘记在 HONOR CODE 中注明，参考 抄袭与查重。

注意事项

• Wordle 虽好玩，不要沉迷哦。
• 本作业将严格进行查重，任何抄袭同学或网络已有代码的行为均将被视为学术不端。
• 对于如何判定学术不端，以及应该如何正确地引用已有代码，请阅读 Writing Code Writing Code 中文版 抄袭与查重

---

最后更新: 2023年7月4日

作者：Jiajie Chen (95.77%), Harry Chen (0.77%), Harry Chen (3.46%)