Appearance
question:# Problem Statement One of the popular text formatting needs in document processing is formatting numbers as words in English. For example, converting `123` to "one hundred twenty-three". This capability can greatly enhance document readability and automate the creation of more human-friendly content. # Requirements Implement a Python function `number_to_words` that takes a single parameter, `num: int`, representing a non-negative integer, and returns a string representing the English words for the given number. # Constraints * The function should handle numbers in the range `[0, 999999]` inclusive. * You should avoid using any third-party libraries that directly convert numbers to words. # Input and Output Formats * **Input**: * `num: int` - A non-negative integer that needs to be converted to words. * **Output**: * `str` - A string representing the English words for the given number. # Example ```python def number_to_words(num: int) -> str: # Your implementation here # Test cases print(number_to_words(0)) # Output: "zero" print(number_to_words(123)) # Output: "one hundred twenty-three" print(number_to_words(1001)) # Output: "one thousand one" print(number_to_words(100000)) # Output: "one hundred thousand" print(number_to_words(123456)) # Output: "one hundred twenty-three thousand four hundred fifty-six" ``` # Hints * Consider breaking down the problem by handling units, tens, hundreds, thousands, and so on separately. * Handle special cases such as numbers involving "zero" correctly to avoid issues with concatenation. # Notes * Ensure to follow proper English grammar rules for converting numbers to words. * Test your function thoroughly with edge cases like `0`, `999999`, and different ranges of numbers to ensure accuracy.
answer:def number_to_words(num: int) -> str: if num == 0: return "zero" ones = ["", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"] teens = ["", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"] tens = ["", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"] def one(num): return ones[num] def two_less_20(num): return teens[num - 10] def ten(num): return tens[num] def two(num): if not num: return "" elif num < 10: return one(num) elif num < 20: return two_less_20(num) else: ten_val = num // 10 rest = num % 10 return ten(ten_val) + ("-" + one(rest) if rest else "") def three(num): hundred_val = num // 100 rest = num % 100 if hundred_val and rest: return one(hundred_val) + " hundred " + two(rest) elif not hundred_val and rest: return two(rest) elif hundred_val and not rest: return one(hundred_val) + " hundred" def word(num): million = num // 1_000_000 thousand = (num // 1_000) % 1_000 rest = num % 1_000 part = [] if million: part.append(three(million) + " million") if thousand: part.append(three(thousand) + " thousand") if rest: part.append(three(rest)) return " ".join(part) return word(num)
question:# Problem Statement You are given an `n x n` grid where each cell has a non-negative integer representing the cost of passing through that cell. You are required to find the minimum path sum from the top-left corner to the bottom-right corner. You can only move down or right at any point in time. Implement the function `min_path_sum(grid: List[List[int]]) -> int`. # Function Signature ```python def min_path_sum(grid: List[List[int]]) -> int: ``` # Input - `grid`: A list of lists of integers where `1 <= len(grid), len(grid[0]) <= 100` and each integer is between `0` and `100` inclusive. # Output - An integer representing the minimum path sum to travel from the top-left corner to the bottom-right corner of the grid. # Constraints - All input values and dimensions are guaranteed to be valid as per the specifications. # Example ```python grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] print(min_path_sum(grid)) # Outputs: 7 grid = [ [1, 2, 3], [4, 5, 6] ] print(min_path_sum(grid)) # Outputs: 12 ``` # Execution Requirements - The function should be efficient in terms of both time and space complexity, given the constraints. - Memory usage should be handled carefully to avoid excessive consumption. # Scenario Imagine you are programming a robot to navigate a warehouse with a specific layout. The goal is to minimize the energy consumption of the robot as it travels from its starting position at the entrance (top-left corner) to its target at the exit (bottom-right corner). The grid represents the layout of the warehouse where each cell requires a different amount of energy to pass through. Your function will calculate the optimal path for the robot, ensuring minimal energy usage.
answer:from typing import List def min_path_sum(grid: List[List[int]]) -> int: Given a 2D grid of non-negative integers representing the cost of passing through cells, returns the minimum path sum from the top-left corner to the bottom-right corner. You can only move down or right at any point in time. if not grid or not grid[0]: return 0 rows, cols = len(grid), len(grid[0]) # Create a 2D dp array with the same dimensions as grid dp = [[0] * cols for _ in range(rows)] dp[0][0] = grid[0][0] # Initialize the first column for i in range(1, rows): dp[i][0] = dp[i-1][0] + grid[i][0] # Initialize the first row for j in range(1, cols): dp[0][j] = dp[0][j-1] + grid[0][j] # Fill up the dp array for i in range(1, rows): for j in range(1, cols): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[rows-1][cols-1]
question:# Question: Implement Insertion Sort Context: Your task is to implement the insertion sort algorithm for a given list of integers. The function should sort the list in ascending order using the insertion sort technique. Function Signature: ```python def insertion_sort(lst: list) -> list: ``` Parameters: - `lst`: a list of integers that need to be sorted. Returns: - The function returns a list of integers sorted in ascending order. Constraints: - The input list can be empty. - Consider edge cases like a list with only one element, a list that is already sorted, and a list that is sorted in reverse order. - Do not use any in-built sort functions. Examples: ```python # Example 1 print(insertion_sort([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])) # Output: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9] # Example 2 print(insertion_sort([5, 4, 3, 2, 1])) # Output: [1, 2, 3, 4, 5] # Example 3 print(insertion_sort([1, 2, 3, 4, 5])) # Output: [1, 2, 3, 4, 5] # Example 4 print(insertion_sort([7])) # Output: [7] # Example 5 print(insertion_sort([])) # Output: [] ``` Note: Implement the insertion sort algorithm by iterating through the list and inserting each element into its correct position relative to the sorted portion of the list. Ensure to handle the provided edge cases and that the function works optimally for different sizes of input lists.
answer:def insertion_sort(lst: list) -> list: Perform insertion sort on a list of integers. :param lst: List of integers to be sorted. :return: List of integers sorted in ascending order. for i in range(1, len(lst)): key = lst[i] j = i - 1 while j >= 0 and key < lst[j]: lst[j + 1] = lst[j] j -= 1 lst[j + 1] = key return lst
question:# Matrix Transpose Function Implement a function to compute the transpose of a given square matrix. Ensure your implementation is optimized for performance and adheres to the constraints and requirements detailed below. Function Signature ```python def transpose_matrix(matrix: List[List[int]]) -> List[List[int]]: Given a square matrix, return its transpose. ``` Input * A List of Lists (2D List) `matrix` representing the square matrix, where each inner list has the same number of integer elements as the number of inner lists. Output * A new 2D List that represents the transpose of the input matrix. Constraints and Requirements * The function should handle matrices ranging from 1x1 to 1000x1000 elements. * The function should raise a `ValueError` if the input `matrix` is not square. * The function should perform the transpose operation in O(n^2) time complexity, where `n` is the dimension of the matrix. * Space complexity should remain O(n^2) for the result storage but avoid using any additional significant data structures. Example ```python # Example usage matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] transposed = transpose_matrix(matrix) # transposed should be: # [ # [1, 4, 7], # [2, 5, 8], # [3, 6, 9] # ] ``` Testing Design and include unittests to verify your implementation, taking care to include edge cases such as: - Empty matrix - Single-element matrix - Typical square patterns of varying sizes (2x2, 3x3, etc.) - Maximum constraint size (1000x1000) For example, for unit testing in Python: ```python import unittest class TestTransposeMatrix(unittest.TestCase): def test_empty_matrix(self): self.assertEqual(transpose_matrix([]), []) def test_single_element_matrix(self): self.assertEqual(transpose_matrix([[1]]), [[1]]) def test_typical_case(self): self.assertEqual(transpose_matrix([[1, 2], [3, 4]]), [[1, 3], [2, 4]]) def test_large_matrix(self): matrix = [[i + j*1000 for i in range(1000)] for j in range(1000)] expected = [[matrix[j][i] for j in range(1000)] for i in range(1000)] self.assertEqual(transpose_matrix(matrix), expected) def test_non_square_matrix(self): with self.assertRaises(ValueError): transpose_matrix([[1, 2, 3], [4, 5, 6]]) if __name__ == "__main__": unittest.main() ```
answer:from typing import List def transpose_matrix(matrix: List[List[int]]) -> List[List[int]]: Given a square matrix, return its transpose. if not matrix: return [] n = len(matrix) if any(len(row) != n for row in matrix): raise ValueError("The input matrix is not square") transposed = [[matrix[j][i] for j in range(n)] for i in range(n)] return transposed