Skip to content

Instantly share code, notes, and snippets.

@Alfex4936
Last active December 23, 2020 01:43
Show Gist options
  • Save Alfex4936/e7c5d377808ece62acdd10cd9633c9d8 to your computer and use it in GitHub Desktop.
Save Alfex4936/e7c5d377808ece62acdd10cd9633c9d8 to your computer and use it in GitHub Desktop.
Python: solving Water Area problem in most bizaare and inefficient way
heights = [0, 8, 0, 0, 5, 0, 0, 10, 0, 0, 1, 1, 0, 3]
"""Result
(0 for void, 1 for a pillar, 2 for water)
[[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 2, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 2, 1, 2, 2, 1, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 1],
[0, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 1],
[0, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1]]
"""
# why not trying with visual
def waterArea(heights):
if not heights:
return 0
from pprint import pprint
Max = max(heights)
graphic = [[0 for width in range(len(heights))] for height in range(Max)]
area = 0
for index, height in enumerate(heights):
i = len(graphic) - 1 # from the bottom
while height > 0:
graphic[i][index] = 1 # set a pillar
i -= 1
height -= 1 # building higher
for i, line in enumerate(graphic):
indices = [i for i, x in enumerate(line) if x == 1] # get all pillars' indices
if len(indices) <= 1: # only 1 pillars around
continue
first, second = indices.pop(0), indices.pop(0)
while True:
for between in range(first + 1, second): # change 0 to 2 between 1 (pillars)
graphic[i][between] = 2
area += 1 # add water area
if len(indices) == 0:
break
first, second = second, indices.pop(0)
pprint(graphic)
return area
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment