你是否有过周赛当场轻松 AK，但结算分数时却发现自己掉了很多分的时刻呢？如果有的话，那你可能会想知道怎样才能找到新的测试数据来 hack 其他人。

一个常用的办法是阅读其他人的 AC 代码，并思考其中是否包含尚未被检测出的 bug。但一场周赛中有成千上万份代码，难道要一个个手工看过去吗？即使看到了他人的代码，发现 bug 也不是一件容易的事。我们需要更高效准确的方式。

对拍是什么

对拍是一种简单的交叉检验两份程序正确性的方式。假设我们知道程序 A 是正确的，但不确定程序 B 中是否有 bug。一种检验方式是随机生成大量的测试数据，如果在所有这些数据上 A 和 B 都能产生一样的输出结果，那我们就可以大致认为程序 B 也是正确的。这个检验流程虽然遇到某些极难发现的 bug 时会产生漏网之鱼，但一般可以找出绝大部分的 bug。与人工阅读代码构造针对的 hack 数据相比，对拍方法的优点是简单高效。如果一秒钟可以生成一万组数据，那大概率一些奇妙的 corner case 已经包括在其中了，不需要用人脑慢慢思考寻找。

学会了，真容易？但一份份地对别人提交的代码进行对拍也需要花很多的时间。我们想要更自动高效的方法。

自动对拍系统的设计

首先我们需要一个下载所有周赛提交代码的方式，不需要在周赛结果页面上一个个点击复制下来。虽然我不太会，但只要认识一个 JS 的高手朋友就可以轻松解决了。@XYShaoKang

然后需要一个自动随机生成测试数据的方式。对于绝大部分的题目，无脑随机生成一些小数据就够用了。少数更复杂的情况需要一点经验和算法知识(比如怎么卡模拟退火)。

接下来需要以生成的数据作为输入，自动运行所有下载下来的代码，并收集输出结果交叉比较。这有点像在本地搭一个 OJ。不过我没有精力搭一个支持各种编程语言的 OJ(这不是和 LC 抢活干了么)，而且传统 OJ 的测试流程也决定了只能达到一秒测几个数据的速度量级，我希望能对小数据达到一秒测试成千上万份的速度来更快地生成 hack 数据。所以我选择的方案是把所有同语言的提交代码集成到一份代码里，直接一起跑就好了。

一开始测试的目标语言是 C++，方法大概是定义一个形如

class Solution {
public:
	virtual int run(vector<int>& arr, int target) = 0;
};

的基类，然后把大家的 class Solution 重命名为 class Solution#i 并继承 Solution 就好了，跑的时候用一下多态。这个办法需要对大家提交的代码作一些修改，不过我们在下载代码的时候可以顺便做一些编译器预处理的活。整体上这个方案比较粗暴，但实现起来不是很麻烦。应该也有更漂亮一点的语法糖解决方案，比如类似 这个代码。

C++ 的版本有比较多的缺陷，最头疼的还是因为我本地编译环境和 LC 上不太一样，有时候会编译失败或者跑出不一样的结果，每次跑需要花一些时间来修改调试。后来发现还是 python 比较灵活，所以就又开发了个 python 的自动对拍版本。

Python 的话除了要把 class Solution 重命名为 Solution#i 避免命名冲突之外，基本就不需要对大家的提交代码作什么修改了。这里随便讲一些实现上的小细节：

