-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathwaterfall-streams.py
127 lines (120 loc) · 4.49 KB
/
waterfall-streams.py
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
# Waterfall Streams
# 🟣 Very Hard
#
# https://www.algoexpert.io/questions/waterfall-streams
#
# Tags: Arrays
import timeit
# Simulate the water flow through the matrix, when we hit an obstacle,
# try to flow left and right, discard flows that get interrupted.
#
# Time complexity: O(m*n^2) - Where m is the number of rows and n is the
# number of columns in the matrix, we iterate over all rows, for each
# row we visit all positions checking if they contain water, if they do,
# we may check n positions in the matrix until we find where the water
# will fall or decide that it gets stuck.
# Space complexity: O(n) - We store n values in memory.
class Solution:
def waterfallStreams(self, array, source):
rows, cols = len(array), len(array[0])
dp = [0] * cols
# All the water falls below the source.
dp[source] = 100
for row in range(1, rows):
# The amount of water that each column will see through.
buckets = [0] * cols
for col, water in enumerate(dp):
if water:
if array[row][col] == 0:
buckets[col] += water
else:
# Some water flows left.
for idx in range(col - 1, -1, -1):
# If there is a block in the previous row,
# the water will become trapped.
if array[row - 1][idx] == 1:
break
# If the water could flow here and it can
# fall into this bucket, it will.
if array[row][idx] == 0:
buckets[idx] += water / 2
break
# Some water flows right.
for idx in range(col + 1, cols):
# If there is a block in the previous row,
# the water will become trapped.
if array[row - 1][idx] == 1:
break
# If the water could flow here and it can
# fall into this bucket, it will.
if array[row][idx] == 0:
buckets[idx] += water / 2
break
dp = buckets[::]
return dp
def test():
executors = [Solution]
tests = [
[[[0], [0], [0], [0], [0], [0], [0]], 0, [100]],
[[[0], [0], [0], [1], [0], [0], [0]], 0, [0]],
[
[
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0],
],
3,
[0, 0, 0, 25, 25, 0, 0],
],
[
[
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
],
6,
[0, 0, 0, 0, 0, 0, 0],
],
[
[
[0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 1, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
],
3,
[25, 6.25, 0, 0, 0, 6.25, 0],
],
]
for executor in executors:
start = timeit.default_timer()
for _ in range(1):
for col, t in enumerate(tests):
sol = executor()
result = sol.waterfallStreams(t[0], t[1])
exp = t[2]
assert result == exp, (
f"\033[93m» {result} <> {exp}\033[91m for"
+ f" test {col} using \033[1m{executor.__name__}"
)
stop = timeit.default_timer()
used = str(round(stop - start, 5))
cols = "{0:20}{1:10}{2:10}"
res = cols.format(executor.__name__, used, "seconds")
print(f"\033[92m» {res}\033[0m")
test()