Waterflow Problem

For each location calculate (1) the maximum of all the heights up to and including that point and (2) the maximum of heights from that point onward.

The smaller of those two numbers minus the height at that point is the water amount.

Add all the water amounts to get $\boxed{791}$

The bottom row is the array, and the top row is the number of cells with water in each column. If you add all the numbers in the top row, you will get that the total amount of water is 791.

Here is a beautiful implementation of what @Marta Reece said, in Haskell:

1
2
3
4
5
6
7

water :: [Int] -> Int
water hs =
  sum (zipWith (-)
               (zipWith min
                        (scanl1 max hs)
                        (scanr1 max hs))
               hs)

Here's a really short python solution:

hill = "4 2 4 1 5 3 16 6 17 19 4 13 5 3 10 10 13 6 2 1 5 15 13 19 16 9 13 1 7 18 20 13 9 7 2 10 8 18 4 7 5 8 10 13 7 18 19 2 19 8 10 10 17 6 6 20 20 11 10 11 13 9 7 1 10 5 12 16 10 7 15 13 12 10 1 1 4 2 16 10 20 17 11 19 19 20 9 10 17 9 18 8 10 18 8 19 16 17 3 1"
hill_nums = [int(x) for x in hill.split(" ")]
water = [0] * len(hill_nums)
print(water)

for i in range(1, len(hill_nums)-1):
    water[i] = max(0, min(max(hill_nums[:i]), max(hill_nums[i+1:])) - hill_nums[i])

print(water)
print(sum(water))

Fed 100 and the array to STDIN.

 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

#include <iostream>

using namespace std;

int main()
{
    int N, s = 0;
    cin >> N;
    int a[N];
    for(int i = 0; i < N; ++i)
        cin >> a[i];
    for(int i = 0; i < N - 1; ++i)
        if(a[i] > a[i + 1])
        {
            int itemp = i + 1, j;
            for(j = i + 1; a[j] < a[i] && j < N; ++j)
                if(a[i] - a[j] <= a[i] - a[itemp])
                    itemp = j;
            if(j != N)
            {
                for(int k = i + 1; k < j; ++k)
                    s += (a[i] - a[k]);
                i = j - 1;
            }
            else
                if(itemp != i)
                {
                    for(int k = i + 1; k < itemp; ++k)
                        s += (a[itemp] - a[k]);
                    i = itemp - 1;
                }
                else
                    break;
        }
    cout << s;
}

So you need to make a new array in which the values of the current array are replaced by the minimum of "maximum of the previous entries" and "maximum of the upcoming entries". This minimum gives the water level. You then need to subtract the hill level to have the water content, and then sum it all to get the total water content.

Here is my one line solution ;o) (well actually is two lines because I need to import numpy)

1
2

import numpy as np
print(np.sum([min(max(hill[0:i+1]),max(hill[i:len(hill)])) - hill[i] for i in range(0,len(hill))]))

It returns $\fbox{791}$ .

details: max(hill[0:i+1]) and max(hill[i:len(hill)]) return "maximum of the previous entries" and "maximum of the upcoming entries"

min(max(hill[0:i+1]),max(hill[i:len(hill)])) is the water level at the i $^\text{th}$ entry.

min(max(hill[0:i+1]),max(hill[i:len(hill)])) - hill[i] is the water content corresponding to this entry.

[ "some expression with i" for i in range(0,len(hill))] makes a list with the same length as hill and the i $^\text{th}$ entry is evaluated. So in our case the list of the water content at the current position.

np.sum() returns the sum of the list elements. So in our case the total water content.

For each point take the lesser of the left and right highest peaks (aka water level) and subtract the hill height.

In python:

$for\:i\:in\:range(len(hill)): water \mathrel{+}= min(max(hill[:i+1]), max(hill[i:])) - hill[i]$

Note: The +1 is neccesary since a[b:c] includes b but excludes c. Therefore "hills up to and including i" is "hill[:i+1]" while "hills from and including i" is just "hill[i:]".

