# card24

**Repository Path**: Kenneth-Lee-2012/card24

## Basic Information

- **Project Name**: card24
- **Description**: a game solver for 24dian。
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-10-13
- **Last Updated**: 2024-03-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 简单写一个计算24点的程序

写这个工程的目的是希望通过一个“有趣的游戏”给一位开始学习C++的同学介绍怎么组织一
个比较复杂的程序。

24点游戏就是出四张扑克牌，通过四则运算得到24的一个游戏。我们这里泛化一下，我们
给定一个目标，Target，和一组正整数，Ints，求一个解释解，通过四则运算组合Ints求
得到Target的方法。

我这个问题的数学方法没有深入的分析，所以这里用最简单的穷举方法，如果：

```
  Ints = (i_0, i_1, ... i_n)
  Ops = (+, -, *, /) = (op_i)
```

我们要穷举所有的计算组合，就要把Ints分成两组，每组各自递归，然后把两组用4种计算
中的某一种计算出来。之后逐步递归，直到算出答案，最后比较是否等于Target就可以了。

分组是个简单的排列组合问题，只要穷举就行。麻烦的是什么时候执行计算，如果每次都
执行计算，到最后我们都不知道这个结果是怎么算的。所以我这样安排数据结构：

![data_struct](card24.svg)

我们输入的数据放到一个ValComp的数据结构中，ValComp-\>vals是它包含的所有数据，
vals包含超过一个数字，我们就穷举它分解成两组的所有情况，然后把原来的ValComp作根，
创建两个新的ValComp作为它的两个操作数。然后递归地对它的两个操作数重复这样的操作，
直到所有叶子节点的ValComp只有一个参数。

另一个难处理的问题是除法，除法破坏了整数的闭包，有可能让结果包含小数数，这会有
误差，导致不是解释解。一种简单的方法是就用浮点，只要误差在范围内就接受它。另一
种方法是计算结果用解释解的方式保存，我们在最终计算的时候再进行合并。我这里的选
择是两种方法各自实现一个。所以我们用Val封装这个数，选择不同的Val的实现来实现不
同的算法。

Target和Ints通过命令行传递进去。第一个参数是Target，后面的是Ints。比如你这样写：

```
  card24 24 10 10 4 4
```

就是用10, 10, 4, 4计算24。

# 算法细节

## 枚举算法

这是个典型的递归算法，如果不用递归，其实也是要模拟递归，反正它的循环不是固定层
次的循环可以解决的，因为for的层次数是固定的。只有我们知道有多少维，我们才能用循
环，而这个循环是不知道维的数量的。

或者我们应该这样说：所有需要回溯（比如树的遍历）基本上都是递归算法，否则就需要
通过堆栈保存回溯点，不用语言本身的回溯能力，就不得不自己管理回溯点，这最终就是
个堆栈。而递归算法本身其实就是堆栈。

我们通过先把输入分成两个集合加上操作符来枚举，如果我们有集合{1, 2, 3, 4}，我们
先分成：
```
  {1} {...}
  {2} {...}
  {3} {...}
  {4} {...}

  {1, 2} {...}
  {1, 3} {...}
  {1, 4} {...}
  {2, 3} {...}
  {2, 4} {...}
  {3, 4} {...}
```
首先，我们不用管右值。如果给定全集，选定了左值，右值就是固定的。但左值和右值对
称的不用做多次。所以首先枚举左值的集合的势（Power）只要到全集的一半就可以了。而
且枚举每列的取值不用向回取组合，第一列取2，第二列从3取起即可。

但即使这样还是有重复，当全集的数量是偶数的时候，{1, 4}和{2, 3}就是重复的，上面
的算法过滤不了这种情况，如果这个数量少就罢了，但这是个递归算法，在一层有这个问
题，每次经过分解的层是偶数的时候，都会有这个冗余。

所以偶数全集的枚举，下一列递归只需要递归剩余数量的一半就可以了。我们用6个数的集
合作为全集做例子就能看出来：
```
  左集合
  {1, 2, 3}
  {1, 2, 4}
  {1, 2, 5}
  {1, 2, 6}
  {1, 3, 4}
  {1, 3, 5}
  {1, 3, 6}
  {1, 4, 5}
  {1, 4, 6}
  {1, 5, 6}

  {2, 3, 4}  <-- 重复
  {2, 3, 5}  <-- 重复
  {2, 3, 6}  <-- 重复
  {2, 4, 5}  <-- 重复
  {2, 4, 6}  <-- 重复

  {3, 4, 5}  <-- 重复
  {3, 4, 6}  <-- 重复

  {4, 5, 6}  <-- 重复
```

