GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Python/dynamic_programming/trapped_water.py at python3.15t · TheAlgorithms/Python Expand file tree/ Copy pathtrapped_water.pyMore file actions 60 lines (49 loc) · 2.04 KB / Copy pathtrapped_water.pyFile metadata and controls60 lines (49 loc) · 2.04 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 """ Given an array of non-negative integers representing an elevation map where the width of each bar is 1, this program calculates how much rainwater can be trapped. Example - height = (0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1) Output: 6 This problem can be solved using the concept of "DYNAMIC PROGRAMMING". We calculate the maximum height of bars on the left and right of every bar in array. Then iterate over the width of structure and at each index. The amount of water that will be stored is equal to minimum of maximum height of bars on both sides minus height of bar at current position. """ def trapped_rainwater(heights: tuple[int, ...]) -> int: """ The trapped_rainwater function calculates the total amount of rainwater that can be trapped given an array of bar heights. It uses a dynamic programming approach, determining the maximum height of bars on both sides for each bar, and then computing the trapped water above each bar. The function returns the total trapped water. >>> trapped_rainwater((0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)) 6 >>> trapped_rainwater((7, 1, 5, 3, 6, 4)) 9 >>> trapped_rainwater((7, 1, 5, 3, 6, -1)) Traceback (most recent call last): ... ValueError: No height can be negative """ if not heights: return 0 if any(h < 0 for h in heights): raise ValueError("No height can be negative") length = len(heights) left_max = [0] * length left_max[0] = heights[0] for i, height in enumerate(heights[1:], start=1): left_max[i] = max(height, left_max[i - 1]) right_max = [0] * length right_max[-1] = heights[-1] for i in range(length - 2, -1, -1): right_max[i] = max(heights[i], right_max[i + 1]) return sum( min(left, right) - height for left, right, height in zip(left_max, right_max, heights) ) if __name__ == "__main__": import doctest doctest.testmod() print(f"{trapped_rainwater((0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1)) = }") print(f"{trapped_rainwater((7, 1, 5, 3, 6, 4)) = }") |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |