前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >为了测试未知来源的算法题,我写了一个本地刷题工具!

为了测试未知来源的算法题,我写了一个本地刷题工具!

作者头像
TechFlow-承志
发布2022-08-26 18:22:49
发布2022-08-26 18:22:49
38400
代码可运行
举报
文章被收录于专栏:TechFlowTechFlow
运行总次数:0
代码可运行

作者 | 梁唐

大家好,我是梁唐。

最近复习剑指offer的时候发现一个小问题,就是有些题目找不到来源。不知道来源就导致了,没有办法练习。有的时候我还会有一些奇思妙想,比如对题目做一些变形,甚至是自己搞一些原创题等等。

为了解决这个问题,老梁决定在本地搭建一个算法题的测试样例生成和测试工具。这样就可以在本地对算法进行测试了。

目前主要功能已经开发好了,虽然还比较简单,只能算是一个demo版本。但勉强能用,代码我已经开源在了github。点击「阅读原文」进行跳转。

样例生成

整个项目大概分为三个功能,第一个功能当然是样例生成。

样例生成并不简单,因为不同的题目的题面不同,题面不同自然生成数据的算法也不同。这就意味着对于每道题的生成算法都要单独实现。

虽然数据生成的逻辑各不相同,但是运行的核心逻辑是一样的,都是生成数据再写入文件。只不过生成的逻辑各不相同,所以我们可以把样例的生成逻辑抽象出来放到派生类当中,而写入文件等一些核心逻辑在父类中实现。这样对于每道不同的题目,我们只需要关心数据生成逻辑即可,整个调用链路都是可以复用的。

我们先从最简单的结构开始看起,首先是Case类,Case类即测试样例,一个Case的实例表示一个测试样例,它的定义如下:

代码语言:javascript
代码运行次数:0
复制
class Case:
    def __init__(self,*args, **kw):
        raise NotImplementedError()

    def output(self, data_path, result_path, idx):
        raise NotImplementedError()

相当于我们定义了一个接口,并不会直接使用父类。Case类当中只有两个函数,一个是初始化函数,一个是输出函数output

我们再来看一个它子类的例子,这道题是剑指offer第三题,在一个行列皆有序的二维数组当中寻找target是否存在。那么这个子类的构造函数当中实现的就是创建一个有序二维矩阵和target,output则是将结果输入对应的文件。

代码语言:javascript
代码运行次数:0
复制
class Case3(Case):
    def __init__(self):
        # 创建行列均有序的二维矩阵
        n, m = random.randint(1, 100), random.randint(1, 100)
        nums = sorted([random.randint(0, 100000000) for _ in range(n * m)])
        arr = np.array(nums).reshape((n, m))
        ans, k = 0, 0
        if random.randint(0, 100) > 50:
            ans = 1
            x, y = random.randint(0, n-1), random.randint(0, m-1)
            k = arr[x, y]
        else:
            while True:
                k = random.randint(0, 100000000)
                if k not in nums:
                    break
        self.n, self.m, self.k, self.ans = n, m, k, ans
        self.arr = arr

    def output(self, data_path, result_path, idx):
        # 将测试数据输入data_path,答案输入result_path
        # idx为当前测试样例编号
        with open(data_path, 'a+') as f:
            f.write('{} {} {}\n'.format(self.n, self.m, self.k))
            for i in range(self.n):
                for j in range(self.m):
                    f.write('{} '.format(self.arr[i, j]))
                f.write('\n')

        with open(result_path, 'a+') as f:
            f.write('case :{}\n'.format(idx + 1))
            f.write(str(self.ans))
            f.write('\n')

我们实现了样例的创建逻辑之后,为了将创建逻辑和生成逻辑解耦,我们把这个类本身当做参数传给样例构造的类Generate

