实验二：给解法装上对拍器

到这一课为止，你手上开始有不止一种解法了。同一道题，暴力版能手写出来，二分版也能手写出来；归并排序与内置 sorted 是两条路；递归与循环加栈是两条路。

于是「我这版对不对」这个问题变得难回答了：样例过了不代表对，因为样例只有几组；看着像对也不代表对，第 14 课那三种错法跑起来一行报错都没有，只在某些数据上悄悄给出错的答案。

靠感觉判断对错，在这条路上走不远。这次要造的是把感觉换成证据的东西：把暴力解当参照，随机造数据自动比对，一不一致就把那组数据打印出来。

这份脚本就是配套项目「AI 刷题助手」里「自动验证候选解」那一环的原型。

任务、断言与判分脚本在 lab/0015-lab-02-verify-by-brute-force/；五个任务都做完、判分全过之后，再对照 lab/solutions/。

这次要做出什么

两样产物，都在 lab 目录里。文件名与函数名是判分接口，别改；函数体里怎么写随你。

给好的东西（别改）：候选解 buggy.py（里面藏着第 14 课那三种错法中的一种）、判分脚本 run_tests.py、公共工具 tools.py。

留白版原样跑是不通过的：stress.py 里的函数还空着，stress 交回 None（看起来像「一次都没抓到」，其实是根本没比对）。那是起点，不是 bug。

对拍的四个部件

对拍（stress test）由四件事组成，缺一件都跑不起来：

参照解为什么用暴力版而不是另一份优化版？因为暴力版简单到能一眼看出对不对。它的价值不在快，在于可信：用它当尺子，量出来的差异才有意义。

比对循环的返回值要设计好——不能只回一句「有问题」，要把那一组数据一起交回来：

def stress(candidate, reference, gen, trials, seed=None):
    if seed is not None:
        random.seed(seed)
    for t in range(1, trials + 1):
        a, x = gen()
        got = candidate(a, x)
        want = reference(a, x)
        if got != want:
            return t, a, x, got, want
    return None

t 是第几次抓到的。seed 用来固定随机序列——这一点后面单独讲。

一个真跑出来的例子

参照解与候选解这样写：

