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

This is very cool.

Here is a Haskell solution. Try it online!

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

unfilled; andAt 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.

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.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, butaddswater 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.This is a common form for recursive functions. Let's step through each case.

`[]`

), no need to do anything.`unfilled=0`

), all of the incoming water spilled overso far, plus all of the water thatused to fill this lake, overflows forward.Discard the lake.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.

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.)Once that amount of time has passed (once the next lake has filled to capacity), what are the water levels in a single lake?

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.C++It's pretty ugly, but I think I have a decent algorithm.

The code takes two lines as input: the number of lakes

Nand 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: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!

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

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.

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

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

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

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

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!

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

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

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:

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*0?)+`

where`1`

represents a filled lake and`0`

represents an unfilled lake.I'll be implementing this later when I'm not at work :)

Edit: By the way, awesome challenge!

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

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

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.

edit: commented the code

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.

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)

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.

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