1. 比如有些人会 print 一些东西来调试，这会干扰到我们对对拍结果的观察。那把 print 函数删掉就好了(print=_print，_print 是个空函数)。
2. 有些 import 进来的东西命名比较乱(比如 bisect.bisect)，在最外面覆盖掉就好了。
3. 可以自动找出本题要求的函数名(我用的方法是使用 Solution 类里的最后一个函数的名字，func_name=dir(Solution1())[-1])，这样就不用每次跑之前手工改了。函数参数的话直接打包传就好。注意有时候要先用 deepcopy 把输入参数复制一份，免得被前一个人的代码改掉。
4. 运行一个个类的函数的时候利用 py 的反射机制，A=globals()['Solution%d'%i](), ans=getattr(A,func_name)(*copy.deepcopy(args))。
5. 当一个测试数据 hack 掉了一些代码时，就把这些类的编号记录下来，后续生成数据的时候就不需要测它们了。
6. 跑每份代码的时候记下时间，来检测 TLE。不过我没加跑的时间太久就自动杀掉的功能，一般手工观察下就好。
7. 实际上对拍的时候我们并不知道哪份代码是正确的(即使官方题解也不一定总是对的)，我会默认以排名最高的人的输出作为基准。如果他错了的话就会显示成把其他人都叉掉 :)
8. 另外还有一个群友想要的功能是输出所有被 hack 掉的人的用户名，那可以下载的时候注释记录一下，然后发现一个 class Solution#i 被 hack 掉之后就读自己这份源文件把注释输出来。

整体来说 python 还是挺好用的，每次除了写一下数据生成部分的代码之外就几乎不需要再做什么了，而且很多题的测试数据生成也是很雷同的。熟练使用这个工具后大概两分钟就能跑完整个对拍流程(如果没拍出来的话)。

一些效果展示：

2573. 找出对应 LCP 矩阵的字符串(本周周赛333 T4)：共 41 份 python 提交，其中 16 份 WA，1 份 RE (占比 41%)。
2556. 二进制矩阵中翻转最多一次使路径不连通(双周赛97 T4)：共 102 份 python 提交，其中 74 份 WA，1 份 TLE (占比 74%)。
2531. 使字符串总不同字符的数目相等(周赛327 T3)：共 318 份 python 提交，其中 70 份 WA (占比 22%)。
2499. 让数组不相等的最小总代价(双周赛93 T4)：共 113 份 C++ 提交，其中 52 份 WA，1 份 TLE (占比 47%)。
2468. 根据限制分割消息(双周赛91 T4)：共 233 份 C++ 提交，其中 82 份 WA (占比 35%)。
2117. 一个区间内所有数乘积的缩写(双周赛68 T4)：共 151 份 C++ 提交，其中 150 份 WA (占比 99%)。
(你是否在这些数字中呢？^_^)

一点开发历史

这个项目的雏形是在一年前 双周赛68 出现的，也就是上面列出的那个 99% 的人 WA 了的题。当时 @XYShaoKang 帮我把所有提交代码下载下来了，我自动测了下所有 C++ 的提交，发现只有一人通过(历史遗址在 这里)。后来虽然这个 C++ 的测试系统问题比较多，不是很好用，不过还是帮助产生了不少测试数据。比如我在 github 上给 488. 祖玛游戏 提交了 27 个数据，叉掉了当时大概 70% 显示在 AC 直方图里的人。
后来大概去年 12 月的时候发现实在还是 python 好用，就开发了上面那个 py 的对拍系统版本。因为用起来方便了很多，所以把所有题都拍一遍也花不了多少时间，基本上我都测了(于是发现有些人的 T1 都能 hack)。如果有人感觉最近几次周赛 rejudge 的次数显著变多了，那可能是这个项目的锅。

有待改进的问题

1. 不同的选手可能会定义同一个名称的类，比如 class UnionFind 这样很常用的东西。如果都放在最外层作用域的话它们之间会互相覆盖，产生一些神奇的问题。我在 C++ 里的解决方案是把每个人的代码用一个 namespace #i 包起来，隔离作用域。但对于 python 就不知道怎么办。分很多个文件存然后 import 么？
2. 有些人会在 Solution 类的外面写一些代码来测试，比如 if __name__ == '__main__': xxx 之类的。有什么方便的删掉它们的方式么？

自动对拍系统的代码和使用方式在 这里。大家可以自己玩玩看，不过只要有一个人提交到 LeetCode-Feedback 就行了。
更新：警告！随意在本地机器上运行他人的代码是危险的，不建议在隔离环境外运行本系统。LC 的代码风险检测比较弱，我成功用提交恶意 AC 代码的方式把自己黑掉了...