inrust
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
自上而下分集计算法 (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 测试 观察， 在 **(x8664, 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