Benchmark — 38 configurations

def calculate(expr: str) -> int:
    """
    Evaluate an arithmetic expression with +, -, *, / and non-negative integers.
    Normal precedence: * and / before + and -, left-to-right.
    Division truncates toward zero.
    """
    # Tokenize the expression: numbers and operators
    tokens = []
    i = 0
    n = len(expr)
    while i < n:
        if expr[i].isspace():
            i += 1
            continue
        if expr[i].isdigit():
            num = 0
            while i < n and expr[i].isdigit():
                num = num * 10 + int(expr[i])
                i += 1
            tokens.append(num)
        else:
            tokens.append(expr[i])
            i += 1

    # First pass: handle * and /
    stack = []
    i = 0
    while i < len(tokens):
        tok = tokens[i]
        if isinstance(tok, int):
            stack.append(tok)
        elif tok == '*' or tok == '/':
            # Pop left operand
            left = stack.pop()
            i += 1
            right = tokens[i]  # must be int
            if tok == '*':
                stack.append(left * right)
            else:
                # Integer division truncating toward zero
                if left * right < 0:
                    # Truncate toward zero: use abs and negate
                    res = -((-left) // right) if right > 0 else -(left // (-right))
                    # Simpler: use int(left / right) which truncates toward zero in Python
                    res = int(left / right)
                else:
                    res = left // right
                stack.append(res)
            i += 1
     
… (truncated)

def calculate(expr: str) -> int:
    """
    Evaluate an arithmetic expression with +, -, *, / and non-negative integers.
    Normal precedence: * and / before + and -, left-to-right.
    Division truncates toward zero.
    """
    # Tokenize the expression: numbers and operators
    tokens = []
    i = 0
    n = len(expr)
    while i < n:
        if expr[i].isspace():
            i += 1
            continue
        if expr[i].isdigit():
            num = 0
            while i < n and expr[i].isdigit():
                num = num * 10 + int(expr[i])
                i += 1
            tokens.append(num)
        else:
            tokens.append(expr[i])
            i += 1

    # First pass: handle * and /
    stack = []
    i = 0
    while i < len(tokens):
        tok = tokens[i]
        if isinstance(tok, int):
            stack.append(tok)
        elif tok == '*' or tok == '/':
            # Pop left operand
            left = stack.pop()
            i += 1
            right = tokens[i]  # must be int
            if tok == '*':
                stack.append(left * right)
            else:
                # Integer division truncating toward zero
                if left * right < 0:
                    # Truncate toward zero: use abs and negate
                    res = -((-left) // right) if right > 0 else -(left // (-right))
                    # Simpler: use int(left / right) which truncates toward zero in Python
                    res = int(left / right)
                else:
                    res = left // right
                stack.append(res)
            i += 1
     
… (truncated)

def calculate(expr: str) -> int:
    """
    Evaluate an arithmetic expression with +, -, *, / and non-negative integers.
    Normal precedence: * and / before + and -, left-to-right.
    Division truncates toward zero.
    """
    # Tokenize the expression: numbers and operators
    tokens = []
    i = 0
    n = len(expr)
    while i < n:
        if expr[i].isspace():
            i += 1
            continue
        if expr[i].isdigit():
            num = 0
            while i < n and expr[i].isdigit():
                num = num * 10 + int(expr[i])
                i += 1
            tokens.append(num)
        else:
            tokens.append(expr[i])
            i += 1

    # First pass: handle * and /
    stack = []
    i = 0
    while i < len(tokens):
        tok = tokens[i]
        if isinstance(tok, int):
            stack.append(tok)
        elif tok == '*' or tok == '/':
            # Pop left operand
            left = stack.pop()
            i += 1
            right = tokens[i]  # must be int
            if tok == '*':
                stack.append(left * right)
            else:
                # Integer division truncating toward zero
                if left * right < 0:
                    # Truncate toward zero: use abs and negate
                    res = -((-left) // right) if right > 0 else -(left // (-right))
                    # Simpler: use int(left / right) which truncates toward zero in Python
                    res = int(left / right)
                else:
                    res = left // right
                stack.append(res)
            i += 1
     
… (truncated)

def calculate(expr: str) -> int:
    """
    Evaluate an arithmetic expression with +, -, *, / and non-negative integers.
    Normal precedence: * and / before + and -, left-to-right.
    Division truncates toward zero.
    """
    # Tokenize the expression: numbers and operators
    tokens = []
    i = 0
    n = len(expr)
    while i < n:
        if expr[i].isspace():
            i += 1
            continue
        if expr[i].isdigit():
            num = 0
            while i < n and expr[i].isdigit():
                num = num * 10 + int(expr[i])
                i += 1
            tokens.append(num)
        else:
            tokens.append(expr[i])
            i += 1

    # First pass: handle * and /
    stack = []
    i = 0
    while i < len(tokens):
        tok = tokens[i]
        if isinstance(tok, int):
            stack.append(tok)
        elif tok == '*' or tok == '/':
            # Pop left operand
            left = stack.pop()
            i += 1
            right = tokens[i]  # must be int
            if tok == '*':
                stack.append(left * right)
            else:
                # Integer division truncating toward zero
                if left * right < 0:
                    # Truncate toward zero: use abs and negate
                    res = -((-left) // right) if right > 0 else -(left // (-right))
                    # Simpler: use int(left / right) which truncates toward zero in Python
                    res = int(left / right)
                else:
                    res = left // right
                stack.append(res)
            i += 1
     
… (truncated)

import re
from collections import Counter
def word_freq(text: str, n: int) -> list[tuple[str, int]]:
    words = re.findall(r'\b\w+\b', text.lower())
    freq = Counter(words).most_common(n)
    return [(word, count) for word, count in sorted(freq, key=lambda x: (-x[1], x[0]))]

import re
from collections import Counter

def word_freq(text: str, n: int) -> list[tuple[str, int]]:
    # Extract words (runs of letters) and convert to lowercase
    words = re.findall(r'[a-zA-Z]+', text.lower())
    
    # Count frequency of each word
    word_counts = Counter(words)
    
    # Get n most common words, sorted by count descending then word ascending
    return word_counts.most_common(n)

import re
from collections import Counter

def word_freq(text: str, n: int) -> list[tuple[str, int]]:
    # Extract words (runs of letters) and convert to lowercase
    words = re.findall(r'[a-zA-Z]+', text.lower())
    
    # Count frequency of each word
    word_counts = Counter(words)
    
    # Get n most common words, sorted by count descending then word ascending
    return sorted(word_counts.most_common(n), key=lambda x: (-x[1], x[0]))

import re
from collections import Counter

def word_freq(text: str, n: int) -> list[tuple[str, int]]:
    """
    Returns the n most common lowercase words in text, as (word, count) tuples 
    sorted by count descending then word ascending. Words are runs of letters; 
    ignore case and punctuation.

    Args:
        text: The input string.
        n: The number of top frequent words to return.

    Returns:
        A list of (word, count) tuples.
    """
    # Convert to lowercase and find all sequences of letters (words)
    words = re.findall(r'[a-zA-Z]+', text.lower())
    
    # Count the frequency of each word
    word_counts = Counter(words)
    
    # Get all unique words and their counts as a list of tuples
    items = list(word_counts.items())
    
    # Sort the items:
    # 1. By count (descending): -count
    # 2. By word (ascending): word
    sorted_items = sorted(items, key=lambda item: (-item[1], item[0]))
    
    # Return the top n results
    return sorted_items[:n]

if __name__ == '__main__':
    # Example 1: Basic test
    text1 = "The quick brown fox jumps over the lazy dog. Fox, fox!"
    n1 = 3
    print(f"Text: '{text1}'\nTop {n1} words:")
    result1 = word_freq(text1, n1)
    print(result1)  # Expected: [('fox', 3), ('the', 2), ('quick', 1)] or similar based on tie-breaking

    # Example 2: Case and punctuation test
    text2 = "Apple banana! apple. BANANA, orange? Apple."
    n2 = 4
    print(f"\nText: '{text2}'\nTop {n2} words:")
    result2 = word_freq(text2, n2)
    # Counts: apple: 3, banana: 1, orange: 1. Wait, banana appears twice if we
… (truncated)

def group_anagrams(words: list[str]) -> list[list[str]]:
    anagrams = {}
    for word in words:
        sorted_word = "".join(sorted(word))
        if sorted_word not in anagrams:
            anagrams[sorted_word] = [word]
        else:
            anagrams[sorted_word].append(word)
    return [sorted(group) for group in anagrams.values()]

def group_anagrams(words: list[str]) -> list[list[str]]:
    anagrams = {}
    for word in words:
        sorted_word = "".join(sorted(word))
        if sorted_word not in anagrams:
            anagrams[sorted_word] = [word]
        else:
            anagrams[sorted_word].append(word)
    return [sorted(group) for group in anagrams.values()]

def group_anagrams(words: list[str]) -> list[list[str]]:
    from collections import defaultdict
    
    anagram_groups = defaultdict(list)
    
    for word in words:
        sorted_word = ''.join(sorted(word))
        anagram_groups[sorted_word].append(word)
    
    result = [group for group in sorted(anagram_groups.values(), key=lambda x: min(x))]
    
    return result

def group_anagrams(words: list[str]) -> list[list[str]]:
    from collections import defaultdict
    
    anagram_groups = defaultdict(list)
    
    for word in words:
        sorted_word = ''.join(sorted(word))
        anagram_groups[sorted_word].append(word)
    
    result = [group for group in sorted(anagram_groups.values(), key=lambda x: min(x))]
    
    return result

def spiral(matrix: list[list[int]]) -> list[int]:
    """Return the elements of *matrix* in clockwise spiral order."""
    if not matrix or not matrix[0]:
        return []

    res: list[int] = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        # Traverse the top row from left to right.
        for col in range(left, right + 1):
            res.append(matrix[top][col])
        top += 1

        # Traverse the rightmost column from top to bottom.
        for row in range(top, bottom + 1):
            res.append(matrix[row][right])
        right -= 1

        if top <= bottom:
            # Traverse the bottom row from right to left.
            for col in range(right, left - 1, -1):
                res.append(matrix[bottom][col])
            bottom -= 1

        if left <= right:

def spiral(matrix: list[list[int]]) -> list[int]:
    """Return the elements of *matrix* in clockwise spiral order."""
    if not matrix or not matrix[0]:
        return []

    res: list[int] = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1

    while top <= bottom and left <= right:
        # Traverse the top row from left to right.
        for col in range(left, right + 1):
            res.append(matrix[top][col])
        top += 1

        # Traverse the rightmost column from top to bottom.
        for row in range(top, bottom + 1):
            res.append(matrix[row][right])
        right -= 1

        if top <= bottom:
            # Traverse the bottom row from right to left.
            for col in range(right, left - 1, -1):
                res.append(matrix[bottom][col])
            bottom -= 1

        if left <= right:

def spiral(matrix: list[list[int]]) -> list[int]:
    result = []
    while matrix:
        # Top row
        result += matrix.pop(0)
        if len(matrix) == 0: break
        # Right column
        for col in reversed(matrix[0]):
            result.append(col)
        if len(matrix) == 0: break
        matrix = [row[-1::-1] for row in matrix]
        # Bottom row (reversed due to previous pop and append operations)
        result += matrix.pop(0)[::-1]
        if len(matrix) == 0: break
        # Left column (reversed again because of the way we're popping rows from left side after reversing them once before appending top row in reversed order, so now they need another reversal to get correct direction for bottom-left to be rightmost)
        matrix = [row[1:] for row in matrix]
        if len(matrix) == 0: break
        result += [matrix[-1][0]]
    return result

def spiral(matrix: list[list[int]]) -> list[int]:
    result = []
    while matrix:
        # Top row
        result += matrix.pop(0)
        if not matrix: break
        # Right column
        for col in reversed(matrix[0]):
            result.append(col)
        if not matrix: break
        matrix = [row[-1::-1] for row in matrix]
        # Bottom row (reversed due to previous pop and reverse steps)
        result += matrix.pop(0)[::-1]
        if not matrix: break
        # Left column (reversed again because of the way we're popping rows from bottom up after reversing each row initially when removing right columns)
        for col in reversed(matrix[0]):
            result.append(col)
    return result

def to_roman(n: int) -> str:
    if not (1 <= n <= 3999):
        raise ValueError("Input must be between 1 and 3999")
    
    roman_numerals = [
        ("M", 1000), 
        ("CM", 900), 
        ("D", 500), 
        ("CD", 400), 
        ("C", 100), 
        ("XC", 90), 
        ("L", 50), 
        ("XL", 40), 
        ("X", 10), 
        ("IX", 9), 
        ("V", 5), 
        ("IV", 4)
    ]
    
    result = []
    for symbol, value in roman_numerals:
        while n >= value:
            result.append(symbol)
            n -= value
    return ''.join(result)

def to_roman(n: int) -> str:
    if not (1 <= n <= 3999):
        raise ValueError("Input must be between 1 and 3999")
    
    roman_numerals = [
        ("M", 1000), 
        ("CM", 900), 
        ("D", 500), 
        ("CD", 400), 
        ("C", 100), 
        ("XC", 90), 
        ("L", 50), 
        ("XL", 40), 
        ("X", 10), 
        ("IX", 9), 
        ("V", 5), 
        ("IV", 4)
    ]
    
    result = []
    for symbol, value in roman_numerals:
        while n >= value:
            result.append(symbol)
            n -= value
    return ''.join(result)

import bisect

def lis_length(nums: list[int]) -> int:
    """
    Returns the length of the longest strictly increasing subsequence (LIS) 
    of the given list of numbers.
    """
    if not nums:
        return 0

    # tails[i] stores the smallest tail of all increasing subsequences 
    # with length i+1. This array will always be sorted.
    tails = []

    for num in nums:
        # Find the index 'i' where 'num' can replace an element 
        # to potentially form a shorter or equal-length subsequence 
        # ending with a smaller tail, but here we are looking for 
        # the smallest element in tails that is >= num.
        # bisect_left returns an insertion point which comes before (to the left of) 
        # any existing entries of 'num'. Since we need strictly increasing, 
        # if tails[i] == num, we don't want to replace it because it doesn't help 
        # us find a *strictly* longer sequence ending with a smaller tail.
        
        # We are looking for the smallest element in 'tails' that is >= num.
        # If we find such an element at index 'i', replacing it with 'num' 
        # maintains the property of tails[i] being the smallest tail for length i+1, 
        # and since num <= tails[i], this replacement is valid or beneficial.
        
        # For LIS, we want to find the first element in 'tails' that is >= num.
        # If all elements are < num, then num extends the longest sequence found so far.
        # bisect_left finds the insertion point for 'num' to maintain sorted order.
        i = bisect.bisect_left(tails, num)

       
… (truncated)

import bisect

def lis_length(nums: list[int]) -> int:
    """
    Returns the length of the longest strictly increasing subsequence (LIS) 
    of the given list of numbers.
    """
    if not nums:
        return 0

    # tails[i] stores the smallest tail of all increasing subsequences 
    # with length i+1. This array will always be sorted.
    tails = []

    for num in nums:
        # Find the index 'i' where 'num' can replace an element 
        # to potentially form a shorter or equal-length subsequence 
        # ending with a smaller tail, but here we are looking for 
        # the smallest element in tails that is >= num.
        # bisect_left returns an insertion point which comes before (to the left of) 
        # any existing entries of 'num'. Since we need strictly increasing, 
        # if tails[i] == num, we don't want to replace it because it doesn't help 
        # us find a *strictly* longer sequence ending with a smaller tail.
        
        # We are looking for the smallest element in 'tails' that is >= num.
        # If we find such an element at index 'i', replacing it with 'num' 
        # maintains the property of tails[i] being the smallest tail for length i+1, 
        # and since num <= tails[i], this replacement is valid or beneficial.
        
        # For LIS, we want to find the first element in 'tails' that is >= num.
        # If all elements are < num, then num extends the longest sequence found so far.
        # bisect_left finds the insertion point for 'num' to maintain sorted order.
        i = bisect.bisect_left(tails, num)

       
… (truncated)

def lis_length(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp[-1]

def lis_length(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return dp[-1]

def compare_versions(a: str, b: str) -> int:
    def to_list(s):
        return [int(x.lstrip('0')) for x in s.split('.')]
    
    list_a = to_list(a)
    list_b = to_list(b)
    
    max_len = max(len(list_a), len(list_b))
    padded_a = list_a + [0] * (max_len - len(list_a))
    padded_b = list_b + [0] * (max_len - len(list_b))
    
    for i in range(max_len):
        if padded_a[i] < padded_b[i]:
            return -1
        elif padded_a[i] > padded_b[i]:
            return 1
    
    return 0

def compare_versions(a: str, b: str) -> int:
    def to_list(s):
        return [int(x.lstrip('0')) for x in s.split('.')]
    
    list_a = to_list(a)
    list_b = to_list(b)
    
    max_len = max(len(list_a), len(list_b))
    padded_a = list_a + [0] * (max_len - len(list_a))
    padded_b = list_b + [0] * (max_len - len(list_b))
    
    for i in range(max_len):
        if padded_a[i] < padded_b[i]:
            return -1
        elif padded_a[i] > padded_b[i]:
            return 1
    
    return 0

def compare_versions(a: str, b: str) -> int:
    a = a.replace('.', '')
    b = b.replace('.', '')
    
    # Convert both to integers with leading zeros ignored
    a = int(a, 10)
    b = int(b, 10)
    
    # Compare as integers
    return a - b

def compare_versions(a: str, b: str) -> int:
    a = a.replace('.', '')
    b = b.replace('.', '')
    
    # Convert both to integers with leading zeros ignored
    a = int(a, 10)
    b = int(b, 10)
    
    # Compare as integers
    return a - b

import heapq
from collections import defaultdict

def topo_sort(n: int, edges: list[list[int]]) -> list[int]:
    """
    Computes a topological ordering of nodes 0..n-1 given directed edges.
    If multiple orderings are valid, returns the lexicographically smallest one.
    Returns an empty list if a cycle exists.

    Args:
        n: The number of nodes (0 to n-1).
        edges: A list of edges, where each edge [a, b] means a must come before b.

    Returns:
        A list representing the lexicographically smallest topological ordering, 
        or an empty list if a cycle is detected.
    """
    adj = defaultdict(list)
    in_degree = [0] * n

    for u, v in edges:
        # Edge from u to v (u -> v)
        adj[u].append(v)
        in_degree[v] += 1

    # Min-heap to store nodes with an in-degree of 0. 
    # Using a min-heap ensures that we always pick the smallest available node,
    # guaranteeing the lexicographically smallest result.
    min_heap = []
    for i in range(n):
        if in_degree[i] == 0:
            heapq.heappush(min_heap, i)

    topological_order = []
    nodes_processed = 0

    while min_heap:
        # Get the smallest available node (lexicographically smallest choice)
        u = heapq.heappop(min_heap)
        topological_order.append(u)
        nodes_processed += 1

        # Process neighbors of u
        # Sorting neighbors before adding them to the heap is not strictly necessary 
        # for correctness here because the heap handles the selection, but it's good practice.
        for v in adj[u]:
            in_degree[v] -= 1
  
… (truncated)

import heapq
from collections import defaultdict

def topo_sort(n: int, edges: list[list[int]]) -> list[int]:
    """
    Computes a topological ordering of nodes 0..n-1 given directed edges.
    If multiple orderings are valid, returns the lexicographically smallest one.
    Returns an empty list if a cycle exists.

    Args:
        n: The number of nodes (0 to n-1).
        edges: A list of edges, where each edge [a, b] means a must come before b.

    Returns:
        A list representing the lexicographically smallest topological ordering, 
        or an empty list if a cycle is detected.
    """
    adj = defaultdict(list)
    in_degree = [0] * n

    for u, v in edges:
        # Edge from u to v (u -> v)
        adj[u].append(v)
        in_degree[v] += 1

    # Min-heap to store nodes with an in-degree of 0. 
    # Using a min-heap ensures that we always pick the smallest available node,
    # guaranteeing the lexicographically smallest result.
    min_heap = []
    for i in range(n):
        if in_degree[i] == 0:
            heapq.heappush(min_heap, i)

    topological_order = []
    nodes_processed = 0

    while min_heap:
        # Get the smallest available node (lexicographically smallest choice)
        u = heapq.heappop(min_heap)
        topological_order.append(u)
        nodes_processed += 1

        # Process neighbors of u
        # Sorting neighbors before adding them to the heap is not strictly necessary 
        # for correctness here because the heap handles the selection, but it's good practice.
        for v in adj[u]:
            in_degree[v] -= 1
  
… (truncated)

def topo_sort(n: int, edges: list[list[int]]) -> list[int]:
    # Build adjacency list
    adj = [[] for _ in range(n)]
    in_degree = [0] * n

    # Build adjacency list and in-degree list
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1

    # Use a priority queue (min-heap) to find a topological order
    import heapq

    # Create a priority queue with nodes with in-degree 0
    heap = []
    for i in range(n):
        if in_degree[i] == 0:
            heapq.heappush(heap, i)

    # Initialize result list
    result = []

    # Use a visited set to avoid cycles
    visited = set()

    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        for v in adj[u]:
            if v not in visited:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    heapq.heappush(heap, v)
                visited.add(v)

    return result if len(result) == n else []

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    visited = [False] * n
    stack = []

    # Create the adjacency list representation of the graph.
    for edge in edges:
        a, b = edge[0], edge[1]
        graph[a].append(b)

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        stack.append(node)

    # Perform DFS on each unvisited node.
    for i in range(n):
        if not visited[i]:
            dfs(i)

    order = stack[::-1]  # Reverse the stack to get the topological ordering.

    # Check if there is a cycle by checking if all nodes were visited.
    for i in range(n):
        if not visited[i]:
            return []  # Cycle exists, so we cannot produce a valid ordering.

    return order

```python code
def flatten(nested: list) -> list:
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result
```

```python code
def flatten(nested: list) -> list:
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result
```

def flatten(nested: list) -> list:
    result = []
    stack = []
    for item in nested:
        if isinstance(item, list):
            stack.extend(flatten(item))
        else:
            result.append(item)
    return result

def flatten(nested: list) -> list:
    result = []
    stack = []
    for item in nested:
        if isinstance(item, list):
            stack.extend(flatten(item))
        else:
            result.append(item)
    return result

from collections import OrderedDict

def lru(capacity: int, ops: list) -> list:
    """
    Simulate an LRU cache.

    Parameters
    ----------
    capacity : int
        Maximum number of items the cache can hold.
    ops : list
        A sequence of operations. Each operation is a list where the first element
        is either 'put' or 'get'. For 'put' the format is ['put', key, value];
        for 'get' it is ['get', key].

    Returns
    -------
    list
        Results of all 'get' operations in order; -1 denotes a cache miss.
    """
    if capacity <= 0:
        # Cache cannot store anything; every get is a miss and puts are ignored.
        return [-1 for op in ops if op[0] == 'get']

    cache = OrderedDict()          # key -> value, ordered by recent use (most recent at end)
    results = []

    for op in ops:
        if not op:                     # safety guard
            continue

        typ = op[0].lower()
        if typ == 'put':
            _, key, val = op
            if key in cache:
                # Update value and mark as most recently used.
                cache.move_to_end(key)
                cache[key] = val
            else:
                # Evict least-recently-used item if needed.
                if len(cache) >= capacity:
                    cache.popitem

from collections import OrderedDict

def lru(capacity: int, ops: list) -> list:
    """
    Simulate an LRU cache.

    Parameters
    ----------
    capacity : int
        Maximum number of items the cache can hold.
    ops : list
        A sequence of operations. Each operation is a list where the first element
        is either 'put' or 'get'. For 'put' the format is ['put', key, value];
        for 'get' it is ['get', key].

    Returns
    -------
    list
        Results of all 'get' operations in order; -1 denotes a cache miss.
    """
    if capacity <= 0:
        # Cache cannot store anything; every get is a miss and puts are ignored.
        return [-1 for op in ops if op[0] == 'get']

    cache = OrderedDict()          # key -> value, ordered by recent use (most recent at end)
    results = []

    for op in ops:
        if not op:                     # safety guard
            continue

        typ = op[0].lower()
        if typ == 'put':
            _, key, val = op
            if key in cache:
                # Update value and mark as most recently used.
                cache.move_to_end(key)
                cache[key] = val
            else:
                # Evict least-recently-used item if needed.
                if len(cache) >= capacity:
                    cache.popitem

def lru(capacity: int, ops: list) -> list:
    from collections import deque

    cache = deque()
    result = []

    for op in ops:
        if op == 'put':
            key, value = op[1], op[2]
            if len(cache) < capacity:
                cache.append((key, value))
                result.append(1)
            else:
                # Key exists
                result.append(1)
                cache.popleft()
                cache.append((key, value))
        else:  # op == 'get'
            key = op[1]
            if key in cache:
                result.append(-1)
                result.append(1)
            else:
                result.append(-1)
                cache.append((key, value))

    return result

def lru(capacity: int, ops: list) -> list:
    from collections import deque

    cache = deque()
    result = []

    for op in ops:
        if op == 'put':
            key, value = op[1], op[2]
            if len(cache) < capacity:
                cache.append((key, value))
                result.append(1)
            else:
                # Key exists
                result.append(1)
                cache.popleft()
                cache.append((key, value))
        elif op == 'get':
            key = op[1]
            if key in cache:
                result.append(-1)
                result.append(1)
            else:
                result.append(-1)
                result.append(1)

    return result

def edit_distance(a: str, b: str) -> int:
    m = len(a)
    n = len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j],      # Deletion
                               dp[i][j - 1],      # Insertion
                               dp[i - 1][j - 1])  # Substitution
    return dp[m][n]

def edit_distance(a: str, b: str) -> int:
    m = len(a)
    n = len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j],      # Deletion
                               dp[i][j - 1],      # Insertion
                               dp[i - 1][j - 1])   # Substitution
    return dp[m][n]

def edit_distance(a: str, b: str) -> int:
    # Base case: if one string is empty, the other is the distance
    if a == b:
        return 0
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)
    
    # If one is empty, the other is the distance
    if len(a) == 1:
        return edit_distance(a[0], b) + 1
    if len(b) == 1:
        return edit_distance(a, b[0]) + 1
    
    # Recursive case
    return min(
        edit_distance(a[:i], b[:i]) + 1,
        edit_distance(a[:i], b[i:]) + 1,
        edit_distance(a[i:], b[:i]) + 1,
        edit_distance(a[i:], b[i:]) + 1
    )

def edit_distance(a: str, b: str) -> int:
    # Base case: if one string is empty, the other is the distance
    if a == b:
        return 0
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)
    
    # If one is empty, the other is the distance
    if len(a) == 1 and len(b) == 1:
        return 1
    elif len(a) == 1:
        return len(b) - 1
    elif len(b) == 1:
        return len(a) - 1
    
    # Recursive case
    return 1 + min(edit_distance(a[1:], b[1:]) + 1, edit_distance(a[1:], b) + 1, edit_distance(a, b[1:]))

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    # Sort intervals by their start values
    intervals.sort(key=lambda x: x[0])
    
    result = []
    for start, end in intervals:
        if not result or result[-1][1] < end:
            result.append([start, end])
        else:
            # Merge overlapping intervals
            result[-1] = [min(result[-1][0], start), max(result[-1][1], end)]
    
    return result

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    # Sort intervals by their start values
    intervals.sort(key=lambda x: x[0])
    
    result = []
    for start, end in intervals:
        if not result or result[-1][1] < end:
            result.append([start, end])
        else:
            # Merge overlapping intervals
            result[-1] = [min(result[-1][0], start), max(result[-1][1], end)]
    
    return result

 def merge_intervals(intervals):
    # Sort the intervals by their start time
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    
    merged_intervals = []
    current_interval = None
    
    for interval in sorted_intervals:
        if not merged_intervals or merged_intervals[-1][1] < interval[0]:
            # If the current interval is empty, add the new interval to it.
            merged_intervals.append(interval)
            current_interval = interval
        else:
            # If there's an overlap between the current and the new intervals, merge them.
            if current_interval[1] < interval[1]:
                current_interval[1] = interval[1]
    
    return merged_intervals  

 def merge_intervals(intervals):
    # Sort the intervals by their start time
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    
    merged_intervals = []
    current_interval = None
    
    for interval in sorted_intervals:
        if not merged_intervals or merged_intervals[-1][1] < interval[0]:
            # If the current interval is empty, add the new interval to it.
            merged_intervals.append(interval)
            current_interval = interval
        else:
            # If there's an overlap between the current and new intervals, merge them together.
            if current_interval[1] < interval[1]:
                current_interval[1] = interval[1]
    
    return merged_intervals  

