chat

🔍

question:from typing import List def shortest_path_in_grid(grids: List[List[List[int]]]) -> List[int]: Determine the length of the shortest path from the top-left corner to the bottom-right corner of each grid. Only cells with a value of 0 are traversable, and you can only move right, left, up, or down. >>> parse_input("1n3 3n0 0 1n0 1 0n0 0 0n") [[[0, 0, 1], [0, 1, 0], [0, 0, 0]]] >>> shortest_path_in_grid([[[0, 0, 1], [0, 1, 0], [0, 0, 0]]]) [4] pass def parse_input(data: str) -> List[List[List[int]]]: Parse the input data and return a list of grids. >>> parse_input("1n3 3n0 0 1n0 1 0n0 0 0n") [[[0, 0, 1], [0, 1, 0], [0, 0, 0]]] pass def main(input_data: str): grids = parse_input(input_data) results = shortest_path_in_grid(grids) for result in results: print(result)

answer:from collections import deque def shortest_path_in_grid(grids): def bfs(grid): n, m = len(grid), len(grid[0]) if grid[0][0] != 0 or grid[n-1][m-1] != 0: return -1 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] q = deque([(0, 0, 0)]) # (row, col, distance) visited = set() visited.add((0, 0)) while q: x, y, dist = q.popleft() if x == n-1 and y == m-1: return dist for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in visited and grid[nx][ny] == 0: visited.add((nx, ny)) q.append((nx, ny, dist + 1)) return -1 results = [] for grid in grids: results.append(bfs(grid)) return results def parse_input(data): lines = data.split('n') index = 0 test_cases = [] T = int(lines[index].strip()) index += 1 for _ in range(T): N, M = map(int, lines[index].strip().split()) index += 1 grid = [] for _ in range(N): grid.append(list(map(int, lines[index].strip().split()))) index += 1 test_cases.append(grid) return test_cases def main(input_data): grids = parse_input(input_data) results = shortest_path_in_grid(grids) for result in results: print(result)

question:def longest_common_palindromic_subsequence(seq1, seq2) -> int: Returns the length of the Longest Common Palindromic Subsequence (LCPS) of the given two sequences. >>> longest_common_palindromic_subsequence([1, 2, 3, 4], [3, 2, 1, 3]) == 3 >>> longest_common_palindromic_subsequence([1, 2, 3], [4, 5, 6]) == 0 >>> longest_common_palindromic_subsequence([1, 2, 3, 4, 3], [3, 4, 3, 2, 1]) == 5

answer:def lcs(X, Y): Helper function to find the length of Longest Common Subsequence (LCS) of sequences X and Y. n = len(X) m = len(Y) L = [[0] * (m + 1) for i in range(n + 1)] for i in range(n + 1): for j in range(m + 1): if i == 0 or j == 0: L[i][j] = 0 elif X[i - 1] == Y[j - 1]: L[i][j] = L[i - 1][j - 1] + 1 else: L[i][j] = max(L[i - 1][j], L[i][j - 1]) return L[n][m] def longest_common_palindromic_subsequence(seq1, seq2): Returns the length of the Longest Common Palindromic Subsequence (LCPS) of the given two sequences. seq2_reversed = seq2[::-1] return lcs(seq1, seq2_reversed)

question:from typing import List def is_prime(n: int) -> bool: Helper function to check if a number is prime. def prime_factors(n: int) -> List[int]: Helper function to get the prime factors of a number. def sum_of_digits(n: int) -> int: Helper function to sum the digits of a number. def smith_number(n: int) -> str: Return "Smith !!" if the number is a Smith number, otherwise "Not !!". >>> smith_number(22) 'Smith !!' >>> smith_number(13) 'Not !!'

answer:def is_prime(n): Helper function to check if a number is prime. if n < 2: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True def prime_factors(n): Helper function to get the prime factors of a number. i = 2 factors = [] while i * i <= n: if n % i: i += 1 else: n //= i factors.append(i) if n > 1: factors.append(n) return factors def sum_of_digits(n): Helper function to sum the digits of a number. return sum(int(digit) for digit in str(n)) def smith_number(n): Return "Smith !!" if the number is a Smith number, otherwise "Not !!". if is_prime(n): return "Not !!" prime_fact = prime_factors(n) sum_n = sum_of_digits(n) sum_factors = sum(sum_of_digits(factor) for factor in prime_fact) if sum_n == sum_factors: return "Smith !!" else: return "Not !!"

question:def can_cat_catch_mouse(n, m, k, s, t, edges): Determine if the cat can catch the mouse in an undirected unweighted graph. Args: n : int : number of nodes m : int : number of edges k : int : time interval for the mouse's movement s : int : starting node of the cat t : int : starting node of the mouse edges : List[Tuple[int, int]] : list of edges in the graph Returns: str : "Yes" if the cat can catch the mouse, "No" otherwise Examples: >>> can_cat_catch_mouse(6, 7, 2, 1, 6, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (2, 4), (2, 5)]) 'Yes' >>> can_cat_catch_mouse(4, 4, 1, 1, 4, [(1, 2), (2, 3), (3, 4), (2, 4)]) 'No' >>> can_cat_catch_mouse(5, 5, 0, 3, 5, [(1, 2), (2, 3), (3, 4), (4, 5), (1, 5)]) 'Yes' >>> can_cat_catch_mouse(3, 2, 1, 1, 3, [(1, 2), (2, 3)]) 'No' >>> can_cat_catch_mouse(3, 3, 0, 1, 3, [(1, 2), (2, 3), (1, 3)]) 'Yes'

answer:from collections import deque def can_cat_catch_mouse(n, m, k, s, t, edges): def bfs(start): distances = [-1] * (n + 1) queue = deque([start]) distances[start] = 0 while queue: node = queue.popleft() for neighbor in graph[node]: if distances[neighbor] == -1: distances[neighbor] = distances[node] + 1 queue.append(neighbor) return distances graph = [[] for _ in range(n + 1)] for u, v in edges: graph[u].append(v) graph[v].append(u) cat_distances = bfs(s) mouse_distances = bfs(t) time_to_catch = cat_distances[t] if time_to_catch == -1: return "No" if k == 0: return "Yes" mouse_time = time_to_catch / k if mouse_time.is_integer(): return "No" return "Yes"