Algorithm-Template

An awesome Algorithm Template for IO-Driven Single-File Problem(like Online-Judge Problem) !
分布式¹ 去中心化² 的IO驱动型单文件问题³解题模板
Explore the docs »

View Demo · Report Bug · Request Feature

Table of Contents

1. About The Project
   • Built With
2. Getting Started
   • Prerequisites
   • Installation
   • Project Structure
3. Usage
   • Command Line Build
4. Test Introduce
5. Details
6. Roadmap
7. Contributing
8. License
9. Contact
10. Acknowledgments
11. Thanks

About The Project

OJ系统存在着一些特殊要求, 因此考虑到下面的因素, 设计了一套代码模板, 以适应OJ系统的独特环境.

• 上交题目无需修改类名, 方法名等等内容, 只需复制粘贴.
• 支持为每个问题撰写测试用例, 并支持用户之间方便的交换测试用例.
• 只依赖 Unix-Like 系统与一个支持 C++20 的编译器, 外部依赖仅有 Google Test.
• 易于拓展, 提供基本算法接口与实现.

Built With

• 语言: C++ — 提交用源码按 C++11 编译, 测试按 C++20 编译, 因此需要支持 C++20 的编译器.
• 构建: CMake (>= 3.16.6) 与 ccache.
• 测试: Google Test / Google Mock.
• 可选: Podman 容器开发环境, 见 script/container.sh.

(back to top)

Getting Started

2021年代码已存储到单独分支, https://github.com/Certseeds/algorithm-template/tree/2021fall

1. 下载Release中的压缩包或者另一个压缩包, 之后解压使用(简易)
2. 使用绿色按钮Use This Template, 生成仓库, clone下来使用(推荐)
3. fork repo, clone下来使用(不推荐, fork的仓库只有合入主仓库才被github计入提交图)

Prerequisites

环境准备

推荐使用 windows subsystem linux 2 Ubuntu-26.04, 换好 apt 源之后只需要

yes | sudo apt-get update
yes | sudo apt-get upgrade
yes | sudo apt-get install build-essential ccache cmake
yes | sudo apt-get install libgtest-dev libgmock-dev

注意: GTest 需要和编译器在同一环境下安装。

• 系统 GCC → apt install libgtest-dev libgmock-dev
• conda GCC → conda install -c conda-forge gtest gmock
• 若混用 (如 conda GCC + apt GTest)，CMake 可能找不到库或头文件。

• 命令行检测gcc版本

# username @ ${pcName} in ${path}
gcc --version
# username @ ${pcName} in ${path}
g++ --version
# username @ ${pcName} in ${path}
ccache --version

Installation

• generate

点击绿色按钮Use This Template, 生成仓库

• clone生成的自己的仓库到本地

# 在use this template之后
git clone https://github.com/${YOUE_GITHUB_USER_NAME}/algorithm-template.git

• 使用CLion打开仓库

• 可选项:

  • 使用脚本产生自定义的文件(适合source.zip或者有bonuslab): 使用命令行, 进入./script下, 编辑file_template的labs & problem_orders, python3 ./file_template.py, 出现produce files finish提示, 即为创建成功.

Project Structure

.
├── CMakeLists.txt        # 顶层构建入口, 自动发现 lab_* 目录
├── cmake/                # 构建配置: 编译类型 / 跨平台 / 并行 / ccache / policy
├── include/              # 公共头文件, 以 Interface Library 提供给各题目
│   ├── gtest_main.hpp    # 测试入口, 引入 gtest/gmock 与 public.hpp
│   ├── include/          # CS203_redirect / CS203_sequence / CS203_timer 等工具
│   ├── class_helper/     # nonable 等基类
│   ├── list/ tree/       # 链表 / 树 / Trie 等数据结构
│   └── magic_macro/      # 手动开优化用的宏
├── lab_00/               # 一个 lab, 内含若干题目
│   ├── CMakeLists.txt    # 声明本 lab 下的题目列表
│   └── A/                # 一道题目
│       ├── main.cpp      # 将要提交的源文件, 含 read()/处理函数/output()
│       └── test.cpp      # Google Test 测试
├── script/               # 模板生成 / 一键构建 / 容器脚本
└── .github/workflows/    # CI(提交触发) 与 CD(Tag 触发 Release)

• include/ 通过 CMake Interface Library 暴露, 各题目用 target_link_libraries 链接.
• lab_*/ 由顶层 CMake 用 file(GLOB ...) 自动发现, 新增 lab 后重新 configure 即可.

(back to top)

Usage

执行代码和测试:

在 CLion 中

使用 CLion 打开文件夹, 配置好 C++ 环境后会自动识别 CMakeLists.txt, 并生成若干可运行项:

• ALGORITHM_lab_00_A: 调用 lab_00/A/main.cpp, 即将要提交的源文件.
• ALGORITHM_lab_00_A_test: 调用 lab_00/A/test.cpp, 对其进行测试.

可运行项命名规则为 ALGORITHM_lab_{lab 编号}_{题号}, 其中 lab 编号为两位数字、题号为字母, 例如 ALGORITHM_lab_00_A 对应 lab_00 的 A 题.

