使用 Zsh 脚本进行对拍

笔者在写《数据结构》课程的编程作业时，遇到了一件令人恼火的事。

题目是构造哈夫曼树，这并不难，问题在于，总共 5 个测试点，有 4 个 AC 了，可还是有一个 WA！

看来出题人构造了一个非常坑的测试数据，而笔者又很难快速找出这样一组能让我的程序出错的数据。

这时，要是有一个自动化生成数据并进行验算的工具该多好啊！

诶嘿，还真有这样的工具，对拍就是干这个的！

对拍

对拍是指运行两个目的相同的程序，并比较它们输出结果的自动化过程。完整的对拍需要下面四个程序。

• 实验程序：这就是各位大神各显神通、用尽了各种奇技淫巧写出来的最终提交的程序，但不知为什么总有个别测试点无法通过，因此我们需要修复它。
• 对照程序：这个一般是写法十分简单、或许非常暴力、可能容易超时，但是绝对不会出错的程序。如果不想自己写的话，也可以到网上扒一份下来，或是贿赂已经 AC 的同学让他把他的程序交给你。不过，我们当然不关心源代码是怎么写的，我们只关心它给出的结果。
• 数据发生器：这是一个能够源源不断地产生符合题目要求的数据的程序，通常大量使用了随机数发生器。不用多说，这个程序的输出格式一定是需要满足题目的输入格式的。
• 对拍脚本：这个脚本循环调用数据发生器和两个程序，然后自动比较输出结果。只要它开始运行，测试数据就能不断产生，直到出现一组能让我们的程序出错的数据。

数据发生器脚本

为了写脚本，我们需要先学习 Zsh 语法。当然，只学我们需要的部分也行。或者，你也可以用你熟悉的语言写数据发生器，再去修改对拍脚本的对应部分就可以了。

#!/bin/zsh
n=$(($RANDOM % 1024))
printf "%d\n" n
for i ({1..$n})
	printf "%d " $RANDOM
printf "\n"

第一行的 Shebang 指定用 Zsh 执行脚本，这样你就可以直接用文件名运行脚本，无需显式地指定解释器。

第二行使用了随机数发生器。$RANDOM 的取值范围是 $[0,32768)$，为了加速迭代，我们可以限制 n 的大小。$(()) 是求值运算。赋值语句的等号两边不能有空格。

第三行 printf 使用方式基本与 C 语言一致，只是去掉了括号和逗号，改用空格代替。

第四行 for 循环 n 次，$ 表示取变量的值，.. 表示连续取值。

对拍脚本

在执行这个脚本前，别忘了先编译要使用的两个程序哦！或者，你也可以将编译的命令一起添加进来。

#!/bin/zsh
# clang++ expr.cpp -o expr
# clang++ ctrl.cpp -o ctrl
cnt=0
while true; do
	./gen.sh > data.in
	./expr < data.in > data.out
	./ctrl < data.in > data.ans
	if diff data.out data.ans; then
		printf "\rTestcase #%d AC!" ++cnt
	else
		printf "\nTestcase #%d WA!\n" ++cnt
		exit 0
	fi
done

第六到八行使用了「重定向」，不用修改程序的输入输出设备即可实现文件读写。< 操作符将程序的标准输入（stdin）重定向到后面的文件，> 操作符将程序的标准输出（stdout）重定向到后面的文件中。

diff 是比较文件内容的程序。只有当两个程序输出的文件内容不一致时，将在控制台输出「WA」并退出。这时，令我们程序出错的一组测试数据就找到了，我们用它来对一开始的程序进行调试并修复问题。

写完后，为两个脚本赋予可执行权限，否则脚本无法执行。

chmod +x gen.sh cmp.sh

然后调用

./cmp.sh

一开始的问题

所以，到底是什么样的数据能让哈夫曼树崩掉呢？在我的对拍脚本高速运行一分多钟、产生了一千多组测试数据之后，终于耀眼的「WA」在屏幕上蹦了出来！怀着激动的心和颤抖的手，我点开 data.in 文件，未曾料想到它只有短短 6B：

1
129

所以到底为什么 1 个结点也要用哈夫曼树啊！