# Programming Challenge - It's raining!

Hi everyone, it's been 12 days since last programming challenge. So here's another one. The task is to make an algorithm that'll count how long would it take to fill system of lakes with water.

It's raining in the forest. The forest is full of lakes, which are close to each other. Every lake is below the previous one (so 1st lake is higher than 2nd lake, which is higher than 3rd lake). Lakes are empty at the beginning, and they're filling at rate of 1l/h. Once a lake is full, all water that'd normally fall into the lake will flow to the next lake.

For example, you have lakes A, B, and C. Lake A can hold 1 l of water, lake B can hold 3 l of water and lake C can hold 5 l of water. How long would it take to fill all the lakes?
After one hour, the lakes would be: `A (1/1), B (1/3), C(1/5)`. After two hours, the lakes would be: `A(1/1), B(3/3), C(2/5)` (because this hour, B received 2l/h - 1l/h from the rain and 1l/h from lake A). After three hours, the lakes would be: `A(1/1), B(3/3), C(5/5)`. So the answer is `3`. Please note, that the answer can be any rational number. For example if lake C could hold only 4l instead of 5, the answer would be `2.66666...`.

Hour 0:

``````
\            /
----(A)----
\                /
\              /
\            /
----(B)----
\           /
\         /
\       /
|       |
|       |
--(C)--
``````

Hour 1:

``````
\============/
----(A)----
\                /
\              /
\============/
----(B)----
\           /
\         /
\       /
|       |
|=======|
--(C)--
``````

Hour 2:

``````            ==============
\============/           |
----(A)----            |
\================/
\==============/
\============/
----(B)----
\           /
\         /
\       /
|=======|
|=======|
--(C)--
``````

Hour 3:

``````            ==============
\============/           |
----(A)----            |             ========
\================/       |
\==============/        |
\============/         |
----(B)----           |
\===========/
\=========/
\=======/
|=======|
|=======|
--(C)--
``````

Good luck everyone! Tell me if you need clarification or a hint. I already have a solution, but it sometimes doesn't work, so I'm really interested in seeing yours :-)