def two_sum(nums: list[int], target: int) -> list[int]:
    indices = []
    for i, num in enumerate(nums):
        if (target - num) in nums[i:] and nums[i] != nums[i - 1]:
            indices.append(i)
            indices.append(i + 1)
    return indices

def two_sum(nums: list[int], target: int) -> list[int]:
    indices = []
    for i, num in enumerate(nums):
        if (target - num) in nums[i:] and nums[i] != nums[i - 1]:
            indices.append(i)
            indices.append(i + 1)
    return indices

 def two_sum(nums: list[int], target: int) -> list[int]:
    num_indices = {}
    for i, num in enumerate(nums):
        if target - num in num_indices:
            return [num_indices[target - num], i]
        num_indices[num] = i
    return [] 

 def two_sum(nums: list[int], target: int) -> list[int]:
    num_indices = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        
        if complement not in num_indices:
            num_indices[num] = i
        else:
            return [num_indices[complement], i]
    
    raise ValueError("No solution found") 

def rle(s: str) -> str:
    result = []
    i = 0
    while i < len(s):
        char = s[i]
        count = 1
        while i + count < len(s) and s[i + count] == char:
            count += 1
            i += count
        result.append(char + str(count))
    return ''.join(result)

def rle(s: str) -> str:
    result = []
    i = 0
    while i < len(s):
        char = s[i]
        count = 1
        while i + count < len(s) and s[i + count] == char:
            count += 1
            i += count
        result.append(f"{char}{count}")
    return "\n".join(result)

