First 11 rows of py
| uuidstring | contentstring | content_formatstring | raw_contentstring | taskstring | analysisstring | solutionstring | teststring | full_contentstring | full_content_formatstring |
|---|---|---|---|---|---|---|---|---|---|
| 02ef0d3e-968f-4246-9def-862554b44b2c | Write a Python function `draw_star_square(n)` that takes a positive integer `n` and returns a list of strings representing a square pattern of concentric star borders. The pattern has side length `4*n - 3`. For `i` from 1 to `n`, the `i`-th border (where `i=1` is the outermost) i… | markdown | import sys input = lambda: sys.stdin.readline().rstrip() n = int(input()) s=n*4-3 arr=[[" "]*s for _ in range(s)] for i in range(1,n+1): start=2*i-2 end=s-(2*i-2)-1 for k in range(start,end+1): for l in range(start,end+1): if k==start or k==end … |
| Write a Python function `draw_star_square(n)` that takes a positive integer `n` and returns a list of strings representing a square pattern of concentric star borders. The pattern has side length `4*n - 3`. For `i` from 1 to `n`, the `i`-th border (where `i=1` is the outermost) i… |
| The approach is to directly simulate the pattern. First, compute side length `s = 4*n - 3`. Create a 2D list (s rows, s columns) initialized with spaces. For each border index `i` from 1 to `n` inclusive, compute the start index `start = 2*i - 2` and end index `end = s - start - … |
| def draw_star_square(n): """ Generate a square pattern of concentric star borders. Args: n (int): A positive integer determining the number of borders. Returns: list[str]: A list of strings, each of length 4*n-3, representing t… |
| assert draw_star_square(1) == ["*"] assert draw_star_square(2) == [ "*****", "* *", "* * *", "* *", "*****" ] assert draw_star_square(3) == [ "*********", "* *", "* ***** *", "* * * *", "* * * * *", "* * * *", "* *****… |
| Write a Python function `draw_star_square(n)` that takes a positive integer `n` and returns a list of strings representing a square pattern of concentric star borders. The pattern has side length `4*n - 3`. For `i` from 1 to `n`, the `i`-th border (where `i=1` is the outermost) i… |
| standard order |
| 5b6f55bd-4374-4c08-9fbb-71faf4753932 | Write a Python function that parses a simple grammar definition in Backus-Naur Form (BNF) and returns a list of production rules, where each rule is represented as a tuple of (left-hand side name, list of right-hand side alternatives). The grammar input uses the following format:… | markdown | from typing import Optional, Iterator, Tuple, List from parso.python.tokenize import tokenize from parso.utils import parse_version_string from parso.python.token import PythonTokenTypes class NFAArc: def __init__(self, next_: 'NFAState', nonterminal_or_string: Optional[str… | Write a Python function that parses a simple grammar definition in Backus-Naur Form (BNF) and returns a list of production rules, where each rule is represented as a tuple of (left-hand side name, list of right-hand side alternatives). The grammar input uses the following format:… | The solution requires a tokenizer and a recursive descent parser. First, we tokenize the input by splitting on whitespace while preserving quoted strings as single tokens. We then process line by line to extract rules. For each non-empty, non-comment line, we find the colon to se… | def parse_bnf_grammar(grammar: str) -> list: """Parse a simple BNF grammar into a list of production rules. Each rule is a tuple (name, alternatives) where alternatives is a list of lists of tokens. Tokens are either literal strings (including quotes) or non-term… | # Test basic rule assert parse_bnf_grammar("statement: 'if' expression") == [('statement', [["'if'", 'expression']])] # Test multiple alternatives assert parse_bnf_grammar("expr: term | term '+' term") == [('expr', [['term'], ['term', "'+'", 'term']])] # Test blank lines and co… | Write a Python function that parses a simple grammar definition in Backus-Naur Form (BNF) and returns a list of production rules, where each rule is represented as a tuple of (left-hand side name, list of right-hand side alternatives). The grammar input uses the following format:… | test-first order |
| c82f1190-f2bc-4982-811a-6206335d7000 | Implement a function `simulate_queue(operations)` that takes a list of operations as input. Each operation is a tuple where the first element is a string (`"push"` or `"pop"` or `"front"`). For `"push"`, the second element is an integer value to enqueue. For `"pop"` and `"front"`… | no fence | class Node: def __init__(self,value = None): self.val = value self.next = None class queue: def __init__(self): self.head = None self.tail = None self.length = 0 def insert(self,data): if self.length == 0: … | Implement a function `simulate_queue(operations)` that takes a list of operations as input. Each operation is a tuple where the first element is a string (`"push"` or `"pop"` or `"front"`). For `"push"`, the second element is an integer value to enqueue. For `"pop"` and `"front"`… | The solution is straightforward: instantiate a queue object using the provided `queue` class. Iterate through each operation tuple. If the operation is `"push"`, call `insert(value)` on the queue. If it is `"pop"`, call `pop()` and append the returned value to the results list (w… | class Node: def __init__(self, value=None): self.val = value self.next = None class Queue: def __init__(self): self.head = None self.tail = None self.length = 0 def insert(self, data): if self.length == 0: … | assert simulate_queue([]) == [] assert simulate_queue([("push", 1), ("pop",)]) == [1] assert simulate_queue([("pop",)]) == [None] assert simulate_queue([("front",)]) == [None] assert simulate_queue([("push", 1), ("push", 2), ("push", 3), ("pop",), ("pop",), ("pop",)]) == [1, 2, 3… | # Implement a function `simulate_queue(operations)` that takes a list of operations as input. Each operation is a tuple where the first element is a string (`"push"` or `"pop"` or `"front"`). For `"push"`, the second element is an integer value to enqueue. For `"pop"` and `"front… | commented standard order |
| 276d5cb2-9e9c-4074-8765-a4461e44b986 | Implement a function `radix255_encoding(d, q=2**255 - 19)` that takes an integer `d` and returns a base-2^26 representation string of `d` modulo the prime `q = 2^255 - 19`, following the algorithm in the snippet. The function should reduce the input modulo `q`, then normalize the… | no fence | q = 2**255 - 19 def expmod(b,e,m): if e == 0: return 1 t = expmod(b,e/2,m)**2 % m if e & 1: t = (t*b) % m return t def inv(x): return expmod(x,q-2,q) def radix255(x): x = x % q if x + x > q: x -= q x = [x,0,0,0,0,0,0,0,0,0] bits = [26,25,26,25,26,25,26,25,26,… | Implement a function `radix255_encoding(d, q=2**255 - 19)` that takes an integer `d` and returns a base-2^26 representation string of `d` modulo the prime `q = 2^255 - 19`, following the algorithm in the snippet. The function should reduce the input modulo `q`, then normalize the… | The core algorithm involves three parts: modular exponentiation, modular inverse, and radix-2^26 encoding. 1. **Modular exponentiation**: Use the `expmod` function from the snippet, but in Python 3, the division `e/2` must be replaced with `e//2` (integer division) to avoid flo… | def expmod(b, e, m): """Return b^e mod m using exponentiation by squaring.""" if e == 0: return 1 t = expmod(b, e // 2, m) ** 2 % m if e & 1: t = (t * b) % m return t def mod_inverse(x, q): """Return modular inverse of x modulo prime q usi… | # Test modular inverse: inverse of 1 is 1, inverse of 2 mod 5 is 3 assert expmod(2, 3, 5) == 3 assert mod_inverse(1, 5) == 1 assert mod_inverse(2, 5) == 3 # Test reduction and encoding for small known values q = 2**255 - 19 # For x=0, encoding should be all zeros assert radix255… | """ Implement a function `radix255_encoding(d, q=2**255 - 19)` that takes an integer `d` and returns a base-2^26 representation string of `d` modulo the prime `q = 2^255 - 19`, following the algorithm in the snippet. The function should reduce the input modulo `q`, then normalize… | solution-first order |
| 5528cd71-2b03-4835-9a00-ea311457b89e | """ Write a Python function `calculate_ponds(terrain)` that takes a string representing a cross-section of terrain, where `'\\'` (backslash) represents a downward slope, `'/'` (forward slash) represents an upward slope, and `'_'` represents flat ground. Rain falls uniformly, and … | code comment | import sys,itertools from collections import deque input = sys.stdin.readline def _main(): IN = input() area = 0 all_area_stack = deque([]) local_spot_stack = deque([]) for i, op in enumerate(IN): if(op == '\\'): all_area_stack.append(i) … | Write a Python function `calculate_ponds(terrain)` that takes a string representing a cross-section of terrain, where `'\\'` (backslash) represents a downward slope, `'/'` (forward slash) represents an upward slope, and `'_'` represents flat ground. Rain falls uniformly, and wate… | The solution uses a stack-based approach similar to the classic "trapping rain water" problem but generalized to handle slope characters. We process the terrain left to right, maintaining two stacks: 1. A stack of indices where we've seen a `'\\'` (downward slope). 2. A stack of … | def calculate_ponds(terrain): """ Calculate the total area of water trapped in terrain and the area of each individual pond. Args: terrain (str): A string containing characters '\\', '/', and '_'. Newlines are ignored. Returns: tuple: (total_area… | assert calculate_ponds("") == (0, []) assert calculate_ponds("___") == (0, []) assert calculate_ponds("\\\\//") == (2, [2]) assert calculate_ponds("\\\\///") == (3, [3]) assert calculate_ponds("\\/") == (1, [1]) assert calculate_ponds("\\_/") == (1, [1]) assert calculate_ponds("\… | Write a Python function `calculate_ponds(terrain)` that takes a string representing a cross-section of terrain, where `'\\'` (backslash) represents a downward slope, `'/'` (forward slash) represents an upward slope, and `'_'` represents flat ground. Rain falls uniformly, and wate… | test-first order |
| 409fc2af-b7d1-4493-ac14-2b02a3a65b1e | Implement a pure-Python function `max_flow_value(graph, source, sink)` that computes the value of the maximum flow in a directed graph with integer or float edge capacities. The graph is represented as a dictionary mapping each node `u` to a dictionary `{v: capacity}` for each di… | markdown | """ Boykov-Kolmogorov algorithm for maximum flow problems. """ from collections import deque from operator import itemgetter import networkx as nx from networkx.algorithms.flow.utils import build_residual_network __all__ = ["boykov_kolmogorov"] @nx._dispatch( graphs={"G": … | Implement a pure-Python function `max_flow_value(graph, source, sink)` that computes the value of the maximum flow in a directed graph with integer or float edge capacities. The graph is represented as a dictionary mapping each node `u` to a dictionary `{v: capacity}` for each di… | We need to implement the Boykov-Kolmogorov max-flow algorithm independently. The core idea is to maintain two search trees: one rooted at the source (source tree) and one rooted at the sink (target tree). The algorithm repeatedly performs three stages until no augmenting path exi… | from collections import deque def max_flow_value(graph, source, sink): """ Compute the maximum flow value in a directed graph using the Boykov-Kolmogorov algorithm. The graph is represented as a dictionary: graph[u] = {v: capacity} for each directed edg… | # Test 1: Simple graph from the docstring example graph = { 'x': {'a': 3.0, 'b': 1.0}, 'a': {'c': 3.0}, 'b': {'c': 5.0, 'd': 4.0}, 'c': {'y': 2.0}, 'd': {'e': 2.0}, 'e': {'y': 3.0}, 'y': {} } assert abs(max_flow_value(graph, 'x', 'y') - 3.0) < 1e-9 # … | Implement a pure-Python function `max_flow_value(graph, source, sink)` that computes the value of the maximum flow in a directed graph with integer or float edge capacities. The graph is represented as a dictionary mapping each node `u` to a dictionary `{v: capacity}` for each di… | standard order |
| ed3a6acb-bb9c-4a2a-b54f-edb14ca1810c | """ Create a Python function named `print_patterns` that takes an integer `n` (number of rows, where `n >= 1`) as input and prints three distinct patterns to the console, each separated by a line of 12 dashes (`------------`). The first pattern is a centered pyramid of asterisks:… | code comment | n = int(input("Enter the number of rows: ")) for i in range(1, n+1): print(" "*(n-i), end= "") print("*"*(i*2-1)) # * # *** # ***** print("------------") for i in range(1, n+1): print("*"*(i)) # * # ** # *** print("------------") for i in range(1, n+1): if i =… | Create a Python function named `print_patterns` that takes an integer `n` (number of rows, where `n >= 1`) as input and prints three distinct patterns to the console, each separated by a line of 12 dashes (`------------`). The first pattern is a centered pyramid of asterisks: for… | The solution requires three separate loops, each iterating from `1` to `n` inclusive. For the pyramid, we use `print(" " * (n - i), end="")` to output the leading spaces (for `n=1`, this produces zero spaces), then `print("*" * (2*i - 1))` to output the asterisks. For the triangl… | def print_patterns(n): """Print three patterns: centered pyramid, right triangle, and hollow square. Args: n: Positive integer representing the number of rows (must be >= 1). Prints: Three patterns separated by a line of 12 dashes. """ # Pyra… | import io import sys def capture_output(n): old_stdout = sys.stdout sys.stdout = io.StringIO() print_patterns(n) output = sys.stdout.getvalue() sys.stdout = old_stdout return output # Test n=1 assert capture_output(1) == "*\n------------\n*\n------------… | """ Create a Python function named `print_patterns` that takes an integer `n` (number of rows, where `n >= 1`) as input and prints three distinct patterns to the console, each separated by a line of 12 dashes (`------------`). The first pattern is a centered pyramid of asterisks:… | solution-first order |
| 98782a76-3776-49db-a59b-258256a85588 | """ Write a Python function `count_even_digit_numbers(nums)` that takes a list of non-negative integers and returns the count of numbers in the list that have an even number of digits. For example, 12 has two digits (even), while 345 has three digits (odd). The function should ha… | code comment | # Given an array nums of integers, determine how many numbers in the array have an even number of digits. # # Example: # # Input: nums = [12, 345, 2, 6, 7896] # # Output: 2 # # Explanation: Numbers 12 and 7896 have an even number of digits. # https://leetcode.com/problems/find-nu… | Write a Python function `count_even_digit_numbers(nums)` that takes a list of non-negative integers and returns the count of numbers in the list that have an even number of digits. For example, 12 has two digits (even), while 345 has three digits (odd). The function should handle… | The core challenge is to determine the number of digits in each integer without using string conversion. The standard arithmetic approach is to repeatedly divide the number by 10 (using integer division) and count how many times this can be done until the number becomes 0. For ex… | def count_even_digit_numbers(nums): """Count how many numbers in `nums` have an even number of digits. Args: nums: A list of non-negative integers. Returns: An integer count of numbers with an even number of digits. Numbers are counted based … | assert count_even_digit_numbers([]) == 0 assert count_even_digit_numbers([0]) == 0 assert count_even_digit_numbers([1]) == 0 assert count_even_digit_numbers([12, 345, 2, 6, 7896]) == 2 assert count_even_digit_numbers([1, 22, 333, 4444]) == 2 assert count_even_digit_numbers([10000… | # Write a Python function `count_even_digit_numbers(nums)` that takes a list of non-negative integers and returns the count of numbers in the list that have an even number of digits. For example, 12 has two digits (even), while 345 has three digits (odd). The function should hand… | test-first order |
| 9423ca23-0f62-4b21-a303-634a95aa0622 | You are given a straight road of length `L` meters with `N` rest areas already built at distinct integer positions (between 0 and L). You are allowed to build at most `M` additional rest areas anywhere along the road at integer positions (not at the existing ones or at the ends).… | no fence | import sys input = sys.stdin.readline def solve(): n, m, l = map(int, input().split()) ws = [0] + sorted(list(map(int, input().split()))) ws.append(l) lo, hi = 1, l ans = int(1e4) while(lo <= hi): mid = (lo+hi)//2 cnt = 0 for i i… | You are given a straight road of length `L` meters with `N` rest areas already built at distinct integer positions (between 0 and L). You are allowed to build at most `M` additional rest areas anywhere along the road at integer positions (not at the existing ones or at the ends).… | The problem is a classic binary search on the answer. If we fix a candidate maximum gap `x`, we can check whether it is possible to achieve that maximum gap by adding at most `m` rest areas. For each existing gap between consecutive points (including 0 and L), the number of new r… | def minimize_max_gap(n, m, l, positions): """ Return the minimum possible maximum distance between consecutive rest areas. Args: n: Number of existing rest areas. m: Maximum number of new rest areas we can build. l: Total length of the road (0… | # Basic cases assert minimize_max_gap(0, 0, 10, []) == 10 assert minimize_max_gap(0, 5, 10, []) == 2 # can place 5 points to make gaps of 2 assert minimize_max_gap(1, 0, 10, [5]) == 5 # gaps 5 and 5 assert minimize_max_gap(1, 1, 10, [5]) == 5 # placing one doesn't help if gap … | # You are given a straight road of length `L` meters with `N` rest areas already built at distinct integer positions (between 0 and L). You are allowed to build at most `M` additional rest areas anywhere along the road at integer positions (not at the existing ones or at the ends… | commented standard order |
| 0bb8836a-24cf-418e-ae55-0872198f60b1 | """ Given an array of N integers and a positive integer K, write a function that computes the total number of inversions (pairs i<j where a[i] > a[j]) in the array formed by concatenating K copies of the original array. Since the result can be very large, return the answer modulo… | code comment | N,K=map(int,input().split()) a=list(map(int,input().split())) tentou1=0 for i in range(N): for j in range(i+1,N): if(a[i]>a[j]): tentou1+=1 stentou=0 for i in range(N): for j in range(N): if(a[i]>a[j]): stentou+=1 answer=int(tentou1*K + stentou*K*(K-1)/2… | Given an array of N integers and a positive integer K, write a function that computes the total number of inversions (pairs i<j where a[i] > a[j]) in the array formed by concatenating K copies of the original array. Since the result can be very large, return the answer modulo 1,0… | The brute force approach would be to construct the repeated array and count inversions in O((N*K)^2), which is infeasible for large K. Instead, we can decompose the problem: 1. **Inversions within one copy**: Count the number of inversions inside a single copy of the array. Call… | def count_inversions_repeated(a, K): """ Count the total number of inversions in an array formed by repeating the input list `a` exactly K times, modulo 1,000,000,007. Args: a: List of integers (the original array). K: Positive integer, number of … | assert count_inversions_repeated([2, 1], 1) == 1 assert count_inversions_repeated([2, 1], 2) == 3 # [2,1,2,1] inversions: (2,1) at pos0-1, (2,1) at pos0-3, (2,1) at pos2-3 = 3 assert count_inversions_repeated([1, 2, 3], 5) == 0 assert count_inversions_repeated([3, 2, 1], 1) == 3… | Given an array of N integers and a positive integer K, write a function that computes the total number of inversions (pairs i<j where a[i] > a[j]) in the array formed by concatenating K copies of the original array. Since the result can be very large, return the answer modulo 1,0… | test-first order |
| 5d33eb59-c4be-4c35-b05b-b8fdfd32ff25 | Write a function `minimum_height_tree_roots(n, edges)` that takes the number of nodes `n` (labeled from 0 to n-1) and a list of undirected edges (each edge is a list `[u, v]` connecting nodes `u` and `v`), and returns a list of all root nodes that produce a tree of minimum height… | markdown | class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: # create one tree and then calculate height of tree from each possible node adjacency_list = {} if not edges: return [0] for node_… | Write a function `minimum_height_tree_roots(n, edges)` that takes the number of nodes `n` (labeled from 0 to n-1) and a list of undirected edges (each edge is a list `[u, v]` connecting nodes `u` and `v`), and returns a list of all root nodes that produce a tree of minimum height… | The solution must consider every possible root and compute the height of the tree when rooted at that node. Since the input is a tree (connected acyclic graph), we can build an adjacency list from the edges. For each node as a potential root, we perform a depth-first traversal to… | from typing import List def minimum_height_tree_roots(n: int, edges: List[List[int]]) -> List[int]: """Return all roots that minimize the height of the tree formed by edges. Args: n: Number of nodes labeled 0 to n-1. edges: List of undirected edges, each… | assert minimum_height_tree_roots(1, []) == [0] assert minimum_height_tree_roots(2, [[0, 1]]) == [0, 1] assert minimum_height_tree_roots(3, [[0, 1], [1, 2]]) == [1] assert minimum_height_tree_roots(4, [[0, 1], [1, 2], [2, 3]]) == [1, 2] assert minimum_height_tree_roots(4, [[0, 1],… | """ Write a function `minimum_height_tree_roots(n, edges)` that takes the number of nodes `n` (labeled from 0 to n-1) and a list of undirected edges (each edge is a list `[u, v]` connecting nodes `u` and `v`), and returns a list of all root nodes that produce a tree of minimum he… | solution-first order |