1. wirelyre
(edited )
This is very cool. Here is a Haskell solution. Try it online! import Data.Ratio main = print . fill \$ map lake [1, 3, 5] data Lake = Lake { unfilled :: Rational -- litres , rate :: Rational --...
• Exemplary

This is very cool.

Here is a Haskell solution. Try it online!

``````import Data.Ratio

main = print . fill \$ map lake [1, 3, 5]

data Lake = Lake { unfilled :: Rational -- litres
, rate :: Rational -- litres per hour
}

lake :: Rational -> Lake
lake depth = Lake {unfilled=depth, rate=1}

fill :: [Lake] -> Rational
fill [] = 0
fill ls = time + fill (spill 0 (map fill' ls))
where
time = minimum . map (\lake -> unfilled lake / rate lake) \$ ls
fill' Lake {unfilled=u, rate=r} = Lake {unfilled=u-r*time, rate=r}

spill :: Rational -> [Lake] -> [Lake]
spill _ [] = []
spill incoming (Lake {unfilled=0, rate=r} : ls) = spill (incoming+r) ls
spill incoming (Lake {unfilled=u, rate=r} : ls) = Lake {unfilled=u, rate=incoming+r} : spill 0 ls
``````

Since the answer can be any rational number, we'll use the built-in `Ratio` library. Haskell will promote literal integers like `0` and `1` into `Rational`s automatically.

At any given time, for each lake, we only care about

1. how much is unfilled; and
2. how quickly water is flowing into it.
``````import Data.Ratio

data Lake = Lake { unfilled :: Rational -- litres
, rate :: Rational -- litres per hour
}
``````

At the start, each lake has a flow rate of 1 litre per hour, so we'll make a convenience function to construct a lake from its volume.

``````lake :: Rational -> Lake
lake depth = Lake {unfilled=depth, rate=1}
``````

Finally, we'll declare a function `fill`, which takes a list of lakes and finds out how long it takes to fill them. Now we can write a main function.

``````fill :: [Lake] -> Rational
main = print . fill \$ map lake [1, 3, 5]
``````

Here's the plan: At every time step, we find out how long until some lake is filled next. Then, for each lake, we decrease `unfilled` by the appropriate amount. Finally, we clean up the list of lakes by removing lakes that are completely full.

But wait! A lake that is full needs to spill incoming water to the next lake. We need one final auxiliary function, `spill`. `spill` takes a list of lakes, and removes lakes that are completely full, but adds water intake rates forward into lakes that are not yet full. That is, if a lake is full, all of the incoming water is carried forward to the next lake.

``````spill :: Rational -> [Lake] -> [Lake]
spill _ [] = []
spill incoming (Lake {unfilled=0, rate=r} : ls) = spill (incoming+r) ls
spill incoming (Lake {unfilled=u, rate=r} : ls) = Lake {unfilled=u, rate=incoming+r} : spill 0 ls
``````

This is a common form for recursive functions. Let's step through each case.

1. Base case: If there are no lakes remaining (`[]`), no need to do anything.
2. Otherwise, we have at least one lake. If the lake is empty (`unfilled=0`), all of the incoming water spilled over so far, plus all of the water that used to fill this lake, overflows forward. Discard the lake.
3. Otherwise, we have at least one lake and the lake is not empty. Keep the lake, and increase the incoming water rate. Zero water overflows forward (because any incoming water will fill this lake first).

Now the rest is straightforward. For the base case, it takes no time to fill no lakes.

``````fill :: [Lake] -> Rational
fill [] = 0
``````

How long until the next lake is filled to capacity? (A little math: each lake fills in `unfilled / rate` hours. The minimum of those is the next to fill.)

``````  where
time :: Rational
time = minimum . map (\lake -> unfilled lake / rate lake) \$ ls
``````

Once that amount of time has passed (once the next lake has filled to capacity), what are the water levels in a single lake?

``````  where
fill' :: Lake -> Lake
fill' Lake {unfilled=u, rate=r} = Lake {unfilled=u-r*time, rate=r}
``````

Finally, we recurse. After `time` has passed, we update each lake (`map fill' ls`), spill over empty lakes (`spill 0 _`, because `0` litres per hour overflow into the first lake), and add `time` to however long it takes to fill the new list of lakes.

``````fill ls = time + fill (spill 0 (map fill' ls))
``````
2. 
Hvv
(edited )
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...

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.second;
int vol = v.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.first/(ld)v.second;
printf("%Lf\n",dv);
}
``````
1. Emerald_Knight
You know, it never occurred to me to merge my lakes together during each pass. That drastically simplifies things conceptually. Great idea there!

You know, it never occurred to me to merge my lakes together during each pass. That drastically simplifies things conceptually. Great idea there!

3. 
mb3077
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...

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 :)

1. 
mb3077
(edited )
After some thinking I came up with better method that actually works with any amount of lakes: def rain(a): #Recieve list 'a' that contains the volumes of the lakes. b =  * len(a) #Create new...

After some thinking I came up with better method that actually works with any amount of lakes:

``````def rain(a):            #Recieve list 'a' that contains the volumes of the lakes.
b =  * len(a)    #Create new list 'b' with the same length as 'a' and fill it with zeros
load = 0            #Load is basically "Spill". If a lake can't contain a certain amount of water, that amount gets added to the load or "Spill"
t = 0.0             #The cumulative time. This gets returned by the function
while True:
for i in range(len(b)):
if b[i] == a[i]:                    #Check if the lake (b[i]) is full.
else:
b[i] += 1                       #If the lake is not full, add the rain to it.
if (b[i] + load) > a[i]:        #Check if the current load (spill from previous lakes) can fit into the lake
if i == (len(b) - 1):       #Check if we are on the last lake in the list
t += (a[i] - b[i] + 1) / len(b)     #Because the last lake is almost full, it will take less than an hour to fill it due to the incoming-
return t                            #-spill from the other lakes. Calculate that time and add it to the total and return it.
else:
load -= a[i] - b[i]                 #If we are not on the last lake, then simply add as much water that can fit and move on
b[i] = a[i]
else:
b[i] += load                            #If the lake can take the entire load, then add it to the lake.
if i == (len(b) - 1) and b[i] == a[i]:  #After this, check if we are on the last lake, and if the lake is full. If it is then return t.
t += 1
return t
t += 1                                  #Add an hour to the time.
``````

Again the problem is that it counts on the last lake to be the largest one. In order to fix that you need to split the list into sub lists that end with the largest local number. This was done very elegantly by others in this thread.

edit: fixed some mistakes

1. 
alphapapa
It would be much easier to understand the code if the variables were named descriptively.

It would be much easier to understand the code if the variables were named descriptively.

1. 
mb3077
Yeah sorry about that, I have a bad habit of not naming my variables properly.. I added some explanations to the code so hopefully it's more understandable!

Yeah sorry about that, I have a bad habit of not naming my variables properly..
I added some explanations to the code so hopefully it's more understandable!

1 vote
1. 
alphapapa
(edited )
The explanations help, but why not just name the variables more descriptively? e.g. instead of saying "t is the time variable," why not just name it time? Instead of "load is basically spill," why...

The explanations help, but why not just name the variables more descriptively? e.g. instead of saying "t is the time variable," why not just name it `time`? Instead of "load is basically spill," why not name it `spillover`?

And instead of, "Create new list 'b' with the same length as 'a' and fill it with zeros," why not give `b` a descriptive name and explain the purpose? Everyone who knows Python can see that it's making a new list and filling it with zeroes, but what's the purpose of doing that?

Do you see what I mean? :)

BTW, the comments and code would be easier to follow if you put the comments in the code rather than beside it. It helps visualize the structure and break the code into parts, like headings in a long document.

One Python-related suggestion: `for i in range(len(x))` is not idiomatic Python. Python isn't C. :) Try `for lake in lakes`, and look up Iterators. ;)

1 vote
1. mb3077
Yeah I just added the comments out of pure lazyness and because I wanted to make sure I myself fully understand what I wrote, although in retrospect your way would've required less effort. Thanks...

Yeah I just added the comments out of pure lazyness and because I wanted to make sure I myself fully understand what I wrote, although in retrospect your way would've required less effort.

Thanks for the feedback!

1 vote
2. Emerald_Knight
Hey, don't worry too much about not being able to handle all of the cases. When you're first learning, just handling the special case you did here can be incredibly difficult. Never be discouraged...

Hey, don't worry too much about not being able to handle all of the cases. When you're first learning, just handling the special case you did here can be incredibly difficult. Never be discouraged if you can't solve the whole problem. Solve what you can now, and if you're feeling up to it later, come back when you're a little more experienced and take another crack at the problem.

Any part that you can solve will still help you become a better programmer :)

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

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

5. alphapapa
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...

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)
``````
6. 
Emerald_Knight
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...

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.
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!

