Rust 学习项目从头开始

一个用于积累我对 Rust 编程和工程知识的项目。

解决 24点游戏/谜题 计算

经典的 24 点计算：给定任意 4 个 1-10 或 1-13 的整数 (扑克牌数) ， 使用 (+, -, *, /) 四则计算和括号组合成算术表达式，使其计算结果为目标数 24 (30 以内因数最多的合数)；

泛化的 '24' 点计算：给定任意个 有理数， 使用 (+, -, *, /) 四则计算和括号组合成算术表达式，使其结果为某个任意给定的 目标有理数；

并且要求去重：只输出计算形式/方法/结构上 唯一/不相同 的所有 表达式结果； (all algebraically unique/inequivalent solutions)

Input integers/rationals for 24: 1 2 3 4
1*2*3*4
(1+3)*(2+4)
4*(1+2+3)

Input integers/rationals for 24: 8 8 3 3
8/(3-8/3)

Input integers/rationals for 24: g100 13 14 15 16 17
### Reset GOAL to 100 ###
16+(17-14)*(13+15)
(17-13)*(14+15)-16

PS: 还使用 Yew 框架开发了一个 在线的交互界面。

自上而下分集计算法 (Top-down divide)

全搜索的 计算复杂度： O(n) ~= ((2^{n-1} - 1) * 5) * ((2^{n-2} - 1) * 5) * ... * ((2^1 - 1) * 5)

动态规划 与 递归分解

自下而上递归构造法 (Bottom-up construct)

全搜索的 计算复杂度： O(n) ~= (C^2_n * 5) * (C^2_{n-1} * 5) * ... * (C^2_2 * 5)

在位递归构造 与 复制递归构造

规避等价表达式

prune repeated combinations by the same numbers and symmetries with hashmap (构造法只能对最后的完整表达式规避)；

Commutativity (selecting a bias by lexicographical comparison);

((A . B) . b) => (A . (B . b)), kept the right sub-tree only;

((A / B) * b) => ((A * b) / B) if b != 1,
(a * (A / B)) => ((a * A) / B) if a != 1, (1 * x) => kept in the final only,
(a * (A * B)) => (A * (a * B)) if A  < a;

((A - B) + b) => ((A + b) - B) if b != 1,
(a + (A - B)) => ((a + A) - B) if a != 0, (0 + x) => kept in the final only,
(a + (A + B)) => (A + (a + B)) if A  < a;

Asymmetric select subtraction by judging sign of the target/goal;
(b - (B - A)) => ((b + A) - B), (x - 0) => (0 + x),
((A + x) - x) => kept in the final only;

(a / (A / B)) => ((a * B) / A), (x / 1) => (1 * x), (0 / x) => (0 * x),
((x * B) / x) => ((x + B) - x);

用 C++ 实现同样的算法并对比性能

基本上用 C++ 实现上述四种算法，在 (Apple M1, macOS, Clang) 上性能都比 Rust 的实现 差；通过 GitHub Action/workflow 的 CI 测试 观察，在 (x86_64, Ubuntu, GCC) 上 Rust 的实现也比 C++ 要 快；是因为 Rust 的 Rc 实现比 C++ 的 SharedPtr 的性能好？

Rust/C++ 版本前一类算法的性能都比后一类算法高一个数量级，个数越多性能差异越大；但它们在当前的主流 PC 上计算 9-10 个数的时间就都难以忍受了；

代码片段精华

• 猜数字游戏
• 单链表
• 简单的幂集 (powerset) 算法
• Fibonacci 数列迭代生成器
• 流式 Pi 值计算
• 命令管道

积累和 TODO

• 宏/proc-macro
• SVG/XR/游戏
• 并发
• CodeLLDB
• crates.io
• (cargo-)flamegraph
• benchmark/criterion
• C/C++ FFI & build.rs
• 构建时间戳 & 提交-ID
• 自动代码 覆盖率
• 问号 (?) 的错误传播
• cargo/crate/module/workspace 组织
• 国际化 (i18n) 使用 Fluent
• UI/WebAssembly (Yew/Perseus/ Sycamore/Dioxus/ slint/egui)
• 持续集成/部署 (Github Action)
• 持续 (单元/集成/文档/模糊) 测试
• 条件编译
• Rust 编程

参考资料

24-Game Solver

• https://github.com/MaigoAkisame/enumerate-expressions
• https://zhuanlan.zhihu.com/p/34015231
• https://github.com/wiebemarten/gamemn
• https://github.com/auntyellow/24
• https://github.com/mhfan/smonde
• https://4shu.net/theory/