CS203-DSAA-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
3. Usage
4. Roadmap
5. Contributing
6. License
7. Contact
8. Acknowledgments

About The Project

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

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

Built With

(back to top)

Getting Started

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

Prerequisites

This is an example of how to list things you need to use the software and how to install them.

Windows

1. WSL(推荐ubuntu 22.04 | 20.04), sudo apt install build-essential ccache

• 命令行检测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}/CS203_DSAA_template.git

• 使用CLion打开仓库

• 可选项:

  • 将脚本创建的版权声明中的所有者替换成自己:
    1. ./.idea中的#set( ${GITHUB_USER} = "Certseeds") -> #set( ${GITHUB_USER} = "YOUR_GITHUB_NAME")
    2. ./script/file_template.py 里面的 Certseeds to YOUR_GITHUB_NAME,nanoseeds to YOUR_USER_NAME,
  • 使用脚本产生自定义的文件(适合source.zip或者有bonuslab): 使用命令行,进入./script下,编辑file_template的labs & problem_orders, python3 ./file_template.py,出现produce files finish提示,即为创建成功.

(back to top)

Usage: 执行代码和测试

使用clion打开文件夹,配置好C++环境的基础上,会自动识别CmakeList.txt.

产生CS203_lab${order}_${ques_Order},CS203_lab${order}_${ques_Order}_test 形式的复数个可以运行的可选项.

lab${order}_${ques_Order}为对应题号,比如lab07_01对应lab_07的C1题.

• CS203_lab07_01将调用lab_07\lab_07_C1\lab07_C1.cpp,为将要提交的源文件.
• CS203_lab07_01_test将调用lab_07\lab_07_C1\lab07_C1_test.cpp,对其进行测试.
• lab_*\lab_*_*\lab_*_*_test.cpp目的为方便测试,同时便于分享测试用例.

(back to top)

Test Introduce

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

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

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

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

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

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

多个输出值的检查:Catch::Matchers

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

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

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

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

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

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

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

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

TEST_CASE("test case 1", "[test 00 C]") {
  const CS203_redirect cr{"01.data.in", ""};
  // 重定向开始,开始run
  // or CS203_redirect cr{"01.data.in"};
  const auto output_data = isBipartite(read());
  // 重定向结束
  CHECK_FALSE(output_data);
}

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

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

PS: 此处注意,引用文件的相对路径,不是直接的test/lab_00/lab_00_C/resource/01.data.in,

而是编译出的文件相对于测试数据的相对路径.

在样例中,编译出的文件在CS203_DSAA_template/cmake-build-debug下,所以需要加./../

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

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

  TEST_CASE("test case 2", "[test 00 D]") {
    SECTION("do") {
      const CS203_redirect cr{"01.data.in", "01.test.out"};
      auto input_data = read();
      cal(input_data);
    } SECTION("compare files") {
      CHECK(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++是dalao们的选择 直接去 dalao1 dalao2 dalao3 等等dalao的解题页面看看,会发现在排行榜榜首的人,绝大多数题目使用的都是C++.

2. 速度.

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

3. 对数据结构的友好性

DSAA既然内含Data structure,就势必涉及到类似Node,Tree,Graph等等数据结构,这类数据结构使用C++写,比较方便理解.

4. 对算法友好的性能:

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

5. 相关资源的丰富程度

不管怎么说,c++是dalao的选择,所以在网络上搜索题目,得到的大多数答案都是C/C++,java的数量很少.

如何手动开优化

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;
}();

已放置在源文件最下方,注意不要混用C风格输入输出(scanf,printf)与c++风格输入输出(cin,cout)

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

Why choose Catch?

1. 先来看可选项有哪些

FrameWork	Catch2	Google Test	CPPUnit	Boost.Test	Microsoft 单元测试框架
跨平台	√	√	√	√	X
是否需要提前在系统内安装	X	√	√	√	√(and visual studio make it)
语法	简单	简单	复杂	简单	Unknown

先筛选跨平台,去掉了Microsoft,再筛选不需要安装,只剩Catch2, 结束.

Roadmap

• 基础框架
• Catch2 接入
• 测试用例接入文件
• 算法模块添加
  • FFT
  • Tree
    • Trie
    • RB-Tree
    • AVL-Tree
  • Matrix
  • AND MORE...
• 跨平台
  • Windows(No Support becuase ccache do not support MSVC, compile cost too much time and product size)
  • Unix-Like
• CI-CD
  • CI: GitHub-Actions提交触发
  • CD: Tag触发的自动Release
• leetcode题目
• 预编译头文件ccache加速编译
• basic文件夹添加CS205内容,方便入门C++
  • 以及一部分rust代码
• 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

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/CS203_DSAA_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)