大作业一：Wordle（2021-2022 学年夏季学期）

作业简介

Wordle 是由 Josh Wardle 开发的网页文字游戏，以其简单有趣的规则在 2021 年底风靡全球，并在 2022 年被纽约时报收购。

Wordle 的玩法是（来自 Wikipedia），玩家每日可挑战在六次尝试内，猜出由五个字母所组成的英文单词。所有人每天的单词都一样，来源于作者预先定义的词库（”候选词“），均为比较常见的五字单词。尝试中可以使用的单词（”可用词“）也是预定义的，比候选词的数量更多。

每次尝试后，每个字会显示为绿、黄或灰色：绿色表示字母猜中，而且位置正确；黄色表示单词包含此字母但位置不正确；灰色则表示字母出现的次数多于实际出现的次数。Wordle 还设置有”困难模式“，在此模式下，玩家的猜测必须使用前面已经给出的所有提示，否则为无效猜测。

Wordle 有许多仿制和衍生版，如：

更改规则：Absurdle（非确定目标）、hello wordl（可变词长）
中文版：汉兜、成语 Wordle（四字词语或成语）、诗谜（七言诗句）、词影、笔兜 Strokle（根据笔画猜测）、Zidou（粤语拼音）、注得了（注音符号）
其他语言：略
非书面语言：Numberle、nerdle、math wordle（数学等式）、passWORDLE、sha256le（直接猜测 SHA256）

除了使用纯粹的人类智慧外，也有许多的工具可以帮助解决 Wordle。此类工具通常分为两类，一类只通过现有的猜测结果来筛选剩余的单词，如 [1]、[2]、[3]、[4]、[5]；还有一类直接给出猜测，并根据反馈指导下一步猜测，如 [6]。著名的科普视频作者 3Blue1Brown 也制作了使用信息熵解决 Wordle 的视频（以及对应的勘误）。

作业要求

在本作业中，你需要使用 Rust，基于给出的项目模板实现一个本地版本的 Wordle 游戏。如果没有特殊说明，它应该在各个平台下都能正常工作。

自动化测试

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

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

运行测试的方式详见项目模板。每个测试的名称类似 test_01_20_pts_basic_one_game，名称中即标记了对应的分数。

关于测试的注意事项

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

基础要求（60‘）

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

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

（20分）支持从标准输入指定一个词开始一局游戏（共 6 次猜测）。候选词与可用词内嵌在程序中（分别对应代码 src/builtin_words.rs 中的 FINAL 和 ACCEPTABLE），从标准输入读取用户的猜测：
- 在每次猜测（获得可用词列表中的输入）后打印猜测结果和以及所有字母的状态：
  - 测试模式：程序运行后，不进行任何输出。每次猜测后，如果输入符合要求，则打印一行，形如 SSSSS AAAAAAAAAAAAAAAAAAAAAAAAAA ，前面五个字母是用户的猜测结果，后面 26 个字母是所有字母的状态（类似 Wordle 游戏中的输入键盘）。S 和 A 允许的取值包括 R（Red，数量过多的字母）、Y（Yellow，位置不正确的字母）、G （Green，正确的字母）、X（Unknown，未知状态的字母），语义与作业简介中描述的一致。如答案为 CRANE，猜测 ABUSE 的结果是 YRRRG，猜测 WANNA 的结果是 RYRGR。如果读入的一行不符合要求，则打印 INVALID。在打印所有字母状态时，如果某个字母在猜测中有多个不同的状态，则选择最「好」的一种，即优先级为 G>Y>R>X。
  - 交互模式：每次猜测后向标准输出打印到本次为止的所有猜测结果，以及所有字母的状态（模拟 Wordle 网页的状态）。必须使用带颜色的输出，可用红色替代灰色。
- 在游戏结束（用完六次机会或者猜对）后打印猜测次数（包括猜对的最后一次），如果失败，则还需打印正确答案
  - 测试模式：打印 CORRECT n（其中 n 为猜测次数）/ FAILED ZZZZZ（其中 ZZZZZ 为答案）
  - 游戏结束后正常退出程序
（5分）记现有从标准输入指定答案的模式为指定答案模式。在指定答案模式下，增加命令行参数 -w/--word 用于指定答案，如 -w build 表示指定答案为 build；如果不指定，则依旧从标准输入读入答案。增加命令行参数 -r/--random 用于启动随机模式，在随机模式下，不再采用指定答案模式，而是从候选词库中（项目模版中给定）随机抽取问题。如果没有启动随机模式，则是指定答案模式，即从标准输入指定答案，或者使用 -w/--word 参数来指定答案。此选项不应该改变程序在测试模式下的输出格式。
- 如果想要向程序传递命令行参数，请参考提示中相关内容。
（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，分别是最频繁使用的五个词和次数；如果不足五个，则只要输出实际的数量；
  - 读入一行，如果为 Y 则继续，如果是 N 或者 EOF 标志则退出；