def brute_find(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1

def cand_find(a, x):
    lo = 0
    hi = len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

cand_find 就是第 14 课那个「闭区间配上 while lo < hi，漏掉最后一个元素」的错法。数据生成器给两组：

def gen_wide():
    n = random.randint(1, 8)
    a = sorted(random.sample(range(100), n))
    return a, random.randrange(100)

def gen_from_array():
    n = random.randint(1, 8)
    a = sorted(random.sample(range(100), n))
    return a, random.choice(a)

拿 gen_from_array 对拍，第 2 次就抓到了：

第 2 次抓到：a=[63, 97] x=97 候选=-1 参照=1

两个元素的数组里，97 明明在下标 1 上，候选解却交回 -1。原因回到第 14 课那句话：区间只剩一个元素时循环已经退出，那一格从没被检查过。

抓到了不等于看清了。两格的数据已经足够小，但「最小化」这一步仍然值得做——后面单独讲。

抓错快慢差四百倍

换成另外三种造数据方案，同一个候选解、同样 5000 次的预算，抓到它的速度差得很远：

最快第 1 次，最慢第 398 次——四百倍的差距。这个结果值得停一下：方案 A 看起来「最随机」，却排在中游；方案 D 明明已经包含单元素数组这种最容易出错的数据形态，却排在最慢。

原因在触发条件。这个候选解只在「答案恰好是最后剩下那个没被检查的元素」时出错。于是抓到它的快慢取决于两件事：

• x 得真的在数组里。方案 A 里 x 在 0 到 99 里随便取，而数组只有几个元素，多数时候 x 根本不在数组里——两边都交回 -1，一次也抓不到。方案 B 把 x 限定成数组里的元素，命中率立刻上去。
• 数组得有重复值，或者答案在端点。方案 C 值域只有 0 到 4，重复多，对撞的路径更容易走到「只剩一格」那一步。

方案 D 与方案 E 的对比最能说明问题。两者都包含单元素数组，写法上的差别只在 x：

def gen_boundary():
    kind = random.randrange(4)
    if kind == 0:                      # 空数组
        return [], random.randrange(100)
    if kind == 1:                      # 单元素，x 就取那个元素
        v = random.randrange(100)
        return [v], v
    if kind == 2:                      # 全相同
        v = random.randrange(5)
        return [v] * random.randint(2, 6), v
    n = random.randint(2, 6)           # 答案在两端
    a = sorted(random.sample(range(100), n))
    return a, (a[0] if random.randrange(2) == 0 else a[-1])

D 里 x 仍然宽范围随机，单元素数组必须恰好配上 x 等于那个元素才会暴露，两个条件叠起来的概率很低；E 里 kind == 1 那一支直接把 x 设成那个元素，两个条件被绑在一起造出来：

第 1 次抓到：a=[72] x=72 候选=-1 参照=0

所以 gen_boundary 的任务很明确：把空数组、单元素、全相同、答案在两端这些形态主动造出来，而不是靠随机碰。

反例最小化

抓到的那组数据往往比必要的更大。a=[63, 97]、x=97 里的第一个元素对暴露 bug 毫无贡献——真正的错在「区间只剩一格」这一步。

反例最小化（shrinking）就是反复试着把反例改小，只要它还能让两边不一致，就接受这个更小的版本：

def shrink(candidate, reference, a, x):
    cur = list(a)
    changed = True
    while changed:
        changed = False
        for i in range(len(cur)):
            smaller = cur[:i] + cur[i + 1:]
            if candidate(smaller, x) != reference(smaller, x):
                cur = smaller
                changed = True
                break
    return cur

对上面那组反例跑一遍：

原始反例: [63, 97] x = 97  候选 -1  参照 1
最小化后: [97] x = 97  候选 -1  参照 0

一步就缩到了极限：一个元素的数组，97 就是它自己，候选解却交回 -1。看到这一组，错在哪几乎不用再猜了。

最小化之后的反例还有一个用处：它可以直接抄进测试用例。第 14 课那些边界数据，其中几条正是这样来的——从对拍抓到的反例里缩出来的。

参考解也会错

对拍有一个前提容易被忽略：它比对的是两个解，不是解与真相。参照解自己写错时，对拍给出的结论会误导人。

先看一种情况：参照解用了「严格大于」，候选解用了「不小于」。

参照用「严格大于」时：第 1 次抓到 a=[2, 5, 8, 9] x=9 候选=3 参照=4

对拍报了不一致。可是该改哪一边？对拍自己不知道——它只负责报差异。这时要靠手算的小样例或标准库来裁决：这道题问的是「第一个不小于 x 的位置」，正确答案是 3，错的是参照解。

再看更麻烦的一种：两边错成同一种。

def ref_gt(a, x):
    for i in range(len(a)):
        if a[i] > x:
            return i
    return len(a)

def cand_gt(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

一个用暴力、一个用二分，写法完全不同，但两边问的都是「第一个严格大于 x 的位置」。拿去对拍：

2000 次里不一致的次数: 0 -> 全部通过

2000 次全部通过。而真正的答案要求「不小于」：

a=[1, 3, 5] x=3:  两边给 2   真实答案 1
a=[2, 5, 8, 9] x=9:  两边给 4   真实答案 3
a=[1, 1, 1] x=1:  两边给 3   真实答案 0

三组全错。对拍说没问题，实际上两边一起错。 这也正是「参考解要写得简单到一眼能看出对不对」的原因：复杂到看不出对错的参照解，对拍的全部结论都不可信。

种子与复现

对拍脚本里如果用了随机数，就必须能复现。看三行输出：

seed=1: 第 2 次抓到 a=[63, 97] x=97
seed=1: 第 2 次抓到 a=[63, 97] x=97
seed=2: 第 1 次抓到 a=[11] x=11
不设种子那一次: 第 1 次抓到 a=[21, 32, 39, 77, 85, 94] x=32

同一个 seed 连着跑两次，抓到的是同一组数据；换个种子就换一组；不设种子则每次都不同。

为什么非要固定种子？因为抓到反例之后你要做的是改代码、再跑一遍确认修好了。不固定种子的话，第二遍跑的是另一批随机数据，它可能根本不碰那个已经修好的位置——于是「改完就通过了」这件事什么都没证明。固定种子之后，同一个反例每次都重现：修之前必挂，修之后必过。

怎么算过

run_tests.py 按四层判：

退出码：四层都过是 0，还有没过的（或跳过的）是 1。

第 2 层值得解释一句：拿同一个函数同时当候选与参照，对拍必须一次都抓不到。这一层专门抓「stress 根本没在比对」这类问题——比如漏了 if got != want 那一行，或者把两个结果写反了。

怎么跑

py stress.py            # 手动跑一次，看抓到什么
py run_tests.py         # 交判分

py stress.py 直接输出抓到的反例、最小化结果与 findings.md 该写的内容，对着抄进去即可。

自查清单

• brute_find 在空数组、单元素、目标不存在这三种输入上给出的是 -1 吗？
• gen_wide 交回的 a 是升序的吗？gen_boundary 是不是真的造了空数组与单元素，而不只是换个值域？
• stress 拿同一个函数当候选与参照跑 2000 次，交回的是 None 吗？
• 同一个 seed 连着跑两次，抓到的是同一组数据吗？
• shrink 之后那组数据，跑一遍两边还是不一致吗？再试着删掉一个元素，还缩得动吗？
• findings.md 里那三样东西都写了吗？（原始反例、最小反例、出错的那一行）
• 三个任务的函数体里有没有留下的调试 print？标准输出应当只有脚本要求的那几行。
• py run_tests.py 是不是四层全过、退出码 0？

最可能卡在哪

坑一：参照解自己就写错了。 表现是：对拍报了一堆不一致，改了半天候选解还是不一致。原因是参照解写错时，对拍的两边都在错。先单独验参照解：拿三组手算过的小数据（空、一个元素、两个元素）跑它，答案对得上再拿它对拍。

坑二：只对拍一组数据就收工。 表现是：跑一次 trials=10，看到 None 就认为候选解是对的。这一课的数据摆在那儿：同一个 bug，有的方案第 1 次就中，有的要到第 398 次。次数要足够多（几千次），方案要覆盖边界形态。

坑三：没固定随机种子。 表现是：把 seed 留成 None 或者每次跑都换一个数，于是反例记不下来——写完 findings.md 再跑一遍，抓到的是另一组数据，判分第 3 层直接不过。

坑四：造了无序的数据。 表现是：对拍报了大量不一致，而那组数据本来就不合法（候选解是二分，前提是有序）。生成器里排一次序，或者用 sorted(...) 包一层。

按经验，卡住的地方通常是这几个（按出现频率排）：

卡壳顺序

按这五步来，别一上来就问：

1. 读错误信息。 判分脚本会把它跑出来的报错最后几行贴出来并指到那一行；TypeError 与 IndexError 往往直接说明是哪个函数还空着。
2. 自己跑一遍。 py stress.py 单独跑，看它到底交回了什么：交回 None 是没抓到，抛异常是函数没接上。
3. 看 FAIL 行。 每一行 FAIL 后面写了期望、实际，以及「这一层指向哪一段」。
4. 再对线索。 抓不到 → 造数据器没踩中触发条件；两次种子结果不同 → 种子没设对；缩完两边一致了 → shrink 接受条件写松了。
5. 对照参考解。 四层都过了再打开 lab/solutions/ 比一比——重点比「造数据器覆盖了哪些形态」和「stress 的返回值设计」，不是比谁的代码短。

做完之后

这份对拍器是「AI 刷题助手」里验证环节的原型。它接下来会被用在三处：第 27 课（给新解法对拍出反例）、第 30 课（交卷前的自检）、第 33 课（综合实战里自动挑出候选解里错的那一版）。

交完之后用一句话回答：这次对拍里，是哪一个数据形态让 buggy.py 暴露出来的？

• Python 官方文档 · randomseed 固定随机序列、randint 与 sample 的区间口径、choice
• Python 官方文档 · bisect裁决「参照解与候选解谁错」时的第三方依据：bisect_left 给出标准答案
• lab 说明 lab/README.md载体与环境依赖、任务表、写法边界、卡壳顺序（先读这一份）