Command Line Build

仓库提供 script/test.sh, 在仓库根目录执行即可完成配置、编译与 ctest.

bash script/test.sh

脚本会在临时目录中基于 CMake 构建并运行全部测试, 结束后自动清理. 也可手动执行:

cmake -S . -B cmake-build-debug -DCMAKE_BUILD_TYPE=Debug
cmake --build cmake-build-debug --parallel "$(nproc)"
cd cmake-build-debug && ctest --output-on-failure

若需要在容器内开发, 可使用 script/container.sh 启动预配置好的镜像.

(back to top)

Test Introduce

为什么要将 读取 数据处理 输出 分开?

1. 便于理清思路, 读完题目之后, 不管别的, 先把数据读入, 输出的函数写好, 方便后续写作.
2. 交流代码逻辑的时候不会受到无关逻辑的影响
3. 可以互相分享少量代码而不触及核心逻辑, 方便协作.
4. 便于使用测试.

约定: read() / 处理函数 / output()

每道题的 main.cpp 按同一套签名组织, 使读取、处理、输出彼此独立:

using input_type = ...;   // 输入数据的类型
using output_type = ...;  // 输出数据的类型

input_type read();                     // 从 cin 读入
output_type solve(const input_type &); // 处理函数, 名称随题目而定
void output(const output_type &);      // 写到 cout

int main() {
    const auto input_data = read();
    const auto output_data = solve(input_data);
    output(output_data);
    return 0;
}

• 处理函数名随题目而定 (如 isBipartite), 但签名约定一致, 便于测试直接调用.
• test.cpp 通过 #include "main.cpp" 复用这些函数, 并用 CS203_redirect 重定向 IO.
• 每个 test.cpp 需实现 getFilePath() 并据此定义 CS203_redirect::file_paths, 详见下文重定向部分.

基本测试用例展示 A+B: lab_00_A , 测试样例

• 这个问题较为简单, 见A+B 解决起来不复杂.
• 虽然可以手工一个一个输入, 然后观察输出. 但是如果我们希望严谨的测试, 要100组测试数据, 难道每次出新版本都要手动输入100次吗?

显然, 有更好的解决方式:使用测试框架.

• 在本repo, 使用 Google Test 测试框架.
  • 比如, 我们有四组数据, 第一组, 第二组测试边界值, 第三组使用随机数测试对偶性与正确性, 第四组测试几个手动的随机值.
  • 参见test_for_lab00_A
• 这样一来, 我们只需要每次修改完主文件之后, run ALGORITHM_lab_00_A_test, 对其进行调用, 就能验证其在所有的测试用例上的正确性.

多个输出值的检查: EXPECT_EQ

上面的例子里, 输出值只是一个值, 所以手动检查的难度不大, 但是如果目标输出是一个数组, 那么手动检查的难度就非常大了.

举例:Crzay Plan, 输入可能有1.1*10^6个.

这种情况下对这么多值进行直接的观察就很难, 所以我们预先将期望的值直接写在测试文件里, 用Google Test内置的EXPECT_EQ比较(见test_for_lab00_B部分.)

PS: 当然, 这种情况也只适用于规模比较小的情况, 规模再大的话, 直接由人手动写在测试文件里也太占空间了.

输入输出重定向-Stage 1: 从文件中读取输入

常见于tree, graph类的问题, debug需要的数据集都比较大, 不方便直接写在代码中.

比如判断二分图, 一张图可以有几十上百个node, 写在内部占用空间太大.

而在这里, 使用CS203_redirect对象, 便可以省去手动输入的方式.

TEST(lab_00_C, test_case_1) {
  const CS203_redirect cr{"01.data.in", ""};
  // 重定向开始, 开始run
  // or CS203_redirect cr{"01.data.in"};
  const auto output_data = isBipartite(read());
  // 重定向结束
  EXPECT_FALSE(output_data);
}

只需要准备好输入的数据与结果, 就可以从文件中读取, 执行后判断结果是否符合预期.

• test case 1-5为最简单的逐个判断, 最简单, 代码量最大.
• test case loop 则优化了一些, 但是还是比较麻烦, for循环还需要了解测试样例的个数.
• test case with tuple 则最优雅, 修改起来的难度最小.
• test case with sequence 比tuple更优雅, 输入, 输出全为自动产生.

PS: 此处注意, 01.data.in 这类路径是相对于编译产物所在目录解析的, 而非相对于 test.cpp.

每个 test.cpp 中的 getFilePath() 返回资源目录相对编译产物目录的路径, 例如 lab_00/C/test.cpp:

std::string getFilePath() noexcept { return "./../../../lab_00/C/resource/"; }
const std::string CS203_redirect::file_paths = getFilePath();

以 cmake-build-debug 为例, 测试产物位于 cmake-build-debug/lab_00/C/ 下, 因此需要 ./../../../ 回到仓库根目录, 再拼接 lab_00/C/resource/. 换用其它构建目录时, 相对层级可能不同, 需相应调整 getFilePath().