I did it in steps manually. Let the first largest and the second largest numbers are n and m respectively. They could be equal. If they repeat, use the left most and the right most numbers. To complete the step find the differences of m(second largest) and any number between the two chosen largest numbers. Now find the total of all differences. The total is the result of the step. Repeat the step to the left and to the right of the chosen numbers till all numbers are covered. If there aren't numbers between the two chosen numbers, the result of the step is 0. I did it in 10 steps. Lastly find the sum of the results from all of the steps. You should end up with 791.

Step 1: The two largest numbers are 20 and 20, result 512. The steps on the left side of 20 and 20 are with numbers: 19 and 20, result 197: 17 and 19, result 0; 16 and 17, result 10; 5 and 16, result 2; 4 and 5, result 5. On the right side of the initial numbers 20 and 20 the steps are with numbers: 20 and 19, result 64; 19 and 17, result 1; 17 and 3, result 0; 3 and 1, result 0. As I said, we end up with 791.

In Python 3. Gives the answer $\boxed{791}$ .

 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

def accu(string):
    # Make it a list
    array = string.split(' ')
    new = [int(i) for i in array]
    # Find the max and min of the list, first time. Second and latter time will be in the while loop.
    upper_bound = max(new)
    lower_bound = min(new)
    # A copy of max
    proto = upper_bound
    # Initialize the result sum.
    result = 0
    while (proto>=lower_bound):
        # Count the index of first appear upper_bound
        first_occur = new.index(upper_bound)
        # Count the index of last appear upper_bound
        last_occur = len(new)-1-new[::-1].index(upper_bound)
        # If the list only have one max number.
        if first_occur == last_occur:
            # Setting new list instead.
            new = new[:first_occur] + [upper_bound-1] + new[first_occur+1:]
        # If the list have more than one max number.
        else:
            for_calc = new[first_occur+1:last_occur]
            want_to_sum = [upper_bound-i for i in for_calc]
            result += sum(want_to_sum) # Accumulate the raindrops. 
            # Setting new list after retrieve the volume of raindrops.
            new = new[:first_occur] + [upper_bound-1]*(last_occur-first_occur+1)+new[last_occur+1:]
        # Setting new upper_bound
        upper_bound = max(new)
        # Refresh the copy of upper_bound
        proto = upper_bound
    return result
test = '4 2 4 1 5 3 16 6 17 19 4 13 5 3 10 10 13 6 2 1 5 15 13 19 16 9 13 1 7 18 20 13 9 7 2 10 8 18 4 7 5 8 10 13 7 18 19 2 19 8 10 10 17 6 6 20 20 11 10 11 13 9 7 1 10 5 12 16 10 7 15 13 12 10 1 1 4 2 16 10 20 17 11 19 19 20 9 10 17 9 18 8 10 18 8 19 16 17 3 1'
print (accu(test))

This solution focuses on rows rather than columns. Implemented in MATLAB.

Let $x$ be the $m$ -dimensional vector that describes the cell topography. Transform $x$ into an $n \times m$ binary matrix where $1$ and $0$ represent land and sky respectively. Note that $n = \max{x}$ . For the $ith$ row in this matrix (where $i=1,...,n$ ), trim the leading and trailing zeros to create a new vector, $y_i$ . Then the water in the $ith$ row is equal to $length(y_i)-sum(y_i)$ and the total water is then $\sum_{i=1}^{n}(length(y_i)-sum(y_i))$ .

Here's a visual of the example.

The MATLAB code. It could be tightened up a bit, of course.

I used the same algorithm as Marta

For those who want to try, I copied the land array into cells A3:A102 (and included terminating zeroes in A2 and A103)

In cell B3 insert formula:

$=MAX(MIN(MAX(A\$2:A2)-A3,MAX(A4:A\$103)-A3),0)$

and copy down to B102.

Then sum B3:B102 to get the accumulated amount of water.

In R

 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

hills <- c(4,2,4,1,5,3,16,6,17,19,4,13,5,3,10,10,13,6,2,1,5,15,13,19,16,9,13,1,7,18,20,13,9,7,2,10,8,18,4,7,5,8,10,13,7,18,19,2,19,8,10,10,17,6,6,20,20,11,10,11,13,9,7,1,10,5,12,16,10,7,15,13,12,10,1,1,4,2,16,10,20,17,11,19,19,20,9,10,17,9,18,8,10,18,8,19,16,17,3,1);

nextpeak <- function(u,i) {
    n <- length(u);
    if(i<n) {
        h <- u[i];
        u <- u[c((i+1):n)];
        return(min(h,max(u)));
    }
    return(u[i]);
};

pk = min(hills)-1;
regen = c();
n <- length(hills);
for(i in c(1:n)) {
    h <- hills[i];
    if(h >= pk) {
        pk = nextpeak(hills,i);
        regen <- c(regen,0);
    } else {
        regen <- c(regen,pk-h);
    }
}

df <- t(matrix(c(hills,regen),n,2));
barplot(df,col=c('red','blue'));
show(sum(regen)); # results in 791

I am doing a visual solution by print out the hills. Then scan each level for the first and last barriers. The empty spaces are where water exists.

 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

ll = [4, 2, 4, 1, 5, 3, 16, 6, 17, 19, 4, 13, 5, 3, 10, 10, 13, 6, 2, 1, 5, 15,
        13, 19, 16, 9, 13, 1, 7, 18, 20, 13, 9, 7, 2, 10, 8, 18, 4, 7, 5, 8, 10, 13, 
        7, 18, 19, 2, 19, 8, 10, 10, 17, 6, 6, 20, 20, 11, 10, 11, 13, 9, 7, 1, 10, 
        5, 12, 16, 10, 7, 15, 13, 12, 10, 1, 1, 4, 2, 16, 10, 20, 17, 11, 19, 19, 20, 
        9, 10, 17, 9, 18, 8, 10, 18, 8, 19, 16, 17, 3, 1]

# create hill list
hill = ['#'*n + ' ' * (max(ll)-n) for i,n in enumerate(ll)]
# rotate CCW
hillr=[[hill[i][j] for i in range(len(hill))] for j in range(max(ll))]
hill = [''.join(x) for x in hillr][::-1]

# print hill
for level in hill:
    print(level)

# calculate pit units
count = 0
for x in hill:
    first = x.index('#')
    last = len(x) - 1 - x[::-1].index('#')
    mid = x[first:last]
    count += mid.count(' ')

print('water retained: ', count) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

                                #                        ##                       #    #
           #             #      #               # #      ##                       #  ###         #
           #             #     ##      #       ## #      ##                       #  ###    #  # #
          ##             #     ##      #       ## #   #  ##                       ## ###  # #  # # #
        # ##             ##    ##      #       ## #   #  ##          #          # ## ###  # #  # ###
        # ##           # ##    ##      #       ## #   #  ##          #  #       # ## ###  # #  # ###
        # ##           # ##    ##      #       ## #   #  ##          #  #       # ## ###  # #  # ###
        # ## #    #    #### #  ###     #     # ## #   #  ##   #      #  ##      # ## ###  # #  # ###
        # ## #    #    #### #  ###     #     # ## #   #  ##   #     ##  ###     # ## ###  # #  # ###
        # ## #    #    #### #  ###     #     # ## #   #  ### ##     ##  ###     # ######  # #  # ###
        # ## #  ###    #### #  ###   # #    ## ## # ###  ######   # ### ####    ######## ## # ## ###
        # ## #  ###    ######  ####  # #    ## ## # ###  #######  # ### ####    ############# ## ###
        # ## #  ###    ######  ####  ###   ### ## #####  #######  # ### ####    ####################
        # ## #  ###    ###### ###### ### # ###### #####  ######## # ########    ####################
        #### #  ####   ###### ###### ### # ###### ############### # ########    ####################
      # #### ## ####  ####### ###### ### ######## ############### ##########    ####################
  # # # ####### ####  ####### ###### ############ ############### ##########  # ####################
  # # ##############  ####### ###### ############ ############### ##########  # #####################
  ### ############### ####### ################################### ##########  #######################
  ####################################################################################################

water retained:  791

a little complicated solution : )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