- 交互模式：以自定义方式显示信息
（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，再用这个 StdRng 去 shuffle。
（5分）增加命令行参数 -f/--final-set 以及 -a/--acceptable-set 用于指定候选词库和可用词库文件（如 -f final.txt -a acceptable.txt）。如果不指定，则使用内置的词库。文件的格式均为按行分割的单词列表（不区分大小写）。加载时需要检查是否符合格式要求、是否存在重复，并且候选词库必须严格是可用词库的子集。如果在指定答案模式中，则也要检查用户给定的答案是否在候选词库中。在读入词库后，需要将其全部转为统一的大小写，并按字典序排序。
（5分）增加命令行参数 -S/--state 用于保存和加载随机模式的游戏状态（如 -S state.json），格式为如下的 JSON 文件：

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

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

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

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

在自动测试中，-S/--state 选项在 common.rs 中添加，不在对应的 .args 文件中。

（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），则以后者为准。

提高要求（20’）

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

提高要求部分不应该影响已有的自动化测试。你可以编写额外的可执行文件（在 Cargo.toml 中添加 [[bin]] 段即可，并注意尽量复用已有代码），或者通过额外的编译选项（不同的 feature） /命令行参数来区分。

设计用户界面（不能替代上面的交互模式）：
- （10分）基于 TUI 绘制用户界面（需要在 Linux 下正常工作），至少应有输入区、键盘区
- （15分 ⚠️）基于 GUI 绘制用户界面（可使用任意平台的任意 GUI 框架），效果类似 Wordle 原版体验
- （20分 ⚠️）将程序编译到 WebAssembly，基于 Web 绘制用户界面（DOM / Canvas 均可）
Wordle 求解（此部分均可直接通过标准输入输出交互，不依赖于 UI，候选词列表对于求解器来说是未知的）：
- （5分）基于现有的猜测结果给出提示，即根据用户提供的所有的已用过的字母和状态（或者游戏的当前状态），从可用词列表（ACCEPTABLE）中筛选出所有可能的答案
- （5分）在这些剩余可用词的基础上，给出若干个推荐词（只需要考虑单步最优，例如按照上述视频中的算法，计算信息熵并排序，也可以自己设计合理的算法）
- （5分）实现类似 WORDLESolver 的交互解决 Wordle 功能，此时每一步的猜测都可以不局限于剩余可用词，而是考虑全局最优的情况
- （5分）在实现求解算法的基础上，对整个候选词库测试你算法的平均猜测次数，并给出若干个全局最优（例如猜测次数最少）的起始猜测词
  - 由于可能耗时较长，验收不要求当面运行，给出结果即可
  - 可使用 rayon 等库进行数据并行加速
其他任何未提及的功能：请先与助教确认可行性，并评估应得分数，如未经确认直接实现则不得分

非功能要求（20‘）

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

提示

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

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

下面是一些可以参考的内容：

如何使用第三方库

在实现作业的时候，经常会需要引入第三方库来快捷地完成任务，在上面也给出了一些推荐使用的第三方 crate，那么要如何使用第三方库呢？这里给出一个例子。

例如要实现带颜色的字符串输出，要采用上面的 colored 第三方库，第一步是访问它的文档：https://docs.rs/colored，格式就是 https://docs.rs/第三方库名称。打开文档以后，可以看到它已经提供了一个代码例子：

use colored::Colorize;

"this is blue".blue();
"this is red".red();
"this is red on blue".red().on_blue();
"this is also red on blue".on_blue().red();
"you can use truecolor values too!".truecolor(0, 255, 136);
"background truecolor also works :)".on_truecolor(135, 28, 167);
"you can also make bold comments".bold();
println!("{} {} {}", "or use".cyan(), "any".italic().yellow(), "string type".cyan());
"or change advice. This is red".yellow().blue().red();
"or clear things up. This is default color and style".red().bold().clear();
"purple and magenta are the same".purple().magenta();
"bright colors are also allowed".bright_blue().on_bright_white();
"you can specify color by string".color("blue").on_color("red");
"and so are normal and clear".normal().clear();
String::from("this also works!").green().bold();
format!("{:30}", "format works as expected. This will be padded".blue());
format!("{:.3}", "and this will be green but truncated to 3 chars".green());

阅读上面的代码，已经大概可以看出这个库要如何使用了。接下来，需要使用命令 cargo add colored 把这个库引入到项目的依赖中：