所以规律其实很简单，偶数全集就枚举第一个数就够了。（其实如果数字的值如果有重复，
我们还可以压缩一些数量，但这个工程主要是展示逻辑复杂的程序是怎么一点点构建起来
的，暂时我们不做这种优化。）

## 内存算法

每个枚举实例，都需要一棵计算树。比如你一开始有{1, 2}这个集合，你分解成{1}+{2}和
{1}-{2}两个计算，它们不可能共同原来的{1, 2}，{1, 2}必须被复制给两棵计算树。我们
需要决定什么时候分配新的树节点，什么时候释放这些节点。

我采用这样的策略：

1. ValComp本身的clone算法用来克隆整个子树。这个算法提供基础的克隆支持。

2. 如果你枚举到子树的中间，需要把上级的整棵树都克隆了，我们再提供clone\_tree函数。
   比如前面的例子，如果你有{1, 2}下面的{1}节点，你要枚举更多的组合，你要克隆一棵
   新的树进行枚举，你可以用{1}.clone\_tree()。但如果你拿到一棵还没有完成的树进行
   枚举，每个新的枚举都clone了一棵新的tree，那么你必须把原来的树释放掉。这样才不
   会内存泄漏。

下图展示了clone\_tree的算法解释：

![clonetree](clonetree.svg)

## 数据表达

如前所述，我们有两种计算结果的方法，为此我们需要一个通过的数据表达类型。这可以
有两种选择，一种是用模板，但模板在创建的时候要指定具体的类型，还是会创建算法和
具体类型的关联。

另一种选择是用一个统一的抽象父类，但这种方法创建的时候还是要知道具体的子类。

所以算了，我用一个最原始的方法：我直接用宏（Val），需要用什么算法，就把Val定义
成那个具体的类型就行了。需要用浮点算法的时候，就定义成FloatVal，需要用解释算法
的时候，就定义成AnaVal，这两者继承同一个接口ValIf，这样我能保证它们有共同的对外
接口可以用。

对于解释解，我表示成一个分数，记录整数的整部，分子和分母，这会有溢出的可能性。
但如果输入真的是扑克牌，最大才13，最多4张牌，也不怕它溢出了，超过的时候溢出，就
不管了，等有需要的时候再保护吧。

## 单元测试

由于树不好用程序自动校验，我主要用人工的方法做单元测试。每个模块我写一个
ut\_xxx.cpp来测试那个模块的算法。标准方法是人工创建一棵树，打印它的样子，然后在
这棵树上执行算法函数，看看结果的树是不是符合预期。

# 一些反思

## 关于算法

这个程序我2009年左右为了单位内部培训用C写过一次，我记忆中这个程序是比较简单的。
但这次写完，发现比我想象中复杂。做完第一个没有优化的版本（v0.1），就用了接近500
行代码。

我就回去找了一下当时的代码，发现还能找到，只用了144行C的代码（都用sloccount统
计）。我发现关键的区别在于——当时用的递归算法并非穷举所有的组合，而是在一个n个元
素的输入中，穷举任意取其中两个合并为n-1个元素的情形，每次递归把集合的势减一，一
直递归到n=1，判断n是不是24就可以了。这里的关键在于，没有一个左右子树分别递归的
过程，这样内存分配可以每次递归都复用一个n-1个元素的数组，最大内存使用n(n-1)/2的
个元素就可以完成了。

我把那个算法实现了一个card24\_v2的程序，复用了原来的ValComp的数据结构，所以数据
上会有一些冗余，但能明显看到整个复杂度低了很多。

老实说，当时选了那个穷举的方法其实挺随机的，现在这个方法……也挺随机的。也许我们
可以因此总结一些教训是：如果有可能，递归算法最好不要有堆栈变量之外的数据依赖。

## 关于Val的实现

这次实现的这个Val变量不太优雅，既然打算在编译中选择用其中哪个算法，就应该从编译
脚本上直接控制编译谁，造成这个问题的核心原因是一开始对构造函数对子类有依赖这个要素
没有掌握，改着改着就成了现在这样了，现在的版本已经调整了。

# 记录一些这次编程中学习到的一些C++的语言经验

C++不是我的日常工作语言，所以一些语法细节我都是用到才去查的，这里做一些记录。

* 构造函数多态不能直接调用其他构造函数（不会报错，但结果是错的），要写成
  \*this = MyClass(...)，或者写在成员构造列表中。如果调用父类的构造，需要放第一个
  初始化位置，否则初始化顺序可能会有错。（会报warning）
* 成员函数后面放const，表示这个函数可以在常数对象中调用。但当然，非常数函数也
  可以调用。
* 友元不是成员，也用不了父类的函数，这个理智思考都知道，但很容易弄错。
* C++不支持带参构造函数的对象数组创建。