hill = [4, 2, 4, 1, 5, 3, 16, 6, 17, 19, 4, 13, 5, 3, 10, 10, 13, 6, 2, 1, 5, 15,
            13, 19, 16, 9, 13, 1, 7, 18, 20, 13, 9, 7, 2, 10, 8, 18, 4, 7, 5, 8, 10, 13, 
            7, 18, 19, 2, 19, 8, 10, 10, 17, 6, 6, 20, 20, 11, 10, 11, 13, 9, 7, 1, 10, 
            5, 12, 16, 10, 7, 15, 13, 12, 10, 1, 1, 4, 2, 16, 10, 20, 17, 11, 19, 19, 20, 
            9, 10, 17, 9, 18, 8, 10, 18, 8, 19, 16, 17, 3, 1]
    water = 0
    for y in range(0, max(hill)):
        last_land = len(hill) + 1
        for x in range(0, len(hill)):
            if y <= hill[x] - 1:
                water += max(0, x - last_land - 1)
                last_land = x
    print(water)

A brute force solution. Scan each level of terrain. Every time you encounter a column with a block at that level, you take the distance to the previous 1 and subtract 1 (so the number of spaces between them), then overwrite the previous one as the current one. This code basically counts up the amount of water on each layer, layer by layer.

Hi, i did this bottom up:

1. trim the empty space surrounding the hill
2. count the empty spaces and add the result to final result
3. fill the empty spaces with 1
4. strip the bottom layer of the hill by 1

repeat until the hill width shrunk to at least 2

python code:

import numpy as np

hill = "4 2 4 1 5 3 16 6 17 19 4 13 5 3 10 10 
13 6 2 1 5 15 13 19 16 9 13 1 7 18 20 13 9 7 
2 10 8 18 4 7 5 8 10 13 7 18 19 2 19 8 10 10 
17 6 6 20 20 11 10 11 13 9 7 1 10 5 12 16 
10 7 15 13 12 10 1 1 4 2 16 10 20 17 11 19 
19 20 9 10 17 9 18 8 10 18 8 19 16 17 3 1" 
.split(" ")
hill = np.array(list(map(int, hill)))
water = 0

while(len(hill) > 2):
    hill = np.trim_zeros(hill) 
    water += np.count_nonzero(hill == 0)
    hill = hill + (hill == 0)
    hill = hill - 1

print(water)

Below is a Java Script code that solves this problem.

var hill = [4, 2, 4, 1, 5, 3, 16, 6, 17, 19, 4, 13, 5, 3, 10, 10, 13, 6, 2, 1, 5, 15, 13, 19, 16, 9, 13, 1, 7, 18, 20, 13, 9, 7, 2, 10, 8, 18, 4, 7, 5, 8, 10, 13, 7, 18, 19, 2, 19, 8, 10, 10, 17, 6, 6, 20, 20, 11, 10, 11, 13, 9, 7, 1, 10, 5, 12, 16, 10, 7, 15, 13, 12, 10, 1, 1, 4, 2, 16, 10, 20, 17, 11, 19, 19, 20, 9, 10, 17, 9, 18, 8, 10, 18, 8, 19, 16, 17, 3, 1]
var n = hill.length, hillterrain = '', hillslice;
while (Number(hill.join('')) > 0) {
    for (i = 0, hillslice = ''; i < n; i++)
        if (hill[i] > 0) {
            hillslice += 'x'
            hill[i]--
        } else {
            hillslice += ' '
        }
    hillterrain = hillterrain.concat(hillslice.trim()).replace(/x+/g, 'x')
}
console.log("The hill\r" + hillterrain)
console.log("Water in the hill\r")
console.log("Method 1: " + hillterrain.match(/ /g).length)
console.log("Method 2: " + (hillterrain.split(' ').length - 1))
console.log("Method 3: " + hillterrain.replace(/ /g, '•').replace(/x/g, '').length)

Basically, it builds the hill terrain slice by slice, from bottom to top (max of hill): a space for the water (light blue) and an 'x' for the solid (orange). As we care only for the water that stays in the hill, each time we build a hill slice, we trim it so that spaces left and right go away. After this, the slice will be a string which starts and ends with 'x' and will be appended to the terrain string. We will end up with a long string of 'x' and spaces, starting and ending with 'x'. The water that stays in the hill is the number of spaces in this string and this number can be obtained by various methods as the code shows.

