methods/lcb/function_code_sample/edge_func_22.py

import random
import string

def generate_string(length):
    """Generate a random string of lowercase letters"""
    return ''.join(random.choice(string.ascii_lowercase) for _ in range(length))

def generate_repetitive_string(length, pattern_length=3):
    """Generate a string with repetitive patterns"""
    pattern = ''.join(random.choice(string.ascii_lowercase) for _ in range(pattern_length))
    return (pattern * (length // pattern_length + 1))[:length]

def generate_palindromic_string(length):
    """Generate a palindromic string"""
    half = length // 2
    first_half = ''.join(random.choice(string.ascii_lowercase) for _ in range(half))
    if length % 2 == 0:
        return first_half + first_half[::-1]
    else:
        middle = random.choice(string.ascii_lowercase)
        return first_half + middle + first_half[::-1]

def generate_operations(initial_length, num_ops, query_ratio=0.4):
    """Generate a mix of operations"""
    operations = []
    current_length = initial_length
    
    for _ in range(num_ops):
        op_type = random.choices(['Q', 'R', 'I'], weights=[query_ratio, (1-query_ratio)/2, (1-query_ratio)/2])[0]
        
        if op_type == 'Q':
            x = random.randint(1, current_length)
            y = random.randint(1, current_length)
            operations.append(f"Q {x} {y}")
        elif op_type == 'R':
            x = random.randint(1, current_length)
            d = random.choice(string.ascii_lowercase)
            operations.append(f"R {x} {d}")
        else:  # Insert
            x = random.randint(0, current_length)
            d = random.choice(string.ascii_lowercase)
            operations.append(f"I {x} {d}")
            current_length += 1
    
    return operations

def generate_adversarial_queries(length):
    """Generate queries that might be computationally expensive"""
    operations = []
    
    # Queries at the beginning and end
    operations.append(f"Q 1 {length}")
    operations.append(f"Q 1 {length//2}")
    
    # Queries with close positions
    for i in range(min(5, length-1)):
        operations.append(f"Q {i+1} {i+2}")
    
    # Random queries
    for _ in range(10):
        x = random.randint(1, length)
        y = random.randint(1, length)
        operations.append(f"Q {x} {y}")
    
    return operations

def construct_inputs():
    inputs = []
    
    # Test case 1: Small string with many operations
    initial_str = "abcabc"
    ops = generate_operations(len(initial_str), 50, query_ratio=0.6)
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    # Test case 2: Repetitive pattern string
    initial_str = generate_repetitive_string(100, 3)
    ops = generate_operations(len(initial_str), 1000, query_ratio=0.3)
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    # Test case 3: Palindromic string
    initial_str = generate_palindromic_string(500)
    ops = generate_adversarial_queries(len(initial_str))
    ops.extend(generate_operations(len(initial_str), 500, query_ratio=0.5))
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    # Test case 4: Maximum constraints
    initial_str = generate_string(100000)
    ops = []
    # Add many insertions to test dynamic length changes
    for i in range(0, min(50000, 100000), 2000):
        ops.append(f"I {i} {random.choice(string.ascii_lowercase)}")
    # Add queries after insertions
    for _ in range(10000):
        x = random.randint(1, 100000)
        y = random.randint(1, 100000)
        ops.append(f"Q {x} {y}")
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    # Test case 5: All same character
    initial_str = "a" * 1000
    ops = generate_operations(len(initial_str), 5000, query_ratio=0.8)
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    # Test case 6: Alternating pattern
    initial_str = "ab" * 5000
    ops = []
    # Many modifications to break the pattern
    for i in range(1, len(initial_str), 100):
        ops.append(f"R {i} {random.choice('cdefgh')}")
    # Then many queries
    for _ in range(1000):
        x = random.randint(1, len(initial_str))
        y = random.randint(1, len(initial_str))
        ops.append(f"Q {x} {y}")
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    # Test case 7: Edge case with single character
    initial_str = "x"
    ops = [
        "Q 1 1",
        "I 1 y",
        "Q 1 2",
        "R 2 x",
        "Q 1 2",
        "I 0 z",
        "Q 1 3"
    ]
    test_case = f"{initial_str}\n{len(ops)}\n" + "\n".join(ops)
    inputs.append(test_case)
    
    return inputs