输入输出重定向-Stage 2: 从文件中读取输入, 将输出定向到文件中

• 一般来说, 题目的输出不会太复杂, 但是反例也不是没有.:比如专门考输出的立体图
• 这种情况下, 使用c++的重定向输出就可以较为方便的对输入进行处理, 同时保存输出方便调试.

  TEST(lab_00_D, test_case_2) {
    {
      const CS203_redirect cr{"01.data.in", "01.test.out"};
      auto input_data = read();
      cal(input_data);
    }
    EXPECT_TRUE(compareFiles("01.test.out", "01.data.out"));
  }

这样就将标准输出重定向到了01.test.out中, 并与01.data.out比对.

PS: 至于比较文件之间的差异, 可以使用内置的compareFiles(string path1, string path2)函数进行比较.

参考文本比对_test_case_2

Details

为什么要选择C++做题?

1. C++ 参考用例更多, 相关资源更丰富
2. 速度.

• oj内一般java的最大运行时间都会是c++的2倍, 显然是暗示速度之间的差别.
• 其次, C++可以通过一些魔法操作, 比如下文的优化等操作再获取一些时间上的优势.

3. 对数据结构的友好性

涉及到类似Node, Tree, Graph等等数据结构, 这类数据结构使用C++写, 比较方便理解.

4. 对算法友好的性能:

之前写树和图相关的题目时, 最头疼的就是Java的爆栈, 有一段时间只要用递归就爆栈, 相同算法修改为C++之后问题就消失了.

如何手动开优化

1. 将magic_optimize内的内容粘贴到代码最上方.
2. 关闭同步,

static const auto faster_streams = [] {
    srand(time(nullptr));
    // use time to init the random seed
    std::ios::sync_with_stdio(false);
    std::istream::sync_with_stdio(false);
    std::ostream::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    // 关闭c++风格输入输出 , 与C风格输入输出的同步, 提高性能.
    return 0;
}();

关闭同步的代码已放在每道题 main.cpp 的最下方, 注意不要混用C风格输入输出(scanf, printf)与c++风格输入输出(cin, cout)

通常情况下, 可以将运行时间缩短到1/2甚至更少.

Why choose googletest

自 Ubuntu 22.04 开始, googletest的预编译包被打包进了官方的源中 (libgtest-dev 和 libgmock-dev), 不再需要自行编译. 因此可以直接通过系统的包管理器安装并使用.

yes | sudo apt-get install libgtest-dev libgmock-dev

考虑到 windows, macos都可以使用容器来运行linux, 只需要近年的 ubuntu lts支持, 就是全平台支持.

Roadmap

• 基础框架
• 测试框架接入
• 测试用例接入文件
• CI-CD
  • CI: GitHub-Actions提交触发
  • CD: Tag触发的自动Release
• 某一学期的完整题目 (见 2021fall 分支)
• ccache 加速编译
• Cyaron 测试数据生成
• WiKi Page

(back to top)

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

(back to top)

License

MIT LICENSE

根目录下, 使用脚本生成的代码均采用Apache 2.0协议, 严谨而宽松.

AGPLv3.0+ LICENSE

非模板部分代码(*.cpp, *.hpp, etc)基于 AGPLv3.0+协议: 限制最强的主流开源协议

• 由于本仓库设计只包括"上交"源码这一种场景, 因此实际上不存在二进制分发以及被云服务使用这种场景.
• 具体内容请看LICENSE_AGPL_V3_0.md

some code is based on this license

CC-BY-NC-SA-4.0+ LICENSE

所有其他非代码部分(主要是*.md)基于CC-BY-NC-SA-4.0(或以后版本)协议.

• 相同方式共享-署名-非商业性使用的知识共享协议4.0或任何以后版本.
• 署名(BY)-使用到相应内容的其他地方, 应该加以注释, 保留来源.
• 非商业性使用(NC)-默认情况下, 只要署名, 可以在不盈利的情况下使用.(并不是指商业情况不能用, 而是需要和原作者沟通)
• 相同方式共享(SA)-使得协议具有传染性, 只要其他内容采用了本repo的内容, 就需要在署名的同时, 保证其协议也是CC-BY-NC-SA-4.0 or later version.
• 具体内容请看LICENSE_CC_BY_NC_SA_V4_0.md

(back to top)

Contact

格式/版权/转载/etc 这类非内容相关问题，请提 issue

添加/删除/修改内容，修改repo相关的，请提 pull_request

讨论内容相关的，请到 Discussion

Project Link: https://github.com/Certseeds/algorithm-template

(back to top)

Acknowledgments

Use this space to list resources you find helpful and would like to give credit to. I've included a few of my favorites to kick things off!

• Img Shields
• Best-Readme-Template
• Choose an Open Source License

(back to top)

Thanks

考虑到whexy 的博客文章用两个晚上做超简易 OpenJudge里因平台显著降低了作业难度。按任课教师要求已经关停。这一句.

设计时将分布式¹ 去中心化² 跨平台³都纳入考虑.

(back to top)