An O(N) brute force technique would be to set up markers on the left and right of the array, and move each in until you hit a local maximum just by comparing the selected value with the next value in (i.e. when each "hill" starts going downhill to the left or right). At that point, you know that regardless of whatever else is in happening in the middle, anything lower this is trapped water, kind of like a bowl. So, from the lower of the two walls, move inward, adding water until you run into a new, higher peak (and forming a potentially deeper bowl), check which of the two walls (right or left) is higher, and repeat the process. Once the point you're measuring hits the opposite wall, you've finally counted everything available.

Here's some code for it in python (written by someone who doesn't actually know python, so apologies for all the obvious shortcuts I've skipped):

 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

hills = [4,2,4,1,5,3,16,6,17,19,4,13,5,3,10,10,13,6,
        2,1,5,15,13,19,16,9,13,1,7,18,20,13,9,7,2,10,
        8,18,4,7,5,8,10,13,7,18,19,2,19,8,10,10,17,6,
        6,20,20,11,10,11,13,9,7,1,10,5,12,16,10,7,15,
        13,12,10,1,1,4,2,16,10,20,17,11,19,19,20,9,
        10,17,9,18,8,10,18,8,19,16,17,3,1]
pl = 0 #position on the left
pr = len(hills)-1 #position on the right
wl = 0 #wall position on the left
wr = len(hills)-1 #wall position on the right
water = 0 #current accumulated water
while pl < pr: # while the two position are still on the left/right of each other
  if hills[pl+1] >= hills[wl]: # move left wall in as long as it slopes up
    pl = pl+1
    wl = pl
    continue
  if hills[pr-1] >= hills[wr]: # move right wall in as long as it slopes up
    pr = pr-1
    wr = pr
    continue
  # at this point you have a pool since something is lower than the left or right wall
  if hills[wl] >= hills[wr]: # if the right wall is lower, count all the water until you hit a new right wall
    pr = pr-1
    water = water + hills[wr] - hills[pr]
  # else count in from the left until you hit a new left wall
  else:
    pl = pl+1
    water = water + hills[wl] - hills[pl]
else: #once the position markers have met, you've found all the water
  print("Total Water: ",water)

Here is my solution in Java:

public static int getWater (String hillString) {

    String[] _hill = hillString.split(" ");
    int[] hill = new int[_hill.length];
    int maxValue = Integer.MIN_VALUE;

    for (int i = 0; i < _hill.length; i++) {
        hill[i] = Integer.parseInt(_hill[i]);
        if(hill[i] > maxValue ) {
            maxValue = hill[i];
        }
    }

    int water = 0;
    for (int i = 1; i <= maxValue; i++) {
        List <Integer> barriers = new ArrayList<Integer>();
        for (int j = 0; j < hill.length; j++) {
            if(hill[j] >= i) {
                barriers.add(j);
            }
        }
        for (int j = 0; j < barriers.size() - 1; j++) {
            water += barriers.get(j + 1) - barriers.get(j) - 1;
        }
    }

    return water;
}

Java solution:

public class WaterInHill { public int[][] getHill(int[] x) { int max = 0;

    for (int i = 0; i < x.length; i++)
    {
        if (x[i] > max)
        {
            max = x[i];
        }
    }

    int[][] hill = new int[max+1][x.length];

    for (int p = 0; p < x.length; p++)
    {
        for (int q = 0; q <= x[p]; q++)
        {
            hill[max - q][p] = 2;
        }
    }

