Systematic Debugging Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

def analyze_test_failures(test_cases: list, my_function, expected_function=None):
    """
    Systematic analysis of test case failures.
    
    Args:
        test_cases: List of (input, expected_output) tuples
        my_function: Your implementation to test
        expected_function: Optional correct implementation for comparison
    """
    failures = []
    
    for i, (input_data, expected) in enumerate(test_cases):
        try:
            # Handle different input formats
            if isinstance(input_data, tuple):
                actual = my_function(*input_data)
            else:
                actual = my_function(input_data)
        except Exception as e:
            failures.append({
                'test_index': i,
                'input': input_data,
                'error': str(e),
                'category': 'CRASH'
            })
            continue
        
        if actual != expected:
            # Calculate difference metrics
            diff_info = {
                'test_index': i,
                'input': input_data,
                'expected': expected,
                'actual': actual,
                'category': 'WRONG_ANSWER'
            }
            
            # Analyze the difference
            if isinstance(expected, (int, float)) and isinstance(actual, (int, float)):
                diff = actual - expected
                diff_info['numeric_diff'] = diff
                
                if diff == 1 or diff == -1:
                    diff_info['likely_cause'] = 'OFF_BY_ONE'
                elif actual < 0 and expected > 0:
                    diff_info['likely_cause'] = 'INTEGER_OVERFLOW_OR_SIGN_ERROR'
                elif abs(diff) == expected:
                    diff_info['likely_cause'] = 'DOUBLED_OR_MISSED_COUNTING'
            
            failures.append(diff_info)
    
    # Summarize patterns
    print(f"
=== Test Failure Analysis ===")
    print(f"Total tests: {len(test_cases)}")
    print(f"Failures: {len(failures)}")
    
    if failures:
        # Group by category
        categories = {}
        for f in failures:
            cat = f.get('likely_cause', f['category'])
            categories[cat] = categories.get(cat, 0) + 1
        
        print(f"
Failure categories:")
        for cat, count in sorted(categories.items(), key=lambda x: -x[1]):
            print(f"  {cat}: {count}")
        
        print(f"
First failure details:")
        print(f"  Input: {failures[0]['input']}")
        print(f"  Expected: {failures[0].get('expected', 'N/A')}")
        print(f"  Actual: {failures[0].get('actual', 'CRASH')}")
        if 'likely_cause' in failures[0]:
            print(f"  Likely cause: {failures[0]['likely_cause']}")
    
    return failures
 
 
# Example usage
def my_buggy_sum(arr):
    # Bug: doesn't handle empty array
    total = 0
    for i in range(len(arr)):
        total += arr[i]
    return total
 
test_cases = [
    ([1, 2, 3], 6),
    ([0], 0),
    ([], 0),  # This might cause issues
    ([-1, -2], -3),
    ([1000000000] * 100, 100000000000),  # Overflow test
]
 
# analyze_test_failures(test_cases, my_buggy_sum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

def minimize_failing_input(test_input, test_func, expected_func):
    """
    Automatically find minimal input that still causes failure.
    Works for list/array inputs.
    """
    
    def fails(inp):
        try:
            actual = test_func(inp)
            expected = expected_func(inp)
            return actual != expected
        except:
            return True  # Crashes count as failure
    
    if not fails(test_input):
        print("Input doesn't fail!")
        return test_input
    
    current = list(test_input)
    
    # Phase 1: Binary search on size
    left, right = 1, len(current)
    while left < right:
        mid = (left + right) // 2
        if fails(current[:mid]):
            right = mid
        else:
            left = mid + 1
    
    current = current[:left]
    print(f"Minimized to length {len(current)}: {current}")
    
    # Phase 2: Try removing each element
    changed = True
    while changed:
        changed = False
        for i in range(len(current)):
            candidate = current[:i] + current[i+1:]
            if fails(candidate):
                current = candidate
                changed = True
                print(f"Removed element at {i}, now: {current}")
                break
    
    print(f"
Minimal failing input: {current}")
    return current
 
 
# Example: Finding minimal case for off-by-one bug
def binary_search_buggy(arr, target):
    left, right = 0, len(arr)  # Bug: should be len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
 
def binary_search_correct(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
 
# Find minimal failing input
failing_input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 10  # Last element - triggers the bug
 
# The minimization would find that [10] with target=10 is the minimal failing case
# Because with right = len(arr) = 1, the while loop doesn't execute
# and we return -1 for the last element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

import time
 
 
 
def comprehensive_verification(
    fixed_function,
    original_failing_cases: list,
    known_good_cases: list,
    edge_cases: list,
    stress_test_generator=None,
    reference_function=None
):
    """
    Comprehensive verification suite for fixed functions.
    """
    print("=== COMPREHENSIVE FIX VERIFICATION ===
")
    
    all_passed = True
    
    # 1. Original Failing Cases
    print("1. Original Failing Cases:")
    for inp, expected in original_failing_cases:
        actual = fixed_function(inp) if not isinstance(inp, tuple) else fixed_function(*inp)
        status = "✓ PASS" if actual == expected else "✗ FAIL"
        print(f"   {inp} -> {actual} (expected {expected}) {status}")
        if actual != expected:
            all_passed = False
    
    print()
    
    # 2. Regression Testing (Previously Passing Cases)
    print("2. Regression Test (previously passing cases):")
    regression_passed = 0
    for inp, expected in known_good_cases:
        actual = fixed_function(inp) if not isinstance(inp, tuple) else fixed_function(*inp)
        if actual == expected:
            regression_passed += 1
        else:
            print(f"   ✗ REGRESSION: {inp} -> {actual} (expected {expected})")
            all_passed = False
    print(f"   {regression_passed}/{len(known_good_cases)} regression tests passed")
    
    print()
    
    # 3. Edge Cases
    print("3. Edge Cases:")
    for inp, expected in edge_cases:
        try:
            actual = fixed_function(inp) if not isinstance(inp, tuple) else fixed_function(*inp)
            status = "✓ PASS" if actual == expected else "✗ FAIL"
            print(f"   {inp} -> {actual} (expected {expected}) {status}")
            if actual != expected:
                all_passed = False
        except Exception as e:
            print(f"   {inp} -> CRASH: {e}")
            all_passed = False
    
    print()
    
    # 4. Stress Test (if generator provided)
    if stress_test_generator and reference_function:
        print("4. Stress Test (random inputs):")
        stress_passed = 0
        stress_count = 100
        
        start = time.time()
        for i in range(stress_count):
            inp = stress_test_generator()
            expected = reference_function(inp) if not isinstance(inp, tuple) else reference_function(*inp)
            actual = fixed_function(inp) if not isinstance(inp, tuple) else fixed_function(*inp)
            if actual == expected:
                stress_passed += 1
            else:
                print(f"   ✗ FAILED on input {inp}")
                all_passed = False
                break
        elapsed = time.time() - start
        
        print(f"   {stress_passed}/{stress_count} random tests passed in {elapsed:.2f}s")
    
    print()
    
    # Summary
    print("=== VERIFICATION SUMMARY ===")
    if all_passed:
        print("✓ ALL TESTS PASSED - Fix verified!")
    else:
        print("✗ SOME TESTS FAILED - Fix incomplete or introduced regression")
    
    return all_passed
 
 
# Example usage:
def binary_search_fixed(arr, target):
    if not arr:
        return -1
    left, right = 0, len(arr) - 1  # FIXED: was len(arr)
    while left <= right:  # FIXED: was left < right
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
 
# comprehensive_verification(
#     binary_search_fixed,
#     original_failing_cases=[([1, 2, 3], 3, 2)],  # Last element
#     known_good_cases=[([1, 2, 3], 1, 0), ([1, 2, 3], 2, 1)],
#     edge_cases=[([], 1, -1), ([5], 5, 0), ([5], 3, -1)],
# )