跳转至

作业要求

作业要求分为三部分:

  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 中的 FINALACCEPTABLE)。从标准输入读取一行用户的猜测词:
    • 在每次猜测(获得可用词列表中的输入)后打印猜测结果和以及所有字母的状态:
      • 测试模式:程序启动后,不进行任何输出,等待用户的输入。在测试模式下可以认为输入的答案词符合要求。每次猜测后,如果输入符合要求,则打印一行,形如 SSSSS AAAAAAAAAAAAAAAAAAAAAAAAAA,前面五个字母是用户的猜测结果,后面 26 个字母是所有字母的状态(类似 Wordle 游戏中的输入键盘)。SA 允许的取值包括 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)),再用这个 StdRngshuffle 候选词库,最后以 day - 1 作为下标访问打乱后的数组。

    数组打乱的方法

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

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

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

    提示

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

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

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

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

提示

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

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,那么找到 [,再找到 {,重复类似前面的过程,分别解析出 answerguesses 的内容。最后把数据放在一个自定义的 struct 中。注意字典里面键(Key)的顺序是不固定的,不保证 total_round 一定出现在 games 之前。
  2. 使用 serde_jsonjson 库来操作 JSON。推荐阅读 How to Work With JSON in RustRust - 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 实现:

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

注意事项

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