Appearance
question:from typing import List def shortest_path(n: int, m: int, grid: List[str]) -> int: Determine the shortest path for a robot from the northwest corner (0, 0) to the southeast corner (n-1, m-1) in a grid, avoiding blocked intersections. If no valid path exists, return -1. >>> shortest_path(5, 5, [ ... "OOOOO", ... "OBBBO", ... "OOOBO", ... "OBBBO", ... "OOOOO" ... ]) == 8 >>> shortest_path(3, 3, [ ... "OBO", ... "BBO", ... "OOO" ... ]) == -1 >>> shortest_path(2, 2, [ ... "OO", ... "BO" ... ]) == 2 >>> shortest_path(2, 2, [ ... "BO", ... "OO" ... ]) == -1 >>> shortest_path(2, 2, [ ... "OO", ... "OB" ... ]) == -1 >>> shortest_path(1, 1, [ ... "O", ... ]) == 0
answer:from collections import deque def shortest_path(n, m, grid): if grid[0][0] == 'B' or grid[n-1][m-1] == 'B': return -1 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] queue = deque([(0, 0, 0)]) # (row, col, distance) visited = set((0, 0)) while queue: row, col, dist = queue.popleft() if (row, col) == (n-1, m-1): return dist for dr, dc in directions: new_row, new_col = row + dr, col + dc if 0 <= new_row < n and 0 <= new_col < m and (new_row, new_col) not in visited and grid[new_row][new_col] == 'O': visited.add((new_row, new_col)) queue.append((new_row, new_col, dist + 1)) return -1
question:def min_operations_to_clean(n: int, tubes: List[int]) -> int: Returns the minimum number of operations required to clean all test tubes. >>> min_operations_to_clean(4, [1, 0, 1, 0]) # 2 >>> min_operations_to_clean(6, [1, 1, 0, 0, 1, 1]) # 2 >>> min_operations_to_clean(3, [0, 0, 0]) # 0 >>> min_operations_to_clean(5, [1, 1, 1, 1, 1]) # 1 pass def process_input(input_lines: List[str]) -> List[int]: Process the input to determine the minimum operations for each dataset. >>> process_input(["4", "1 0 1 0", "6", "1 1 0 0 1 1", "3", "0 0 0", "5", "1 1 1 1 1", "0"]) # [2, 2, 0, 1] >>> process_input(["2", "1 0", "2", "0 1", "0"]) # [1, 1] pass from typing import List def test_min_operations_to_clean(): assert min_operations_to_clean(4, [1, 0, 1, 0]) == 2 assert min_operations_to_clean(6, [1, 1, 0, 0, 1, 1]) == 2 assert min_operations_to_clean(3, [0, 0, 0]) == 0 assert min_operations_to_clean(5, [1, 1, 1, 1, 1]) == 1 def test_process_input(): input_data = [ "4", "1 0 1 0", "6", "1 1 0 0 1 1", "3", "0 0 0", "5", "1 1 1 1 1", "0" ] expected_output = [2, 2, 0, 1] assert process_input(input_data) == expected_output input_data = [ "2", "1 0", "2", "0 1", "0" ] expected_output = [1, 1] assert process_input(input_data) == expected_output input_data = [ "7", "1 1 1 0 1 1 1", "4", "0 1 1 0", "0" ] expected_output = [2, 1] assert process_input(input_data) == expected_output def test_edge_cases(): assert min_operations_to_clean(1, [1]) == 1 assert min_operations_to_clean(1, [0]) == 0 assert min_operations_to_clean(2, [1, 1]) == 1 assert min_operations_to_clean(2, [0, 0]) == 0
answer:def min_operations_to_clean(n, tubes): Returns the minimum number of operations required to clean all test tubes. operations = 0 i = 0 while i < n: if tubes[i] == 1: operations += 1 # Invert the array from the current element to the end of the contiguous segment of contaminated tubes while i < n and tubes[i] == 1: tubes[i] = 0 if tubes[i] == 1 else 1 i += 1 while i < n and tubes[i] == 0: i += 1 return operations def process_input(input_lines): Process the input to determine the minimum operations for each dataset. results = [] i = 0 while i < len(input_lines): n = int(input_lines[i]) if n == 0: break tubes = list(map(int, input_lines[i + 1].split())) results.append(min_operations_to_clean(n, tubes)) i += 2 return results
question:def longest_recurring_substring(s: str) -> str: Returns the longest recurring substring in the given string s. Returns -1 if there is no recurring substring. >>> longest_recurring_substring("banana") == "ana" >>> longest_recurring_substring("abcdef") == -1 >>> longest_recurring_substring("abababab") == "ababab" >>> longest_recurring_substring("xxyyzzyxx") == "xx" >>> longest_recurring_substring("mississippi") == "issi"
answer:def longest_recurring_substring(s): Returns the longest recurring substring in the given string s. Returns -1 if there is no recurring substring. n = len(s) max_len = 0 result = "" for length in range(1, n): substrings = {} for i in range(n - length + 1): substr = s[i:i + length] if substr in substrings: substrings[substr] += 1 else: substrings[substr] = 1 for substr, count in substrings.items(): if count > 1 and len(substr) > max_len: max_len = len(substr) result = substr return result if max_len > 0 else -1
question:from typing import List def can_rearrange_to_no_identical_consecutive(s: str) -> bool: Determine if it is possible to rearrange the characters in s to form a string that has no consecutive identical characters. >>> can_rearrange_to_no_identical_consecutive("aabbccc") True >>> can_rearrange_to_no_identical_consecutive("aaab") False def solve(inputs: List[str]) -> List[str]: For each input string, determine if it is possible to rearrange it to have no consecutive identical characters. >>> solve(["aabbccc", "aaab", "abc", "aabb"]) ["Possible", "Not Possible", "Possible", "Possible"] if __name__ == "__main__": t = int(input()) inputs = [input().strip() for _ in range(t)] results = solve(inputs) for result in results: print(result) # Unit test def test_can_rearrange_to_no_identical_consecutive(): assert can_rearrange_to_no_identical_consecutive("aabbccc") == True assert can_rearrange_to_no_identical_consecutive("aaab") == False assert can_rearrange_to_no_identical_consecutive("abc") == True assert can_rearrange_to_no_identical_consecutive("aabb") == True assert can_rearrange_to_no_identical_consecutive("aaaaa") == False assert can_rearrange_to_no_identical_consecutive("a") == True def test_solve(): inputs = ["aabbccc", "aaab", "abc", "aabb"] expected = ["Possible", "Not Possible", "Possible", "Possible"] assert solve(inputs) == expected inputs = ["aaaa", "abcde", "abcdabc", "aaabbccc"] expected = ["Not Possible", "Possible", "Possible", "Possible"] assert solve(inputs) == expected
answer:from collections import Counter def can_rearrange_to_no_identical_consecutive(s): counts = Counter(s) max_freq = max(counts.values()) return (max_freq - 1) <= (len(s) - max_freq) def solve(inputs): results = [] for s in inputs: if can_rearrange_to_no_identical_consecutive(s): results.append("Possible") else: results.append("Not Possible") return results