def rle(s):
    encoded_str = ""
    count = 1
    
    for i in range(len(s)):
        if (i < len(s) - 1 and s[i] == s[i+1]) or i == len(s) - 1:
            count += 1
            continue
        
        encoded_str += s[i] + str(count)
        count = 1
    
    return encoded_str

def rle(s):
    encoded_str = ""
    count = 1
    
    for i in range(len(s)):
        if (i < len(s) - 1 and s[i] == s[i+1]) or (count == 1):
            count += 1
        else:
            encoded_str += s[i] + str(count)
            count = 1
            
    return encoded_str

def simplify_path(path: str) -> str:
    # Split the path into parts
    parts = path.split('/')
    
    # Initialize the canonical path
    canonical_path = []
    
    # Process each part
    for part in parts:
        if part == '.':
            canonical_path.append('/')
        elif part == '..':
            if canonical_path:
                canonical_path.pop()
        else:
            canonical_path.append(part)
    
    # If there's a trailing slash, remove it (except for the root)
    if len(canonical_path) > 0:
        canonical_path[-1] = '/' if len(canonical_path) == 1 else ''
    
    return ''.join(canonical_path)

def simplify_path(path: str) -> str:
    # Split the path into parts
    parts = path.split('/')
    
    # Process each part
    i = 0
    while i < len(parts):
        part = parts[i]
        if part == '.' or part == '..':
            # Handle the '.' and '..' cases
            if i == len(parts) - 1:
                return '/'  # Only return '/' if it's the root
            else:
                i += 1
        else:
            # Handle the other parts
            i += 1
    
    # Join the parts with '/' and return
    return '/'.join(parts)

 def simplify_path(path):
    stack = []
    for token in path.split("/"):
        if token == "..":
            if stack:
                stack.pop()
        elif token != "." and token != "":
            stack.append(token)
    return "/" + "/".join(stack)  

 def simplify_path(path):
    stack = []
    for token in path.split("/"):
        if token == "..":
            if stack:
                stack.pop()
        elif token != "." and token != "":
            stack.append(token)
    return "/" + "/".join(stack)  

