mhfan/inrust

Fastest, flexible, complete and inequivalent/non-similar solver for 24 game/puzzle/challenge, algorithms implemented in both Rust and C++

Rust study project from scratch

A project to accumulate my knowledge about Rust programming and engineering.

Solve 24 game/puzzle calculation

经典的 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)

动态规划 vs 递归分解

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

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

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

规避等价表达式

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 个数的时间就都难以忍受了；

Code snippet gems

• Game guess number
• single linked list
• 简单的幂集 (powerset) 算法
• Fibonacci 数列迭代生成器
• 流式 Pi 值计算
• 命令管道

积累和 TODO

• macro/proc-macro
• SVG/XR/Game
• concurrency
• CodeLLDB
• crates.io
• (cargo-)flamegraph
• benchmark/criterion
• C/C++ FFI & build.rs
• build timestamp & commit-ID
• Code coverage automatically
• error propagation by question mark (?)
• cargo/crate/module/workspace organization
• internationalization (i18n) with Fluent
• UI/WebAssembly (Yew/Perseus/ Sycamore/Dioxus/ slint/egui)
• Continuous Integration/Deployment (Github Action)
• Continuous (Unit/Integration/Doc/Fuzz) Test
• conditional compilation
• Rust programming

References

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/