puddles_problem.py

"""
We have walls of different heights represented
with the following array: [2,5,1,2,3,4,7,7,6].

The value at each index is the height of the wall.

Now imagine it rains. How much water is going
to be accumulated in puddles between walls?

We count volume in square blocks of 1X1.
Everything to the left of index 1 spills out.
Water to the right of index 7 also spills out.
We are left with a puddle between
1 and 6 and the volume is 10.
"""

heights = [2, 5, 1, 2, 3, 4, 7, 7, 6]

def calc(heights, left, right, level):
    amount = 0
    # Only the amount of water in between
    # should be calculated, so both the first
    # and the last wall should be skipped
    for i in xrange(left+1, right):
        if level > heights[i]:
            amount += level-heights[i]
    print "Amount of water: %i" % amount

def delete_smaller_values_from_beginning(l):
    """
    This function accepts a list of integers
    and returns a new list starting from the
    first element that is greater than
    the element that comes right after it.

    So for [1, 2, 4, 3] it returns [4, 3].
    """
    for i in xrange(1, len(l)):
        if l[i-1] > l[i]:
            return l[(i-1):]

heights = delete_smaller_values_from_beginning(heights)
heights = delete_smaller_values_from_beginning(heights[::-1])[::-1]

number_of_walls = len(heights)

left = None
right = None
level = None
pos = 0

while pos < number_of_walls:
    if level == None:
        left = pos
        level = heights[pos]

    right = pos

    if (
        # The distance between the first and
        # the last wall should be at least 3
        (right > left+1)
        and
        (
            # Perform the calculation if:
            #
            # 1. the level at the given position is greater 
            # than or equal to the level of the first wall
            # of the puddle
            #
            # or
            #
            # 2. if the given position is the last in the
            # array.
            #
            # or
            #
            # 3. if there are no walls greater than or
            # equal to the wall at the given position
            # after it.
            (pos == number_of_walls-1)
            or
            (heights[pos] >= level)
            or
            (heights[pos] > max(heights[(pos+1):]))
        )
    ):
        calc(heights, left, right, min(level, heights[pos]))

        # The same wall can be the first wall of
        # one puddle and the last wall of another.
        # At the same time, the next puddle
        # can only begin from a wall that
        # has a lower wall right after it.
        for i in xrange(pos, number_of_walls):
            if i == number_of_walls-1:
                # No more walls, stop calculating
                pos = number_of_walls
            elif heights[i] > heights[i+1]:
                left = i
                pos = i
                level = heights[i]
                right = None
                break
    else:
        pos += 1