rain array

You have an array of integers, for example: [ 9 8 7 6 2 ].

You graph the values of the array on the y-axis and the index on the x-axis as a bar graph.

Rain falls on the graph. The water collects in any valleys in the graph, and falls off any edges.

In the example array above no water collects because it all falls to the left and right. In [ 3 1 3 ] We get 2 units of water since it collects in the valley between the two 3 bars.

Devise an algorithm to determine how much water is collected by an array. 

Input: Array of integers

Output: Water collected when rain falls on graph

def rain(l=[]):
    result,  leftmaxSoFar, rightmaxSoFar  = 0,  0, 0
    leftMaxList = [0 for i in range(len(l))]
    rightMaxList = [0 for i in range(len(l))]
    capacity = [0 for i in range(len(l))]

    for i in range(len(l)):
        leftMaxList[i] =  leftmaxSoFar
        rightMaxList[len(l) -1 -i]  = rightmaxSoFar
        if l[i] > leftmaxSoFar :
           leftmaxSoFar = l[i]
        if l[len(l) -1 -i] > rightmaxSoFar:
           rightmaxSoFar = l[len(l) -1 -i]
            
    for i in range(len(l)):
        capacity[i] =  min(leftMaxList[i], rightMaxList[i]) -l[i]
        result = result if capacity[i] < 0 else result+capacity[i]
    return result

print rain([3, 1, 3])

print rain( [ 9, 8, 7, 6, 2 ])

Banana Boat Problem

Problem

I am 100 miles from my destination market along a river. To start with, I have 300 bananas and a boat that can hold me and up to 100 bananas. I would like to deliver as many bananas as possible to the market. I may safely leave bananas at the edge of the river and load/unload bananas at no cost. However, when I row with bananas in my boat I end up eating one banana (from among those in the boat) for every one mile (either upstream or downstream). What is the maximum number of bananas that can be delivered to the destination market?

Approaches to Solution by KRU, SRU, SRI, and SUR

Knowledge, Reason, and Understanding (KRU)

Kru's approach is  to reason  about the problem using background knowledge in English and Math to arrive at understanding of the solution.

1. I gain no advantage by taking less bananas in the boat when the boat can carry more because the bananas to be eaten do not depend on the bananas carried but only on the miles traveled.
2. There are no trips less than a mile.
3. Fully loaded boat trips are preferable though not always possible. This follows from one and the fact that in between at some mile, the number of bananas available  may turn out to be less than the capacity of the boat.

Exploring Solutions

Planning just one trip straight to the destination results in no bananas to sell. I load the boat with 100 bananas and I have none left by the time I reach the market as I have to eat one per mile.

I could make a stop at 50 miles  to drop off a few bananas and return to the origin for more. But the boat can only hold a 100 and I would use them up making my way to the 50 mile mark and back in the first 2 round trips. The last trip from origin to 50 mile mark is upstream only and going back is not necessary because no bananas are left at the origin. I bring 50 bananas to the 50 mile mark. After reaching the destination, I still have none left to sell because I need to eat 50 bananas for traveling 50 miles.

Stopping at 25 mile marks
What if I moved all the bananas to the 25 mile first, then the 50, 75 and 100 mile marks?

I load the boat fully and head to the 25 mile mark. The round trip costs 50 bananas but I manage to leave 50 at the shore and make it back to the origin. I can repeat the same process: eat 50 bananas in transit and add 50 bananas to the 25 mile mark. On the final trip, I eat only 25 bananas, because there is no reason to return to the origin. At this point, I have 50 + 50 + 75  bananas at the 25 mile mark.

Getting to the 50 mile mark from the 25 mile mark costs me 50 bananas for the first boat load and 25 bananas for the second. This leaves me with 100 bananas at mile 50. Now I can make it to the market and sell 50.

Can I do better?

Stopping at 10 mile marks
To get to the first 10 mile mark, it costs 50 bananas leaving me with 250. From there to the 20 mile mark, it is another 50 in cost leaving me with 200. To the 30 mile mark it costs only 30 leaving 170. To the 40 mile mark  I can make it with 140. Similarly, I have 110 at the 50 mile mark. If I insist on taking all the 110 bananas, I have to make one round trip and one upstream trip eating 30 bananas and getting only 80 to the 60 mile mark.  It is possible to do better by setting aside 10 bananas and taking just one upstream trip resulting in 90 bananas at 60 mile mark. I can make it to the market with only 50 to sell.

This guess-and-check methodology seems stuck at 50.
Why make an arbitrary assumption about intermediate stops?
Let me explore  answers to a fundamental question.

What is the best thing to do for the first mile?

How many fully loaded  boat trips are possible? 3. It is possible to reach the first mile with 5 bananas loss, The 2 round trips plus one upstream trip have to be taken. More trips would be wasteful. I lose more bananas. Less trips will result in less bananas being moved. The same reasoning applies to the second mile.

How many miles with loss of 5 per mile?
20. After that it is only loss of 3 per mile.

