Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
def solver(array):
local_max_indexes =[]
local_max_indexes.append(0)
left_max = local_max_indexes[0]
last_ex_ind = [0];
for i in xrange(1, len(array) - 1):
#print array[i-1], array[i], array[i+1]
if(array[i] > array[i-1] and array[i] > array[i+1]):
if(array[i] >= array[left_max]):
local_max_indexes.append(i)
left_max = i
last_ex_ind = []
else:
last_ex_ind.append(i)
max_ind = 0
for i in last_ex_ind:
if(array[i] > max_ind):
max_ind = i
if(array[len(array)-1] >= array[max_ind]):
last_ex_ind = []
last_ex_ind.append(len(array)-1)
for i in last_ex_ind:
local_max_indexes.append(i)
#print local_max_indexes
#V calculation
calc_artay = local_max_indexes
j, v = 0, 0
for i in xrange(0, len(calc_artay) - 1):
real_depth = min(array[calc_artay[i]], array[calc_artay[i+1]])
while j < calc_artay[i+1]:
if(j != calc_artay[i]):
v = v + real_depth - min(array[j], real_depth)
j = j + 1
return v
def solver1(land):
leftMax = 0;
rightMax = 0;
left = 0;
right = len(land) - 1;
volume = 0;
while(left < right):
if(land[left] > leftMax):
leftMax = land[left];
if(land[right] > rightMax):
rightMax = land[right];
if(leftMax >= rightMax):
volume = volume + rightMax - land[right];
right = right - 1;
else:
volume = volume + leftMax - land[left];
left = left - 1;
return volume;
def puddle(xs):
result = 0
unresolved = []
for i in range(len(xs)):
y = xs[i]
if len(unresolved) > 0:
while y > unresolved[-1][0]:
z = unresolved.pop()[0]
if len(unresolved) == 0:
break
g, j = unresolved[-1]
g = min(g, y)
result += (g-z) * (i-j-1)
if len(unresolved) == 0:
unresolved.append((y, i))
continue
if y < unresolved[-1][0]:
unresolved.append((y, i))
else:
unresolved.append((y, i))
return result
def calculateWaterVolume(landscape):
gridHeight = max(landscape)
gridWidth = len(landscape)
# We create a 2D grid with 0-1 values
# 1 corresponds to a solid block
# 0 corresponds to empty space
grid = []
for i in range(gridWidth):
grid.append([])
for j in range(gridHeight):
if (j < landscape[i]):
grid[i].append(1)
else:
grid[i].append(0)
count = 0 # The counter for the number of squares filled with water
# Note that the first and last columns cannot hold water.
# Hence, we only need to consider columns 1, ... ,gridWidth-2
for i in range(1, gridWidth-1):
# As for rows, there is no need to consider the solid blocks
for j in range(landscape[i], gridHeight):
# The free space will be occupied by water if and only if
# there exists a solid block at the same height to the left AND
# to the right.
boundedLeft = False
for k in range(0,i):
if grid[k][j] == 1:
boundedLeft = True
boundedRight = False
for k in range(i+1, gridWidth):
if grid[k][j] == 1:
boundedRight = True
if boundedLeft and boundedRight:
count += 1
return count
def Test(array, r_answer):
answer = solver(array)
result_string = ('for array: %s answer = %d .Must be: %d') % (array, answer, r_answer)
if(answer == r_answer):
result_string = "OK " + result_string
else:
result_string = "ERROR " + result_string
print result_string
if __name__ == "__main__":
Test([1,1], 0)
Test([1,1,1,1], 0)
Test([1,2,2,1], 0)
Test([1,2,1,1], 0)
Test([1,3,1,2], 1)
Test([2,1,2], 1)
Test([2,1,4], 1)
Test([4,1,2], 1)
Test([2,1,2,1,2], 2)
Test([4,1,2,1,2], 2)
Test([2,1,4,1,2], 2)
Test([2,1,2,1,4], 2)
Test([2,1,1,1,2], 3)
Test([2,1,0,1,2], 4)
Test([4,1,1,1,4], 9)
Test([4,1,1,1,3], 6)
Test([4,1,2,1,3], 5)
Test([2,1,4,1,3], 3)
Test([2,1,4,1,1], 1)
Test([3,1,2,1,4,1,2,3], 8)
Test([3,1,2,1,4,1,2, 1, 3], 10)
Test([1,2,1,2,1], 1)
Test([1,3,1,2,1], 1)
Test([1,4,1,2,1], 1)
Test([1,4,1,4,1,2], 4)
Test([1,4,1,3,1,2], 3)
Test([1,4,1,3,1,2,1,4], 12)
Test([1,4,1,3,1,2,1,3], 7)
Test([1,4,1,3,1,2,1], 3)
Test([1,5,1,4,1,3,1,2,1], 6)
Test([1,5,1,4,1,4,1,2,1], 7)
Test([1,5,1,4,1,5,1,2,1], 10)
Test([1,5,4,3,2,1,2], 1)
Test([1,5,4,3,2,1], 0)
Test([1,-1,1], 2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.