test-case-generator

A specialized skill for generating comprehensive test cases for algorithm verification, including edge cases, stress tests, random inputs, and counter-example finding through brute force oracle comparison.

Purpose

Generate test cases for:

• Correctness verification against problem constraints
• Edge case identification and testing
• Stress testing with large inputs
• Counter-example finding for wrong solutions
• Brute force oracle generation for validation

Capabilities

Core Features

1. Random Test Generation

• Generate inputs within specified constraints
• Support for various data types (arrays, trees, graphs, strings)
• Configurable distributions (uniform, normal, edge-biased)
• Reproducible tests with seed values

1. Edge Case Generation

• Minimum/maximum constraint values
• Empty inputs, single elements
• Sorted/reverse sorted sequences
• All same elements, alternating patterns
• Boundary conditions

1. Stress Testing

• Maximum constraint inputs
• Time limit verification
• Memory limit testing
• Performance regression detection

1. Counter-Example Finding

• Compare against brute force oracle
• Binary search on input size for minimal failing case
• Automatic test case minimization
• Difference reporting

1. Data Structure Generation

• Arrays: random, sorted, nearly sorted, with duplicates
• Trees: binary trees, BSTs, balanced, skewed
• Graphs: sparse, dense, DAGs, with cycles
• Strings: random, palindromes, patterns

Integration Options

CLI Tools

QuickTest CLI - Comprehensive CP testing tool:

bash
npm install -g quicktest-cli

# Compare against brute force
qt cmp --solution solution.cpp --brute brute.cpp --gen gen.cpp

# Stress test for TLE
qt stress --solution solution.cpp --gen gen.cpp --time-limit 1000

Stress Testing Script (7oSkaaa):

bash
git clone https://github.com/7oSkaaa/Stress_Testing
# Provides: gen_array(), gen_tree(), gen_simple_graph()

testlib.h (Codeforces Standard)

cpp
#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;
}

Usage

Generate Random Test Cases

bash
# Generate array test cases
test-case-generator array \
  --min-size 1 \
  --max-size 100000 \
  --min-value -1e9 \
  --max-value 1e9 \
  --count 100

# Generate graph test cases
test-case-generator graph \
  --nodes 1000 \
  --edges 5000 \
  --type undirected \
  --connected true

Generate Edge Cases

bash
# Automatic edge case generation
test-case-generator edge-cases --problem "two-sum" --constraints constraints.json

# Output includes:
# - Empty array []
# - Single element [x]
# - Two elements (match/no-match)
# - All same elements
# - Maximum array size
# - Maximum/minimum values

Stress Testing

bash
# Compare solution against brute force
test-case-generator stress \
  --solution solution.cpp \
  --brute brute.cpp \
  --iterations 1000 \
  --timeout 5000

# Output on failure:
# Found counter-example at iteration 47:
# Input: [3, 5, 2, 8, 1]
# Target: 6
# Expected: [0, 2]
# Actual: [1, 2]

Find Minimal Counter-Example

bash
# Binary search for smallest failing input
test-case-generator minimize \
  --solution solution.cpp \
  --brute brute.cpp \
  --failing-input large_input.txt

# Output:
# Original input size: 10000
# Minimal failing input size: 4
# Minimal input: [3, 1, 2, 4]

Output Schema

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

Generator Templates

Array Generator

python
def generate_array(n_range=(1, 100000), value_range=(-1e9, 1e9), seed=None):
    """Generate random array within constraints."""
    if seed:
        random.seed(seed)
    n = random.randint(*n_range)
    return [random.randint(*value_range) for _ in range(n)]

def generate_edge_cases():
    """Generate common edge cases for array problems."""
    return [
        [],                          # Empty
        [0],                         # Single element
        [1, 1],                      # Two same
        [1, 2],                      # Two different
        list(range(100)),            # Sorted ascending
        list(range(100, 0, -1)),     # Sorted descending
        [5] * 100,                   # All same
        [10**9] * 1000,              # Max values
        [-10**9] * 1000,             # Min values
    ]

Tree Generator

python
def generate_tree(n, tree_type='random'):
    """Generate tree with n nodes."""
    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)]

Graph Generator

python
def generate_graph(n, m, graph_type='undirected', connected=True):
    """Generate graph with n nodes and m edges."""
    edges = set()

    # Ensure connectivity with spanning tree
    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)))

    # Add remaining edges
    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)

Stress Testing Workflow

1. Write solution.cpp (your solution)
2. Write brute.cpp (naive but correct)
3. Write gen.cpp (test generator)
4. Run stress test loop:
   - Generate input with gen.cpp
   - Run both solutions
   - Compare outputs
   - If different, report counter-example
5. If counter-example found:
   - Minimize input
   - Debug solution
   - Repeat

Edge Case Categories

| Category | Examples | |----------|----------| | Empty | ], "", null | | Single | x], "a", single node | | Boundary | n=1, n=max, value=min/max | | Duplicates | All same, many duplicates | | Sorted | Ascending, descending, nearly sorted | | Extremes | INT_MAX, INT_MIN, 0 | | Special | Palindrome, balanced, skewed |

Integration with Processes

This skill enhances:

• correctness-proof-testing - Verify algorithm correctness
• algorithm-implementation - Test during development
• leetcode-problem-solving - Additional test coverage
• upsolving - Debug failed solutions

References

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

Error Handling

| Error | Cause | Resolution | |-------|-------|------------| | CONSTRAINT_VIOLATION | Generated value out of range | Check constraint bounds | | TIMEOUT | Generation taking too long | Reduce size or simplify | | MEMORY_EXCEEDED | Too many test cases in memory | Stream to file | | ORACLE_FAILED | Brute force solution crashed | Debug brute force |

Best Practices

1. Always test edge cases first - Empty, single, boundary
2. Use reproducible seeds - For debugging failed cases
3. Start small, scale up - n=10, n=100, n=1000, ...
4. Verify brute force - Ensure oracle is definitely correct
5. Minimize counter-examples - Smaller inputs easier to debug
6. Save failing inputs - Keep a regression test suite