How far can we push at the 3 mile rate?
33 more miles. At the end of 53 miles 101 bananas are left. we have 47 miles to go to the destination and 101 bananas, then we can start with only 100 bananas and get only 53 to the destination. The best we can do at the end of 54 miles is 99. And now it is all the way to market having 53 bananas to sell.

Is there a better solution?
At every mile, there is no better way of getting more bananas to the next mile. That is sufficiently convincing argument. That is a proof of optimal nature of the solution found.

How to prove that 54 is not optimal?
To have    54 for the market I need to have a minimum of 100 bananas at  54 mile.
To have  100 bananas at  54 mile I need to have a minimum of 199 bananas at  21 mile.
To have  199 bananas at  21 mile I need to have a minimum of 204 bananas at  20 mile.
To have  204 bananas at  20 mile I need to have a minimum of 299 bananas at  1 mile.
To have  299 bananas at  1 mile I need to have a minimum of 306 bananas at  0 mile.

54 to the market is not even feasible given that at starting point I have only 300 bananas.
Similar argument holds for any number greater than 54.
52 or less is definitely feasible but not optimal.
53 is maximum achievable subject to constraints of the problem.

What can I learn from this one successful numerical example to solve the problem with different numbers for total bananas, boat capacity,  and distance ?
High School Algebra is sufficient.
I can think of  a few general statements using \(t\), \(c\), \(d\) for total bananas, boat capacity,  and distance respectively.  (t / c) stands for integer division. (1/2) is 0 and (5/3) is 1.

1. If origin is the destination, then all \(t\) bananas are for sale.
2. If a partially loaded boat trip is not necessary because it is not worth making a roundtrip for bananas less than 3,  then only  \(c * (t / c)\) bananas are carried in \(( 2 * (t / c) - 1)\) trips.  \(c * (t / c) - ( 2 * (t / c) - 1)\) will reach the next mile.  This rule is a generalization of my experience with 101 bananas left at 53 mile mark and 300 bananas from the origin. 
3. If a partially loaded  boat trip is necessary then all the  bananas are carried in \(( 2 * (t / c) + 1)\) trips and \(t  - ( 2 * (t / c) + 1)\)  bananas will reach the next mile. This rule is a generalization of my experience  with 99 bananas left at 54 mile mark and 295 bananas left at 1 mile mark. 

Suitable Recursion Unit (SRU)

Sru's approach is to represent Kru's understanding  using Recursion. Notice the straightforward translation of Kru's English and Math into  python 2.7 function.

def bananaBoat(t, c, d):
    if d == 0:
        return t
    if c*(t/c)==t or c*(t/c) == t - 1 or c*(t/c) == t - 2 :
        return  bananaBoat(c*(t/c) - (2*(t / c) - 1), c, d - 1)
    else:
        return  bananaBoat(t - (2*(t/c)+1), c, d - 1)
        
print   bananaBoat(16, 3, 2)     #Answer is  3
print   bananaBoat(45, 15, 10)   #Answer is 13  
print   bananaBoat(300, 100, 100)#Answer is 53

Startup Relevant Ideas (SRI)

Sri is always interested in problem solving ideas relevant for society at large. Given mobile phones for all involved, banana farmers and boat operators how can the startup provide a reliable service of letting the participants to know who is available where using Google cloud service?  What is all needed to make this little python program into industrial-strength software?

Symbolic-Numeric Unification Research (SUR)

A lot of research results are available from Economics, Operations Research, and Computer Science about the use of heuristics. We implicitly used the free disposal assumption economists typically make.

A discrete optimization problem

What is the minimum of the absolute values of a sorted array of  integers?
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 }; the answer is 2.
 The code is based on a slight twist to binary search.

public class MinAbs {
public  int cal(int[] a ){
return recurscal( a,  0,  a.length - 1);
}

private  int recurscal(int[] a,  int begin, int end){
assert (end >= begin);
   if (end == begin) return Math.abs(a[begin]);
if ((end - begin) == 1)
return Math.min(Math.abs(a[begin]), Math.abs(a[end]));

final int middle = begin + (end - begin)/2;

//  on downward slope, the new interval is middle to end

if  (   (Math.abs(a[middle - 1] ) >= Math.abs(a[middle]))
     && (Math.abs(a[middle + 1] ) <= Math.abs(a[middle]))
       )   return recurscal(a,  middle, end);

//  on upward slope, the new interval is begin to middle.
if  (   (Math.abs(a[middle - 1] ) <= Math.abs(a[middle]))
     && (Math.abs(a[middle + 1] ) >= Math.abs(a[middle]))
)return recurscal(a,  begin, middle);

// No more testing. Middle is the answer.
return Math.abs(a[middle]);

}

public static void main(String[] args) {
int[] ia = {-38, -20, -10, -5, -2, 3, 4, 5 };

MinAbs mia = new MinAbs();
                System.out.println(mia.cal(ia));
}

}