def word_break(s: str, words: list[str]) -> bool:
    # Check if the words list is empty
    if not words:
        return True
    
    # Check if the words list has at least one word
    if len(words) == 0:
        return False
    
    # Check if the words list has at least one word
    if len(words) == 1:
        return s in words
    
    # Try to break the string into words from the list
    for word in words:
        if s == word:
            return True
        if s.startswith(word):
            return word_break(s[len(word):], words)
    
    return False

def word_break(s: str, words: list[str]) -> bool:
    # Check if the words list is empty
    if not words:
        return True
    
    # Check if the words list has at least one word
    if len(words) == 0:
        return False
    
    # Check if the words list has at least one word
    if len(words) == 1:
        return s in words
    
    # Try to break the string into words from the list
    for word in words:
        if s == word:
            return True
        if s == word + s[1:]:
            return True
    
    return False

 def word_break(s, words):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    
    return dp[-1]  

 def word_break(s, words):
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    
    return dp[-1]  

```python code
def binary_search(items: list[int], target: int) -> int:
    left, right = 0, len(items) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
```

```python code
def binary_search(items: list[int], target: int) -> int:
    left, right = 0, len(items) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
```

 def binary_search(items: list[int], target: int) -> int:
    left = 0
    right = len(items) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  

 def binary_search(items: list[int], target: int) -> int:
    left = 0
    right = len(items) - 1

    while left <= right:
        mid = (left + right) // 2
        
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  