    return hill;
}

public int getWaterFilling(int[] x)
{
    int[][] hill = getHill(x);
    boolean[] filled = new boolean[x.length];
    int sum = 0;

    for (int row = 0; row < hill.length; row++)
    {
        for (int column = 0; column < hill[0].length; column++)
        {
            if (hill[row][column] == 2)
            {
                for (int p = column+1; p < hill[0].length; p++)
                {
                    if (hill[row][p] == 2)
                    {
                        //set filled to true for all of them from row to p
                        //find the column height with respect to row

                        for (int i = column; i <= p; i++)
                        {
                            if (i > column && i <= p - 1 && filled[i] == false)
                            {
                                for (int q = row; q < hill.length && hill[q][i] == 0; q++)
                                {
                                    sum++;
                                }
                            }

                            filled[i] = true;
                        }

                    }
                }
            }
        }
    }

    return sum;


}

public static void main(String[] args)
{
    WaterInHill obj = new WaterInHill();
    int[] p = new int[]{4,2,4,1,5,3,16,6,17,19,4,13,5,3,10,10,13,6,2,1,5,15,13,19,16,9,13,1,7,18,20,13,9,7,2,10,8,18,4,7,5,8,10,13,7,18,19,2,19,8,10,10,17,6,6,20,20,11,10,11,13,9,7,1,10,5,12,16,10,7,15,13,12,10,1,1,4,2,16,10,20,17,11,19,19,20,9,10,17,9,18,8,10,18,8,19,16,17,3,1};
    int water = obj.getWaterFilling(p);
    System.out.println(water);  
}

}

I have a nice algorithm but not the programming experience to implement it easily. I'm not sure if any of the programs proffered as solutions here use it.

1. Create a water counter initiate at W=0

2. Take the list of numbers and add a parallel list initially of all 1's.

3. Scan the original list and for any duplicate values, combine them and add together the corresponding values of the parallel list.

4. Scan the original list for any number smaller than its neighbor.
   3a. Every time you find one, raise it to its lower neighbor. Multiply the amount raised by the value in the parallel list and add this to W. 3b. If the scan finds no number smaller than its neighbor display the value of W and end the program.
   

5. Repeat steps 2 and 3 until you are done.

Here's an example with a shorter list

List: 10 1 2 7 3 9 5 4 6 8

Steps 0 & 1:

• 10 1 2 7 3 9 5 4 6 8 $W=0$

• 1 1 1 1 1 1 1 1 1 1

Step 2 find no duplicates. Step 3

• 10 2 2 7 7 9 5 5 6 8 $W= 0 + 1 + 4 + 1 =6$

• 1 1 1 1 1 1 1 1 1 1

Step 2

• 10 2 7 9 5 6 8 $W=6$

• 1 2 2 1 2 1 1

Step 3

• 10 7 7 9 6 6 8 $W=6+ 5*2 + 1*2 =18$
• 1 2 2 1 2 1 1

Step 2

• 10 7 9 6 8 W=18

• 1 4 1 3 1

Step 3

• 10 9 9 8 8 $W=18 + 2*4 + 2*3 =32$

• 1 4 1 3 1

Step 2

• 10 9 8 $W=32$
• 1 5 4

Step 3 finds no numbers in the original list smaller than its neighbor so the program ends and outputs $W=32$

A significantly more compact solution than those I've seen here. The thought behind it is similar to Marta Reece's idea: Find the smaller one of the maximums of the subarrays to the left and right of the current position, subtract the current value from that, and if this gives a positive value, add it to a running total.

If, like me, you are on a crusade against the Zen of Python and think, "This returns one number, shouldn't it be one expression?", I've also provided an ultra-compressed version (yes, I sometimes code this way).

Both give the correct answer, $\boxed{791}$ .

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def water(array):
    total = 0
    for i in range(1, len(array) - 1):
        diff = min(max(array[:i]), max(array[i + 1:])) - array[i]
        total += max(diff, 0)
    return total

def to_list(numbers):
    return [int(x) for x in numbers.split(" ")]

print(water(to_list("4 2 4 1 5 3 16 6 17 19 4 13 5 3 10 10 13 6 2 1 5 15 13 19 16 9 13 1 7 18 20 13 9 7 2 10 8 18 4 7 5 8 10 13 7 18 19 2 19 8 10 10 17 6 6 20 20 11 10 11 13 9 7 1 10 5 12 16 10 7 15 13 12 10 1 1 4 2 16 10 20 17 11 19 19 20 9 10 17 9 18 8 10 18 8 19 16 17 3 1")))

1
2
3
4
5
6
7