1. Emerald_Knight
Alright, without further ado, here's my solution: <?php class Lake { private \$capacity; private \$fill_level = 0; public function __construct(\$capacity) { \$this->capacity = \$capacity; } public...

Alright, without further ado, here's my solution:

``````<?php

class Lake {

private \$capacity;
private \$fill_level = 0;

public function __construct(\$capacity) {
\$this->capacity = \$capacity;
}

public function dump() {
\$this->fill_level = 0;
}

public function fill(\$fill_amount) {
\$this->fill_level = min(\$this->capacity, \$this->fill_level + \$fill_amount);
}

public function isFilled() {
return \$this->fill_level == \$this->capacity;
}

public function calculateTimeToFill(\$fill_rate) {
\$space_remaining = \$this->capacity - \$this->fill_level;

return \$space_remaining / \$fill_rate;
}
}

class LakeSystem {

private \$lakes = array();
private \$fill_rate;

public function __construct(\$fill_rate = 1) {
\$this->setFillRate(\$fill_rate);
}

public function setFillRate(\$fill_rate) {
\$this->fill_rate = \$fill_rate;
}

\$lake = new Lake(\$capacity);
array_push(\$this->lakes, \$lake);
}

public function dropLakes() {
\$this->lakes = array();
}

public function emptyAll() {
foreach(\$this->lakes as \$lake) {
\$lake->dump();
}
}

private function isSystemFilled() {
foreach(\$this->lakes as \$lake) {
if(!\$lake->isFilled()) {
return false;
}
}

return true;
}

private function segmentSystem() {
\$segments = array();

// A segment is any contiguous sequence of filled lakes of any length ending with an unfilled lake.
\$segment = array();
foreach(\$this->lakes as \$lake) {
array_push(\$segment, \$lake);

// Nice side effect: if the last lake added is filled, its corresponding segment won't be added!
if(!\$lake->isFilled()) {
array_push(\$segments, \$segment);
\$segment = array();
}
}

return \$segments;
}

private function calculateSegmentFillRate(\$segment) {
return count(\$segment) * \$this->fill_rate;
}

private function calculateSegmentFillTime(\$segment) {
\$total_fill_rate = \$this->calculateSegmentFillRate(\$segment);
\$last_lake = array_pop(\$segment);

return \$last_lake->calculateTimeToFill(\$total_fill_rate);
}

