---

name: test-case-generator description: 为算法正确性验证生成全面的测试用例，包括边界情况、压力测试和反例。支持随机生成、基于约束的生成以及暴力破解的预言机比较。 allowed-tools: Bash, Read, Write, Grep, Glob metadata: author: babysitter-sdk version: “1.0” category: algorithms-optimization skill-id: SK-ALGO-008 priority: high

测试用例生成器

一项专门用于为算法验证生成全面测试用例的技能，包括边界情况、压力测试、随机输入以及通过暴力破解预言机比较来寻找反例。

目的

为以下场景生成测试用例：

• 针对问题约束的正确性验证
• 边界情况的识别与测试
• 使用大型输入进行压力测试
• 为错误解决方案寻找反例
• 用于验证的暴力破解预言机生成

能力

核心功能

1. 随机测试生成

   • 在指定约束内生成输入
   • 支持多种数据类型（数组、树、图、字符串）
   • 可配置的分布（均匀分布、正态分布、偏向边界的分布）
   • 使用种子值生成可复现的测试

2. 边界情况生成

   • 最小/最大约束值
   • 空输入、单个元素
   • 排序/逆序序列
   • 所有相同元素、交替模式
   • 边界条件

3. 压力测试

   • 最大约束输入
   • 时间限制验证
   • 内存限制测试
   • 性能回归检测

4. 反例寻找

   • 与暴力破解预言机进行比较
   • 在输入大小上进行二分搜索以寻找最小失败用例
   • 自动测试用例最小化
   • 差异报告

5. 数据结构生成

   • 数组：随机、排序、接近排序、包含重复项
   • 树：二叉树、二叉搜索树、平衡树、倾斜树
   • 图：稀疏图、稠密图、有向无环图、带环图
   • 字符串：随机、回文、模式

集成选项

命令行工具

QuickTest CLI - 全面的竞赛编程测试工具：

npm install -g quicktest-cli

# 与暴力破解方案比较
qt cmp --solution solution.cpp --brute brute.cpp --gen gen.cpp

# 压力测试以检查超时
qt stress --solution solution.cpp --gen gen.cpp --time-limit 1000

压力测试脚本 (7oSkaaa)：

git clone https://github.com/7oSkaaa/Stress_Testing
# 提供：gen_array()、gen_tree()、gen_simple_graph()

testlib.h (Codeforces 标准)

#include "testlib.h"

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>("n", rnd.next(1, 100000));

    println(n);
    println(rnd.any(range(n), [](int) {
        return rnd.next(-1000000000, 1000000000);
    }));

    return 0;
}

使用方法

生成随机测试用例

# 生成数组测试用例
test-case-generator array \
  --min-size 1 \
  --max-size 100000 \
  --min-value -1e9 \
  --max-value 1e9 \
  --count 100

# 生成图测试用例
test-case-generator graph \
  --nodes 1000 \
  --edges 5000 \
  --type undirected \
  --connected true

生成边界情况

# 自动边界情况生成
test-case-generator edge-cases --problem "two-sum" --constraints constraints.json

# 输出包括：
# - 空数组 []
# - 单个元素 [x]
# - 两个元素（匹配/不匹配）
# - 所有相同元素
# - 最大数组大小
# - 最大/最小值

压力测试

# 将解决方案与暴力破解方案比较
test-case-generator stress \
  --solution solution.cpp \
  --brute brute.cpp \
  --iterations 1000 \
  --timeout 5000

# 失败时的输出：
# 在第 47 次迭代发现反例：
# 输入：[3, 5, 2, 8, 1]
# 目标：6
# 预期：[0, 2]
# 实际：[1, 2]

寻找最小反例

# 二分搜索最小的失败输入
test-case-generator minimize \
  --solution solution.cpp \
  --brute brute.cpp \
  --failing-input large_input.txt

# 输出：
# 原始输入大小：10000
# 最小失败输入大小：4
# 最小输入：[3, 1, 2, 4]

输出模式