def is_balanced(s: str) -> bool:
    stack = []
    i = 0
    while i < len(s):
        if s[i] in '([{':
            stack.append(s[i])
            i += 1
        elif s[i] in ')]}':
            if not stack:
                return False
            top = stack.pop()
            if s[i] == ')' and top == '(':
                continue
            elif s[i] == ']' and top == '[':
                continue
            elif s[i] == '}' and top == '{':
                continue
            else:
                return False
        else:
            i += 1
    return True

def is_balanced(s: str) -> bool:
    stack = []
    i = 0
    while i < len(s):
        if s[i] in '([{':
            stack.append(s[i])
            i += 1
        elif s[i] in ')]}':
            if not stack:
                return False
            top = stack.pop()
            if (s[i] == ')' and top == '(') or (s[i] == ']' and top == '[') or (s[i] == '}' and top == '{'):
                continue
            else:
                return False
        else:
            i += 1
    return True

 def is_balanced(s):
    stack = []
    brackets = {'(': ')', '[': ']', '{': '}'}
    
    for char in s:
        if char in brackets:
            stack.append(char)
        elif char in brackets.values():
            if not stack or brackets[stack[-1]] != char:
                return False
            stack.pop()
    
    return len(stack) == 0

The function iterates through the string character by character, pushing opening brackets onto a stack and checking for matching closing brackets when encountered. If a closing bracket is found without a corresponding opening bracket on top of the stack or if there are unmatched brackets left on the stack after iteration, it returns False; otherwise, it returns True. 

 def is_balanced(s):
    stack = []
    brackets = {")": "(", "]": "[", "}": "{"}
    for char in s:
        if char in brackets.values():
            stack.append(char)
        elif char in brackets:
            if not stack or stack[-1] != brackets[char]:
                return False
            stack.pop()
    return len(stack) == 0

run_unit_tests(tests_is_balanced)