Skip to content

Instantly share code, notes, and snippets.

@alexchow
Last active December 26, 2015 23:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save alexchow/7228746 to your computer and use it in GitHub Desktop.
Save alexchow/7228746 to your computer and use it in GitHub Desktop.
This is in response to another [gist](https://gist.github.com/igor47/7228586) for a supposed solution to the [water levels question](https://news.ycombinator.com/item?id=6639839). The solution doesn't work if there is more than 1 "puddle". Example: `[2,5,1,2,3,4,7,7,6,3,5]` should return 12.
#!/usr/bin/python
def water(levels):
# state machine
filling = False
h = 0
total = 0
cur = 0
for i in xrange(1, len(levels)):
# we can start filling once we see a first drop in level
if not filling and levels[i] < levels[i-1]:
filling = True
h = levels[i-1]
if filling:
# we need to stop filling if level is above the original wall
if levels[i] >= h:
total += cur
cur = 0
filling = False
# otherwise, count this level as a puddle
else:
cur += h - levels[i]
return total
if __name__ == "__main__":
testcases = [
([1,0,1], 1),
([5,0,5], 5),
([0,1,0,1,0], 1),
([1,0,1,0], 1),
([1,0,1,2,0,2], 3),
([2,5,1,2,3,4,7,7,6], 10),
([2,5,1,2,3,4,7,7,6,3,5], 12), # fails
]
for case in testcases:
w = water(case[0])
if w == case[1]:
print "TRUE: %s holds %s" % (case[0], w)
else:
print "MISMATCH: %s holds %s (got %s)" % (case[0], case[1], w)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment