Programming Challenge - It's raining!

C++

It's pretty ugly, but I think I have a decent algorithm.

The code takes two lines as input: the number of lakes N and the depths of each of the N lakes.

It outputs a line with a float (long double), which is its calculated time for when all the lakes will fill.

The code's algorithm:

1. Group together lakes that take an ascending amount of time to fill (e.g. 1 hr, 2 hr, 3 hr, 2 hr, 4 hr get grouped into (1,2,3), (2,4))
2. "Fuse" the lakes into one "super-lake" by summing volumes and rate of filling
3. If the first super-lake takes longer to fill than all the ones after (or is the only lake), print the time it takes for that super-lake to fill and end the program
4. Otherwise, repeat step 1 with these super-lakes

Argument for Correctness:

The fusion process groups together lakes that will collectively fill first before overflowing into another lake/group of lakes. This group can then be considered as a single unit, as it will first fill itself and then go on to fill other groups with its flow rate.

If it gets flowed into by another group, that means that it took longer to fill than the previous group and will fuse with it in the next round of fusion.

If the first group takes the longest to fill, then all the groups afterwards are irrelevant (they will do their own thing and fill first before the first group fills) and so the first group's time to fill is unequivocally the time it takes for the lakes to all fill.

I can't find any test cases that break this code, so I hope others can either corroborate its correctness or prove it wrong with some cool input.

Runtime Complexity:

It looks like O(n^2) in the worst case (put lakes in descending order of depth except the last one, which should have the maximum depth).

Upon finding this worst case I look forward to seeing an O(n log n) or better solution if someone cleverer than me feels up to it.

Code:
Try it online!

#include <vector>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long double ld;
int main() {
	int n;
	scanf("%d ",&n);
	vii v;
	while(n--) {
		int t;
		scanf("%d ",&t);
		v.push_back(ii(t,1));
	}
	while(v.size() > 1) {
		vii w;
		int ct = v[0].second;
		int vol = v[0].first;
		for(int i=1;i<v.size();i++) {
			ld a = (ld)v[i].first/(ld)v[i].second;
			ld b = (ld)v[i-1].first/(ld)v[i-1].second;
			if(a<b) {
				w.push_back(ii(vol,ct));
				ct=0;
				vol=0;
			} 
			ct+=v[i].second;
			vol+=v[i].first;
		}
		w.push_back(ii(vol,ct));
		ld mx=0;
		int mi=0;
		for(int i=0;i<w.size();i++) {
			ld dv = (ld)w[i].first/(ld)w[i].second;
			if(dv > mx) {mx=dv;mi=i;}
		}
		if(mi == 0) {
			v.assign(w.begin(),w.begin()+1);
		} else {
			v = w;
		}
	}
	ld dv = (ld)v[0].first/(ld)v[0].second;
	printf("%Lf\n",dv);
}

I'm a novice programmer so this was very challenging for me, still had fun though!

I wrote the code in python in a single function rain() that receives 3 arguments that represent the capacity of each lake.

def rain(a,b,c):

   L1, L2, L3 = 0, 0, 0
   t = 0.0
   high = max(a,b,c)
   low = min(a,b,c)
   mid = (a + b + c) - (high + low)

   for i in range(high):

       if L1 < low and L2 < mid and L3 < high:
           L1 += 1
           L2 += 1
           L3 += 1
           t += 1

       else:

           if L1 == low:
               if L2 < mid:
                   L2 += 1
                   if L2 == mid:
                       L3 += 1

                   else:
                       L2 += 1

                   L3 += 1

               elif L3 < high:
                   if (L3 + 3) > high:
                       t += (high - L3) / 3
                       return t
                   else:
                       L3 += 3

               else:
                   return t

           else:
               L1 += 1

           t += 1

The problem though is that my code only work for 3 lakes, and it assumes that the lakes are positioned so that the smallest one is first and the largest one is last. Because the way I wrote it the largest lake doesn't spill off into any other lake regardless of it's position.

Had a lot of fun with this challange! I almost thought that I couldn't do it at first but I surprised myself :)

I have nothing to contribute except to say these programming challenges are great. It's amazing to see what people come up with.

Here's a way to do it in Emacs Lisp:

(defstruct lake
  quantity capacity)

(defun rainfall (rainfall &rest lakes)
  "Return number of rainfall periods required to apply RAINFALL to LAKES until no capacity remains."
  (cl-loop for remaining-capacity = (apply #'fill-lakes rainfall 0 lakes)
           collect (-map #'copy-lake lakes) into periods
           until (<= remaining-capacity 0)
           finally return (list :hours (length periods)
                                :periods periods
                                :remaining-capacity remaining-capacity)))

(defun fill-lakes (rainfall overflow &rest lakes)
  "Return remaining capacity in LAKES after distributing RAINFALL and OVERFLOW."
  (-let* (((lake . lakes) lakes)
          (remaining-capacity (- (lake-capacity lake) (lake-quantity lake)))
          (new-water (+ rainfall overflow))
          (overflow (max 0 (- new-water remaining-capacity))))
    (cl-incf (lake-quantity lake) (- new-water overflow))
    (cl-decf remaining-capacity (- new-water overflow))
    (if lakes
        (+ (apply #'fill-lakes rainfall overflow lakes) remaining-capacity)
      remaining-capacity)))

(rainfall 1
          (make-lake :capacity 1 :quantity 0)
          (make-lake :capacity 3 :quantity 0)
          (make-lake :capacity 5 :quantity 0))
;; =>
;; (list :hours 3
;;       :periods ((#s(lake 1 1)
;;                    #s(lake 1 3)
;;                    #s(lake 1 5))
;;                 (#s(lake 1 1)
;;                    #s(lake 3 3)
;;                    #s(lake 2 5))
;;                 (#s(lake 1 1)
;;                    #s(lake 3 3)
;;                    #s(lake 5 5)))
;;       :remaining-capacity 0)

At first this seems like a fairly easy problem, but then you realize that you can run into multiple segmented sub-systems of filled lakes separated by unfilled lakes. Getting the correct fractional hours can be tricky because of this.

With that in mind, I've come up with a strategy that I have yet to implement:

1. Segment the lake system into individual sub-systems such that the sub-systems are consecutive filled lakes punctuated by an unfilled lake (or no lake if no unfilled lakes exist). In terms of a regular expression, you can represent the entire system as (1*0?)+ where 1 represents a filled lake and 0 represents an unfilled lake.
2. For each individual sub-system, compute the overflow rate and add this to the base flow rate to get a final fill rate for the unfilled lake at the end of the sub-system.
3. For each individual sub-system, compute the projected time required to fill the remainder of the unfilled lake given the previously computed fill rate.
4. Grab the lake(s) with the smallest computed remaining fill time and mark it/them as filled. For all remaining unfilled lakes, multiply this time by their computed fill rates and update their fill levels.
5. Add the computed time to your total time.
6. Repeat the above until all lakes are filled.

I'll be implementing this later when I'm not at work :)

Edit: By the way, awesome challenge!

I observed that N contiguous lakes of increasing capacity can be treated as one lake with a rainfall of N since the last lake is guaranteed to fill last. This only works moving from left to right. As such, you can chunk lakes according to this property. My assumption is that the lake on the far right will spill over into the center of the earth or something (will never fill the lake to the left of it). In my submission, I move from right to left chunking the lakes whenever the previous one has a smaller capacity, computing their "equivalent" fill times as they are chunked.

When the process is finished, the list of chunked lakes is guaranteed to be in ascending order of fill time (even if it only has one term) and the left-most lake-chunk will be the longest fill time.

#!/usr/bin/python3
import sys

class Lakes:
    capacities = []
    
    def __init__(self, capacities):
        self.capacities = capacities
    
    def Solve(self):
        #since the flow rates are all initialized to 1, the fill times are equal to the capacities
        fill_times = self.capacities.copy() 
        flow_rates = [1] * len(self.capacities)
        capacities = self.capacities.copy()

        print(fill_times)
        print(flow_rates)
        print(capacities)

        #index N-2 to 0 moving backwards
        for i in range(len(self.capacities)-2,-1,-1):
            #keep chunking the lake at the current index with lakes to the right if they have a >= fill time
            while (fill_times[i] <= fill_times[i+1]):
                #compute the equivalent fill time using the previous chunk's fill rate and capacity
                fill_times[i] = (capacities[i] + capacities[i+1])/(flow_rates[i] + flow_rates[i+1])
                
                #remove the i+1 chunk after it has been combined with the current chunk
                fill_times.pop(i+1)
                #do the same for the flow rates and capacities
                flow_rates[i] = flow_rates.pop(i+1) + flow_rates[i]
                capacities[i] = capacities.pop(i+1) + capacities[i]
                
                #break out of the while loop when chunking causes the current index to be the rightmost
                if(len(fill_times) == (i+1)):
                    break
            #print("---" + str(i) + "---")
            #print(fill_times)
            #print(flow_rates)
            #print(capacities)
        
        #the maximum fill time is always the left-most index
        return fill_times[0]

def main():
    capacities = []
    for i in range(1,len(sys.argv)):
        capacities.append(int(sys.argv[i]))
        
    L = Lakes(capacities)
    print(L.Solve())

if __name__ == "__main__":
    main()

C:\...\Lakes>lakes 1 3 4
[1, 3, 4]
[1, 1, 1]
[1, 3, 4]
---1---
[1, 3.5]
[1, 2]
[1, 7]
---0---
[2.6666666666666665]
[3]
[8]
2.6666666666666665

edit: commented the code

I made a function in python which takes a list of the capacities of the lakes, from left to right, and returns the number to fill (in linear time I think)

#!/usr/bin/python3
def rain(lakes):
    # the time it takes to fill the system of previous lakes
    filltime = 0
    # the amount of overflow from the previous lakes in [filltime]
    spill = 0
    for (i,capacity) in enumerate(lakes):
        # number of previous lakes including current one
        num = i + 1
        # we have the spill from the previous lakes and for each second in filltime
        # one additional liter
        level = spill + filltime
        if level > capacity:
            # since we were already full, the filltime stays the same
            # but the spill is now the amount we are over the capacity
            spill = level - capacity
        else:
            # the spill is now zero, since we are still collecting in this lake
            spill = 0
            # but the time to fill up is larger
            # at each second after [filltime], we get [num] liters of water
            # so the remaining time is just the remaining capacity divided by [num]
            filltime += (capacity - level)/num
    return filltime

The way this works is by first calculating the time to fill the first (n-1) lakes and the amount of water that spilled over into the last lake in that time.
The previous lakes are all full after that time, so from that point on there are n liters of water flowing into the last lake each hour.

• If it has already overflowed in that time, we can just add the number of hours to the overspill (since each hour, one liter is added) and substract the capacity of the current lake from it to get the new overspill
• If it has not overflowed, the remaining time to fill it is simply the remaining capacity in the lake divided by n

I have not really tested the code for errors, so it probably has some errors.