# skill_tree_algorithm

`算法(algorithm)技能树` 是[技能树森林](https://gitcode.net/csdn/skill_tree)的一部分。

## 初始化

```
pip install -r requirement.txt
```


## 目录结构说明

* 技能树`骨架文件`：
    * 位置：`data/tree.json` 
    * 说明：该文件是执行 `python main.py` 生成的，请勿人工编辑
* 技能树`根节点`配置文件：
    * 位置：`data/config.json`
    * 说明：可编辑配置关键词等字段，其中 `node_id` 字段是生成的，请勿编辑
* 技能树`难度节点`：
    * 位置：`data/xxx`，例如: `data/1.算法初阶`
    * 说明：
        * 每个技能树有 3 个等级，目录前的序号是必要的，用来保持文件夹目录的顺序
        * 每个目录下有一个 `config.json` 可配置关键词信息，其中 `node_id` 字段是生成的，请勿编辑
* 技能树`章节点`：
    * 位置：`data/xxx/xxx`，例如：`data/1.算法初阶/1.蓝桥杯`
    * 说明：
        * 每个技能树的每个难度等级有 n 个章节，目录前的序号是必要的，用来保持文件夹目录的顺序
        * 每个目录下有一个 `config.json` 可配置关键词信息，其中 `node_id` 字段是生成的，请勿编辑
* 技能树`知识节点`：
    * 位置：`data/xxx/xxx/xxx`，例如：`data/1.算法初阶/1.蓝桥杯/7段码`
    * 说明：
        * 每个技能树的每章有 `n` 个知识节点
        * 每个目录下有一个 `config.json`
            * 其中 `node_id` 字段是生成的，请勿编辑
            * 其中 `keywords` 可配置关键字字段
            * 其中 `children` 可配置该`知识节点`下的子树结构信息，参考后面描述
            * 其中 `export` 可配置该`知识节点`下的导出习题信息，参考后面描述


## `知识节点` 子树信息结构

例如 `data/1.算法初阶/1.蓝桥杯/7段码/config.json` 里配置对该知识节点子树信息结构：
```json
{
    // ...

    "children": [],
}
```



## `知识节点` 的导出习题编辑

例如 `data/1.算法初阶/1.蓝桥杯/7段码/config.json` 里配置对该知识节点导出的习题

```json
{
    // ...
    "export": ["solution.json"]
}
```

格式说明：
* `file`: 指定该目录下的习题源文件
* `variants`： 指定习题同名的json选项配置文件，参考下一节
* `depends`: 如果习题依赖同目录下的其他习题源代码，则在此字段里配置依赖的其他习题源文件名

## `知识节点` 的导出习题选项配置编辑

首先，我们根据前文，在 `data/1.算法初阶/1.蓝桥杯/7段码` 目录增加一个`solution.json`文件：

```json
{
    "type": "code_options",
    "author": "卢昕",
    "source": "solution.md"
}
```

然后在 `data/1.算法初阶/1.蓝桥杯/7段码` 下增加一个`solution.md`文件：

````markdown
# 7段码
#### 题目描述
小蓝要用七段码数码管来表示一种特殊的文字。  
![七段码](https://img-blog.csdnimg.cn/2020110916441977.png#pic_left)   
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。

* 例如：b 发光，其他二极管不发光可以用来表达一种字符。

* 例如：c 发光，其他二极管不发光可以用来表达一种字符。

这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。

* 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。

* 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

## aop
### before
```cpp
#include <iostream>
using namespace std;
int use[10];
int ans, e[10][10], father[10];
void init()
{

	e[1][2] = e[1][6] = 1;
	e[2][1] = e[2][7] = e[2][3] = 1;
	e[3][2] = e[3][4] = e[3][7] = 1;
	e[4][3] = e[4][5] = 1;
	e[5][4] = e[5][6] = e[5][7] = 1;
	e[6][1] = e[6][5] = e[6][7] = 1;
}

int find(int a)
{
	if (father[a] == a)
		return a;
	father[a] = find(father[a]);
	return father[a];
}
```
### after
```cpp
int main()
{
	init();
	dfs(1);
	cout << ans;
	return 0;
}

```

## 答案
```cpp
void dfs(int d)
{
	if (d > 7)
	{
		for (int i = 1; i <= 7; i++)
		{
			father[i] = i;
		}

		for (int i = 1; i < 8; i++)
		{
			for (int j = 1; j < 8; j++)
			{
				if (e[i][j] == 1 && use[i] && use[j])
				{
					int fx = find(i);
					int fy = find(j);
					if (fx != fy)
					{
						father[fx] = fy;
					}
				}
			}
		}
		int k = 0;
		for (int i = 1; i < 8; i++)
		{
			if (use[i] && father[i] == i)
			{
				k++;
			}
		}
		if (k == 1)
		{
			ans++;
		}
		return;
	}

	use[d] = 1;
	dfs(d + 1);
	use[d] = 0;
	dfs(d + 1);
}
```
## 选项

### A
```cpp
void dfs(int d)
{
	if (d > 7)
	{
		for (int i = 1; i <= 7; i++)
		{
			father[i] = i;
		}

		for (int i = 1; i < 8; i++)
		{
			for (int j = 1; j < 8; j++)
			{
				if (e[i][j] == 1 && use[i] && use[j])
				{
					int fx = find(i);
					int fy = find(j);
					if (fx != fy)
					{
						father[fx] = fy;
					}
				}
			}
		}
		int k = 0;
		for (int i = 1; i < 8; i++)
		{
			if (father[i] == i)
			{
				k++;
			}
		}
		if (k == 1)
		{
			ans++;
		}
		return;
	}

	use[d] = 1;
	dfs(d + 1);
	use[d] = 0;
	dfs(d + 1);
}
```

### B
```cpp
void dfs(int d)
{
	if (d > 7)
	{
		for (int i = 1; i <= 7; i++)
		{
			father[i] = i;
		}

		for (int i = 1; i < 8; i++)
		{
			for (int j = 1; j < 8; j++)
			{
				if (e[i][j] == 1)
				{
					int fx = find(i);
					int fy = find(j);
					if (fx != fy)
					{
						father[fx] = fy;
					}
				}
			}
		}
		int k = 0;
		for (int i = 1; i < 8; i++)
		{
			if (use[i] && father[i] == i)
			{
				k++;
			}
		}
		if (k == 1)
		{
			ans++;
		}
		return;
	}

	use[d] = 1;
	dfs(d + 1);
	use[d] = 0;
	dfs(d + 1);
}
```

### C
```cpp
void dfs(int d)
{
	if (d > 7)
	{
		for (int i = 1; i <= 7; i++)
		{
			father[i] = i;
		}

		int k = 0;
		for (int i = 1; i < 8; i++)
		{
			if (use[i] && father[i] == i)
			{
				k++;
			}
		}
		if (k == 1)
		{
			ans++;
		}
		return;
	}

	use[d] = 1;
	dfs(d + 1);
	use[d] = 0;
	dfs(d + 1);
}
```
````

后续的处理程序会根据“答案”、“选项”等标题查找内容，选项章节内部的三级标题不会进入题目，可以用来标注选项信息，例如
“语法错误”，“内存没有初始化”等等。

## 技能树合成

在根目录下执行 `python main.py` 会合成技能树文件，合成的技能树文件: `data/tree.json`
* 合成过程中，会自动检查每个目录下 `config.json` 里的 `node_id` 是否存在，不存在则生成
* 合成过程中，会自动检查每个知识点目录下 `config.json` 里的 `export` 里导出的习题配置，检查是否存在`exercise_id` 字段，如果不存在则生成