Appearance
question:from typing import List, Tuple def find_shortest_paths(t: int, test_cases: List[Tuple[int, int, List[str]]]) -> List[int]: Determine the length of the shortest path from the top-left corner to the bottom-right corner of a grid. Return -1 if there is no such path. Args: t (int): The number of test cases. test_cases (List[Tuple[int, int, List[str]]]): A list of test cases where each test case is a tuple containing the number of rows, number of columns, and the grid itself. Returns: List[int]: A list of results where each result corresponds to the shortest path length for the respective test case. >>> find_shortest_paths(3, [(3, 3, [".#.", "...", "#.."]), (2, 2, ["..", "#."]), (3, 3, [".#.", "#", ".#."])]) [4, 2, -1] >>> find_shortest_paths(1, [(4, 4, [".#..", "..", "#.#.", "..#."])]) [-1]
answer:from collections import deque def shortest_path(n, m, grid): if grid[0][0] == '#' or grid[n-1][m-1] == '#': return -1 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] queue = deque([(0, 0, 0)]) visited = set((0, 0)) while queue: x, y, dist = queue.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 grid[nx][ny] == '.' and (nx, ny) not in visited: queue.append((nx, ny, dist+1)) visited.add((nx, ny)) return -1 def find_shortest_paths(t, test_cases): results = [] for i in range(t): n, m, grid = test_cases[i] results.append(shortest_path(n, m, grid)) return results
question:from itertools import permutations from typing import List, Tuple def get_permutations(arr: List[int]) -> List[Tuple[int]]: Given an array arr of distinct integers, return all possible permutations. You can return the answer in any order. >>> get_permutations([1, 2, 3]) [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] >>> get_permutations([1, 2]) [(1, 2), (2, 1)] >>> get_permutations([1]) [(1,)] >>> get_permutations([]) [()] pass def test_get_permutations_three_elements(): result = get_permutations([1, 2, 3]) expected = [ (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) ] assert sorted(result) == sorted(expected) def test_get_permutations_two_elements(): result = get_permutations([1, 2]) expected = [ (1, 2), (2, 1) ] assert sorted(result) == sorted(expected) def test_get_permutations_single_element(): result = get_permutations([1]) expected = [ (1,) ] assert result == expected def test_get_permutations_empty_array(): result = get_permutations([]) expected = [ () ] assert result == expected def test_get_permutations_four_elements(): result = get_permutations([1, 2, 3, 4]) expected = [ (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1) ] assert sorted(result) == sorted(expected)
answer:from itertools import permutations def get_permutations(arr): Returns all possible permutations of the input array `arr`. return list(permutations(arr))
question:from typing import List, Tuple def shortest_travel_time(n: int, m: int, roads: List[Tuple[int, int, int]], q: int, queries: List[Tuple[int, int]]) -> List[int]: Determines the shortest time from the start building to the destination building for each query. :param n: Total number of buildings. :param m: Total number of roads. :param roads: List of tuples where each tuple contains three integers u, v, and t describing a road. :param q: Total number of queries. :param queries: List of tuples where each tuple contains two integers s and d describing the start and destination buildings. :return: List of integers representing the shortest traversal times for each query, or -1 if no path exists. >>> shortest_travel_time(5, 5, [(1, 2, 10), (2, 3, 20), (3, 4, 30), (4, 5, 40), (1, 3, 100)], 2, [(1, 5), (3, 1), (3, 4)]) [100, -1, 30] >>> shortest_travel_time(4, 2, [(1, 2, 10), (2, 3, 20)], 2, [(1, 4), (3, 4)]) [-1, -1] >>> shortest_travel_time(3, 3, [(1, 2, 10), (2, 3, 10), (1, 3, 5)], 1, [(1, 3)]) [5] >>> shortest_travel_time(4, 4, [(1, 2, 10), (2, 3, 10), (1, 3, 50), (3, 4, 10)], 1, [(1, 4)]) [30] pass
answer:import heapq def dijkstra(n, adj, start): Implementation of Dijkstra's algorithm to find the shortest path from a single source to all other nodes. dist = {i: float('inf') for i in range(1, n + 1)} dist[start] = 0 pq = [(0, start)] while pq: current_dist, u = heapq.heappop(pq) if current_dist > dist[u]: continue for v, weight in adj[u]: distance = current_dist + weight if distance < dist[v]: dist[v] = distance heapq.heappush(pq, (distance, v)) return dist def shortest_travel_time(n, m, roads, q, queries): Determines the shortest time from the start building to the destination building for each query. # Create an adjacency list for the graph adj = {i: [] for i in range(1, n + 1)} for u, v, t in roads: adj[u].append((v, t)) # Precompute shortest paths from each building using Dijkstra's algorithm dist_from_building = {} for i in range(1, n + 1): dist_from_building[i] = dijkstra(n, adj, i) results = [] for s, d in queries: shortest_time = dist_from_building[s].get(d, float('inf')) results.append(shortest_time if shortest_time != float('inf') else -1) return results
question:def is_rearrangement_divisible_by_k(sequence: str, k: int) -> str: Checks if any rearrangement of the digits in the sequence forms a number divisible by k. >>> is_rearrangement_divisible_by_k("123", 3) 'Possible!' >>> is_rearrangement_divisible_by_k("56", 3) 'Impossible!' >>> is_rearrangement_divisible_by_k("12345", 5) 'Possible!' >>> is_rearrangement_divisible_by_k("678", 5) 'Impossible!' >>> is_rearrangement_divisible_by_k("7", 7) 'Possible!' >>> is_rearrangement_divisible_by_k("222", 4) 'Impossible!' >>> is_rearrangement_divisible_by_k("1234567890", 11) 'Possible!' >>> is_rearrangement_divisible_by_k("10", 2) 'Possible!' >>> is_rearrangement_divisible_by_k("10", 8) 'Impossible!'
answer:from itertools import permutations def is_rearrangement_divisible_by_k(sequence, k): Checks if any rearrangement of the digits in the sequence forms a number divisible by k. for perm in permutations(sequence): number = int("".join(perm)) if number % k == 0: return 'Possible!' return 'Impossible!'