def water(array):
    return sum(max(min(max(array[:i]), max(array[i + 1:])) - array[i], 0) for i in range(1, len(array) - 1))

def to_list(numbers):
    return [int(x) for x in numbers.split(" ")]

print(water(to_list("4 2 4 1 5 3 16 6 17 19 4 13 5 3 10 10 13 6 2 1 5 15 13 19 16 9 13 1 7 18 20 13 9 7 2 10 8 18 4 7 5 8 10 13 7 18 19 2 19 8 10 10 17 6 6 20 20 11 10 11 13 9 7 1 10 5 12 16 10 7 15 13 12 10 1 1 4 2 16 10 20 17 11 19 19 20 9 10 17 9 18 8 10 18 8 19 16 17 3 1")))

C code with explained comments in this ideone link

Here's a nice way to solve it in python using itertools and comprehensions, while being relatively efficient:

from itertools import accumulate

hills = [4, 2, 4, 1, 5, 3, 16, 6, 17, 19, 4, 13, 5, 3, 10, 10, 13, 6, 2, 1, 5, 15,
    13, 19, 16, 9, 13, 1, 7, 18, 20, 13, 9, 7, 2, 10, 8, 18, 4, 7, 5, 8, 10, 13, 
    7, 18, 19, 2, 19, 8, 10, 10, 17, 6, 6, 20, 20, 11, 10, 11, 13, 9, 7, 1, 10, 
    5, 12, 16, 10, 7, 15, 13, 12, 10, 1, 1, 4, 2, 16, 10, 20, 17, 11, 19, 19, 20, 
    9, 10, 17, 9, 18, 8, 10, 18, 8, 19, 16, 17, 3, 1]

runningMax = list(accumulate(hills,max))
revRunningMax = list(reversed(list(accumulate(reversed(hills),max))))
filledHills = [min(x,y) for x,y in zip(runningMax, revRunningMax)]
water = [x-y for x,y in zip(filledHills, hills)]
print(sum(water))

Here’s the python code I used to solve the problem, I decided to go level by level and record the amount of empty spots that weren’t in the beginning or the ending spaces:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

array = [4, 2, 4, 1, 5, 3, 16, 6, 17, 19, 4, 13, 5, 3, 10, 10, 13, 6, 2, 1, 5, 15, 13, 19, 16, 9, 13, 1, 7, 18, 20, 13, 9, 7, 2, 10, 8, 18, 4, 7, 5, 8, 10, 13, 7, 18, 19, 2, 19, 8, 10, 10, 17, 6, 6, 20, 20, 11, 10, 11, 13, 9, 7, 1, 10, 5, 12, 16, 10, 7, 15, 13, 12, 10, 1, 1, 4, 2, 16, 10, 20, 17, 11, 19, 19, 20, 9, 10, 17, 9, 18, 8, 10, 18, 8, 19, 16, 17, 3, 1];
volume = 0;
for i in range(0, 21):
    count = 0;
    flag = False;
    for j in range(0, len(array)):
        if(array[j] >= i):
            flag = True;
            volume += count;
            count = 0;
        else:
            if(flag):
                count += 1; 
print(volume);

I decided to get one of the tallest peaks, and work from wither end up until reaching said peak. This avoids having to worry about reaching the end of the list and accidentally overlooking any lower valleys.

 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

var list = [4,2,...,3,1];
var result = 0;
var idMax = 0;
for(var i=0;i<list.length;i++){ //Finding the index of the first (furthest-left) highest peak (id 30, value 20)
   if(list[i]>list[idMax]){
      idMax=i;
   }
}
var i = 0;
while(i<idMax){ //Checking from the left-end up until the first highest peak
   var j = i+1;
   while(list[i]>list[j]){ //Adds the depth of each column until a column of equal or greater size is reached
      result+=list[i]-list[j];
      j++;
   }
   i=j; //Starts from the end of the previous valley
}
i = list.length-1;
while(i>idMax){ //Checking from the right-end up until the first highest peak
   var j = i-1;
   while(list[i]>list[j]){
      result+=list[i]-list[j];
      j--;
   }
   i=j;
}
return result;