# Add latest version
$ cargo add colored
    Updating `tuna` index
      Adding colored v2.0.0 to dependencies.
             Features:
             - no-color
# If you want a specific version instead of latest
$ cargo add colored@1.0.0
    Updating `tuna` index
      Adding colored v1.0.0 to dependencies.

在 Cargo.toml 文件中也可以看到它的依赖信息已经出现了：

[dependencies]
colored = "2.0.0"

接下来，根据刚刚从它的文档中学习到的使用方法来尝试一下：

use colored::Colorize;

fn main() {
        println!(
        "{} {} {} {} {} {}",
        "blue".blue(),
        "yellow".yellow(),
        "red".red(),
        "bold".bold(),
        "italic".italic(),
        "bold red".bold().red()
    );
}

就可以看到下面的输出：

其他库也是类似的。总结一下使用第三方库的流程：

查看第三方库的文档：https://docs.rs/第三方库
根据文档的样例代码来理解这个第三方库的使用方式
使用 cargo add 第三方库 命令把它引入到项目中
在代码中使用第三方库

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

如何运行 Wordle 程序

在前文已经提到了可以用 cargo run 程序来运行 Wordle。实际上，这个命令做了两件事情：

运行 cargo build 来编译 wordle
运行 wordle，默认情况下是运行 target/debug/wordle

你也可以从运行输出中看出它做的事情：

$ cargo run
   Compiling wordle v0.1.0 (/Volumes/Data/rust-course/tpl_wordle)
    Finished dev [unoptimized + debuginfo] target(s) in 0.39s
     Running `target/debug/wordle`
I am in a tty. Please print colorful characters!
Your name:

大作业要求中，经常需要向程序传递命令行参数，例如在第二点要求中，通过命令行指定答案（-w CARGO），可以使用 cargo run -- -w CARGO 命令：

$ cargo run -- -w CARGO
    Finished dev [unoptimized + debuginfo] target(s) in 0.11s
     Running `target/debug/wordle -w CARGO`

可以看到，在 -- 之后的命令行参数都原样地传递给了 wordle 程序。类似地，你也可以传递其他参数。

如何使用 VSCode 调试代码

如果你已经按照环境配置文档配置好了 VSCode 以及 rust-analyzer 插件，你可以用 VSCode 打开仓库，找到代码中的 Run | Debug 显示：

> Run | Debug
fn main() {}

此时的 Run 和 Debug 分别表示运行和调试该程序。点击以后，它会自动生成启动配置（位于 launch.json 文件），并且进入运行或者调试模式。

按照需求，你可以修改 launch.json 中的内容来自定义传入程序的命令行参数、输入输出重定向等。如果安装了 CodeLLDB 插件（在 launch.json 的配置中可以看到 "type": "lldb"），可以参考 CodeLLDB 的文档进行进一步配置。

如何手工测试

当实现了功能，但是自动测试失败的时候，通常会想手工进行一次测试，来尝试找到问题。

以测例 02_01_specify_answer 为例子，当我们在自动测试的时候看到 case 02_01_specify_answer incorrect 的字样的时候，我们首先进入仓库的 tests/cases 目录下，可以看到这个测例的三个文件：

02_01_specify_answer.in：程序接收的标准输入
02_01_specify_answer.args：程序接收的命令行参数
02_01_specify_answer.ans：程序在测试模式下，应该向标准输出打印的内容

那么，使用 cargo test -- test_02_5_pts_specify_answer 评测的时候，实际上运行了下面的命令：

cargo build
./target/debug/wordle -w build < tests/cases/02_01_specify_answer.in > tests/cases/02_01_specify_answer.out

这里的 -w build 是 02_01_specify_answer.args 中指定的命令行参数。

然后比对 02_01_specify_answer.out 和 02_01_specify_answer.ans 的内容，如果一致，并且程序退出返回值符合预期，则评测通过。

所以如果自动测试报错了，可以按照上面的命令进行手工测试，此时比较方便使用各种调试手段。

对于需要读取和保存状态的测例，自动测试程序还会做如下操作，以 07_01_save_state 为例：

复制 tests/cases/07_01_save_state.before.json 到 tests/cases/07_01_save_state.run.json
运行 wordle 程序，添加命令行参数 --state tests/cases/07_01_save_state.run.json
判断 tests/cases/07_01_save_state.run.json 与 tests/cases/07_01_save_state.after.json 是否表示同样的 JSON 值

注意事项

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

最后更新: 2023年6月2日

作者: Jiajie Chen (60.59%), Harry Chen (38.44%), MZZhang (0.65%), Yufan You (0.33%)