{
  "testCases": [
    {
      "id": "test_001",
      "category": "edge_case",
      "description": "空数组",
      "input": {
        "arr": [],
        "target": 5
      },
      "expectedOutput": [],
      "tags": ["empty", "boundary"]
    },
    {
      "id": "test_002",
      "category": "random",
      "description": "随机数组，n=1000",
      "input": {
        "arr": [...],
        "target": 12345
      },
      "expectedOutput": null,
      "oracle": "brute_force"
    }
  ],
  "metadata": {
    "generatedAt": "ISO8601",
    "seed": 42,
    "constraints": {
      "n": [1, 100000],
      "values": [-1e9, 1e9]
    }
  }
}

生成器模板

数组生成器

def generate_array(n_range=(1, 100000), value_range=(-1e9, 1e9), seed=None):
    """在约束内生成随机数组。"""
    if seed:
        random.seed(seed)
    n = random.randint(*n_range)
    return [random.randint(*value_range) for _ in range(n)]

def generate_edge_cases():
    """为数组问题生成常见的边界情况。"""
    return [
        [],                          # 空
        [0],                         # 单个元素
        [1, 1],                      # 两个相同
        [1, 2],                      # 两个不同
        list(range(100)),            # 升序排序
        list(range(100, 0, -1)),     # 降序排序
        [5] * 100,                   # 全部相同
        [10**9] * 1000,              # 最大值
        [-10**9] * 1000,             # 最小值
    ]

树生成器

def generate_tree(n, tree_type='random'):
    """生成具有 n 个节点的树。"""
    if tree_type == 'random':
        return random_tree(n)
    elif tree_type == 'line':
        return [(i, i+1) for i in range(1, n)]
    elif tree_type == 'star':
        return [(1, i) for i in range(2, n+1)]
    elif tree_type == 'binary':
        return [(i, 2*i), (i, 2*i+1) for i in range(1, n//2+1)]

图生成器

def generate_graph(n, m, graph_type='undirected', connected=True):
    """生成具有 n 个节点和 m 条边的图。"""
    edges = set()

    # 用生成树确保连通性
    if connected:
        nodes = list(range(1, n+1))
        random.shuffle(nodes)
        for i in range(1, n):
            u = nodes[random.randint(0, i-1)]
            v = nodes[i]
            edges.add((min(u,v), max(u,v)))

    # 添加剩余的边
    while len(edges) < m:
        u, v = random.randint(1, n), random.randint(1, n)
        if u != v and (min(u,v), max(u,v)) not in edges:
            edges.add((min(u,v), max(u,v)))

    return list(edges)

压力测试工作流

1. 编写 solution.cpp（你的解决方案）
2. 编写 brute.cpp（朴素但正确的方案）
3. 编写 gen.cpp（测试生成器）
4. 运行压力测试循环：
   - 用 gen.cpp 生成输入
   - 运行两个解决方案
   - 比较输出
   - 如果不同，报告反例
5. 如果发现反例：
   - 最小化输入
   - 调试解决方案
   - 重复

边界情况类别

类别	示例
空	[], “”, null
单个	[x], “a”, 单节点
边界	n=1, n=最大值, 值=最小/最大值
重复项	全部相同，大量重复项
排序	升序，降序，接近排序
极值	INT_MAX, INT_MIN, 0
特殊	回文，平衡，倾斜

与流程的集成

此技能增强：

• correctness-proof-testing - 验证算法正确性
• algorithm-implementation - 开发过程中的测试
• leetcode-problem-solving - 额外的测试覆盖
• upsolving - 调试失败的解决方案

参考资料

• QuickTest CLI
• Stress Testing (7oSkaaa)
• testlib.h
• Competitive Programming Stress Testing
• Test Case Generator

错误处理

错误	原因	解决方案
CONSTRAINT_VIOLATION	生成的值超出范围	检查约束边界
TIMEOUT	生成耗时过长	减小规模或简化
MEMORY_EXCEEDED	内存中测试用例过多	流式写入文件
ORACLE_FAILED	暴力破解方案崩溃	调试暴力破解方案

最佳实践

1. 始终先测试边界情况 - 空、单个、边界
2. 使用可复现的种子 - 用于调试失败的用例
3. 从小开始，逐步扩大 - n=10, n=100, n=1000, …
4. 验证暴力破解方案 - 确保预言机绝对正确
5. 最小化反例 - 较小的输入更容易调试
6. 保存失败的输入 - 保留回归测试套件