public function calculateSystemFillTime() {
\$total_fill_time = 0;
while(!\$this->isSystemFilled()) {
// Apparently PHP_FLOAT_MAX wasn't added until 7.2? Seriously?
\$smallest_time_to_fill = PHP_INT_MAX;

// Time calculation.
\$segments = \$this->segmentSystem();
foreach(\$segments as \$segment) {
\$segment_fill_time = \$this->calculateSegmentFillTime(\$segment);
\$smallest_time_to_fill = min(\$segment_fill_time, \$smallest_time_to_fill);
}

// Sub-system filling.
foreach(\$segments as \$segment) {
\$segment_fill_amount = \$this->calculateSegmentFillRate(\$segment) * \$smallest_time_to_fill;
\$last_lake = array_pop(\$segment);
\$last_lake->fill(\$segment_fill_amount);
}

// Time accumulation.
\$total_fill_time += \$smallest_time_to_fill;
}

return \$total_fill_time;
}
}

\$lakes = array(1, 3, 5);

\$lake_system = new LakeSystem();
foreach(\$lakes as \$lake) {
}

echo \$lake_system->calculateSystemFillTime();

?>
``````

I chose to add some additional configuration to allow for flexibility with e.g. rate of rainfall, as well as a number of helper methods that didn't actually end up getting used, but could be helpful for testing purposes. Once again, data validation is for chumps (or for people who don't do enough of it as part of their day job that they don't want to bother with it when they get home).

Seems to work after a few test cases. If you find any incorrect results, please tell me what inputs you used and I'll review for accuracy :)

7. 
determinism
(edited )
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....

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 =  * 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

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]


2.6666666666666665
``````

edit: commented the code

1. determinism
C:\...\Lakes>lakes 1 3 5 1 2 1 2 1 2 5 7 1 3 [1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 1, 3] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 1, 3] ---11--- [1, 3, 5, 1, 2, 1, 2,...
``````C:\...\Lakes>lakes 1 3 5 1 2 1 2 1 2 5 7 1 3
[1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 1, 3]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 1, 3]
---11---
[1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 2.0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 4]
---10---
[1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 2.0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
[1, 3, 5, 1, 2, 1, 2, 1, 2, 5, 7, 4]
---9---
[1, 3, 5, 1, 2, 1, 2, 1, 2, 6.0, 2.0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2]
[1, 3, 5, 1, 2, 1, 2, 1, 2, 12, 4]
---8---
[1, 3, 5, 1, 2, 1, 2, 1, 4.666666666666667, 2.0]
[1, 1, 1, 1, 1, 1, 1, 1, 3, 2]
[1, 3, 5, 1, 2, 1, 2, 1, 14, 4]
---7---
[1, 3, 5, 1, 2, 1, 2, 3.75, 2.0]
[1, 1, 1, 1, 1, 1, 1, 4, 2]
[1, 3, 5, 1, 2, 1, 2, 15, 4]
---6---
[1, 3, 5, 1, 2, 1, 3.4, 2.0]
[1, 1, 1, 1, 1, 1, 5, 2]
[1, 3, 5, 1, 2, 1, 17, 4]
---5---
[1, 3, 5, 1, 2, 3.0, 2.0]
[1, 1, 1, 1, 1, 6, 2]
[1, 3, 5, 1, 2, 18, 4]
---4---
[1, 3, 5, 1, 2.857142857142857, 2.0]
[1, 1, 1, 1, 7, 2]
[1, 3, 5, 1, 20, 4]
---3---
[1, 3, 5, 2.625, 2.0]
[1, 1, 1, 8, 2]
[1, 3, 5, 21, 4]
---2---
[1, 3, 5, 2.625, 2.0]
[1, 1, 1, 8, 2]
[1, 3, 5, 21, 4]
---1---
[1, 4.0, 2.625, 2.0]
[1, 2, 8, 2]
[1, 8, 21, 4]
---0---
[3.0, 2.625, 2.0]
[3, 8, 2]
[9, 21, 4]
3.0
``````
2. determinism
I think this could be augmented to consider surface area as an input parameter (to give different rainfall flow rates to each lake) with some minor modifications to the program. It would just have...

I think this could be augmented to consider surface area as an input parameter (to give different rainfall flow rates to each lake) with some minor modifications to the program. It would just have to pre-compute the fill times for each lake rather than assuming fill_time == capacity.

8. mironimous
(edited )
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...

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
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.