代码语言:javascript
代码运行次数:0
复制
class Generate:
    def __init__(self, n, problem_id, Case):
        # 将Case的实现子类以参数形式传入
        self.n = n
        self.problem_id = problem_id
        self.output_path = os.path.join(output_path_base, '{}.txt'.format(problem_id))
        self.result_path = os.path.join(result_path_base, '{}.txt'.format(problem_id))
        self.cases = []
        self.Case = Case

    def generate(self):
        for _ in range(self.n):
            # 样例的具体生成逻辑都在Case类的初始化函数当中实现了
            self.cases.append(self.Case())

    def output(self):
        # 生成输入的文件地址
        if os.path.exists(self.output_path):
            os.remove(self.output_path)

        if os.path.exists(self.result_path):
            os.remove(self.result_path)

        f = open(self.output_path, 'w')
        f.write('{}\n'.format(self.n))
        f.close()

        # 打印相关信息
        for i in range(self.n):
            print('generating case{}ing'.format(i))
            self.cases[i].output(self.output_path, self.result_path, i)
        f.close()

算法编写

测试样例生成了之后,接下来要做的就是编写算法了。

我们采用最常规的C++来编写,由于测试样例已经输入了文件,当前我们就有两个选择。一个选择是在C++当中进行文件的处理操作,第二个选择是在以命令编译执行C++代码时以数据流的形式指定文件。

前者需要我们将对应的文件路径写在代码里,耦合性比较强,所以我选择了后者,在执行C++的时候做数据流的定向,如:

代码语言:javascript
代码运行次数:0
复制
g++ xxx.cpp -o cur
./cur < input.txt > output.txt

既然如此,那么我们只需要在C++代码当中使用标准输入输出即可。使用标准输入输出之后,我们就可以随意玩耍了。不过为了代码看起来更加标准,我还是采用了LeetCode风格。即将算法执行逻辑以函数的形式实现,和数据处理的逻辑完全拆分开:

代码语言:javascript
代码运行次数:0
复制
int tcase;
cin >> tcase;

for (int _i = 0 ; _i < tcase; _i++) {
    int n, m, target;
    cin >> n >> m >> target;
    vector<vector<int>> mat(n, vector<int>(m, 0)); 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }
 // 算法实现在findNumberIn2DArray 函数中
    cout << findNumberIn2DArray(mat, target) << endl;
}

本地校验

最后是校验的逻辑,其实校验的逻辑很简单,也就是把C++的输出结果和我们创建数据时候的正确答案进行比对。

使用Python的os库,可以实现在Python当中调用shell命令,完成一些比较复杂的功能。比如说调用g++编译C++代码,并进行调用:

代码语言:javascript
代码运行次数:0
复制
def get_cpp_result(code_path, bin_path, data_path, output_path):
    # 编译
    compile_st = os.system('g++ -std=c++17 -o {} {}'.format(bin_path, code_path))
    if compile_st > 0:
        print('compile error!')
        delete_files(bin_path)
        return [], False
    os.system('mkdir cur')
    # 运行
    run_st = os.system('./{} < {} > {}'.format(bin_path, data_path, output_path))

    if run_st > 0:
        print('run time error!')
        delete_files(bin_path)
        os.system('rm -rf {}'.format(output_path))
        return [], False

    ret = []
    with open(output_path, 'r') as f:
        for l in f.readlines():
            ret.append(l)

    delete_files(bin_path)
    return ret, True

最后, 当C++代码执行结束之后,再和我们生成数据时的正确答案进行比对。

在这个工具当中,为了简便,我直接使用的字符串比对。一般的结果直接当做字符串比对即可,有些特殊的题目可能需要special judge,也就是进行一些特殊的比对。比如有些题目的正确答案可能有多个, 任一输出一个即可,再比如有些题目输出的结果是一个浮点数,由于是浮点数所以没办法要求完全一致,一般都是给定精度,只要误差在这个范围内也算是正确等等。

不过special judge的逻辑相对复杂一些,目前还不支持,以后有需要用到了再完善。

这个项目是我心血来潮写的,毕竟还只是初版,有不完美或遗漏的地方在所难免。如果有什么疑问或者需求不妨给我留言,也欢迎大家开发新的功能给我提PR。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-11-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Coder梁 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 样例生成
  • 算法编写
  • 本地校验
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档