Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #By BillBodkin
- '''
- You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is
- unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.
- Compute how many units of water remain trapped on the map in O(N) time and O(1) space.
- For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.
- Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index
- (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water
- '''
- #heightmap = [2, 1, 2]
- heightmap = [3, 0, 1, 3, 0, 5]
- water = [0] * len(heightmap)
- def rain(amt):
- for w in range(0, len(water)):
- water[w] += amt
- def slosh(waterMoveSpeed):
- for w in range(0, len(water)):
- height = heightmap[w] + water[w]
- leftHeight = -999
- rightHeight = -999
- if(w > 0):
- leftHeight = heightmap[w - 1] + water[w - 1]
- if(w < len(water) - 1):
- rightHeight = heightmap[w + 1] + water[w + 1]
- #print("index: " + str(w))
- #print("height: " + str(height))
- #print("leftHeight: " + str(leftHeight))
- #print("rightHeight: " + str(rightHeight))
- if(height > leftHeight):
- toMove = min(waterMoveSpeed, water[w], height - leftHeight)
- water[w] -= toMove
- if(leftHeight > -1):
- water[w - 1] += toMove
- height = heightmap[w] + water[w]
- if(height > rightHeight):
- toMove = min(waterMoveSpeed, water[w], height - rightHeight)
- water[w] -= toMove
- if(rightHeight > -1):
- water[w + 1] += toMove
- for i in range(0, 100):
- rain(0.1)
- for i in range(0, 2000):
- slosh(0.1)
- for w in range(0, len(water)):
- water[w] = round(water[w], 2)
- print(water)
- print(sum(water))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement