Pour water on a landscape

Description of the problem

Rain is pouring for a defined duration on a landscape that consists of multiple columns, each with its own height.

Rules

1. There is an invisible border to the left and to the right of the provided landscape with a height of infinity.
2. Each hour of rain pours one unit of rain into each column.
3. The rain flows from a higher to a lower column. If the column to the left and to the right are both lower, then the rain distributes evenly between those two.

Test solver

Reasoning for the solution

1. Bottom up

At first glance it might seem logical to start pouring the rain from above one hour at a time and distribute it like that.
But if the landscape is slowly filled from the bottom up, many many edge cases will never occur and the problem will be a lot easier to implement.

2. Create regions

Instead of working with each column, I chose to group columns of the same height together into a region.
This will reduce the number of elements that need checking and allows me to easily calculate the water capacity of a region and also if the water should flow somewhere from this element.

3. Gather the rain in the trenches/ local minima

If the landscape will get bigger, it will be very inefficient to pour the water into each column.
Instead it would be easier to find all local minima in the landscape and divide the rain among those minima in the beginning.
This of course costs some time in the beginning of the calculation, especially if the worst case should occur: A zigzag landscape.

4. Shortcut if a landscape overflows

I can skip a lot of calculation if I add a case that checks in the beginning if more water will be poured into the landscape than it can take.

Code

The code for solving this problem is split into two files: region.js and solver.js.

• region.js contains the prototype for each Region instance with the necessary functions to pour rain into itself or another region and merge it with neighbors to create a bigger region. Also it contains the specific border, a region with a height of POSITIVE_INFINITY.
• solver.js contains the code to create the double-linked list of regions from the entered landscape array, and to pour all the rain into the landscape.

To solve an example landscape the file sample.js can be executed, e.g. from the console

npm install
npm start

Output

It will rain for 2 hours on [1, 5, 6, 4] expect as result: [6, 6, 6, 6]
It has rained for 2 hours on [1, 5, 6, 4], result is [6, 6, 6, 6]
regions:
  Region:LOCAL_MINIMUM { start: 0, end: 3, width: 4, height: 6, rain: 0 }

The code is available as a zip file. For usage on this page, the files are combined to water.bundle.js.

Tests

To run the tests of the solution, execute:

npm install
npm test

Output

Initialization tests
√ No rain means result equals initial landscape

One hour rain sessions:
√ It will rain for 1 hours on [1, 5] expect as result: [3, 5]
√ It will rain for 1 hours on [1, 5, 3] expect as result: [2.5, 5, 4.5]
√ It will rain for 1 hours on [4, 2] expect as result: [4, 4]
√ It will rain for 1 hours on [1, 5, 5, 4] expect as result: [4, 5, 5, 5]
√ It will rain for 1 hours on [1, 5, 5, 1] expect as result: [3, 5, 5, 3]
√ It will rain for 1 hours on [1, 6, 6, 4, 6] expect as result: [4, 6, 6, 6, 6]
√ It will rain for 1 hours on [1, 5, 5, 4, 5] expect as result: [5, 5, 5, 5, 5]
√ It will rain for 1 hours on [1, 5, 5, 4, 5, 6] expect as result: [5.2, 5.2, 5.2, 5.2, 5.2, 6]
√ It will rain for 1 hours on [1, 3, 4] expect as result: [3.5, 3.5, 4]
√ It will rain for 1 hours on [1, 3, 4, 4] expect as result: [4, 4, 4, 4]
√ It will rain for 1 hours on [1, 5, 4] expect as result: [3, 5, 5]
√ It will rain for 1 hours on [4, 5, 5, 1] expect as result: [5, 5, 5, 4]
√ It will rain for 1 hours on [1, 3, 1] expect as result: [2.5, 3, 2.5]
√ It will rain for 1 hours on [1, 2, 1] expect as result: [2.3333333333333335, 2.3333333333333335, 2.3333333333333335]

Two hour rain sessions:
√ It will rain for 2 hours on [1, 5] expect as result: [5, 5]
√ It will rain for 2 hours on [1, 5, 4] expect as result: [5.333333333333333, 5.333333333333333, 5.333333333333333]
√ It will rain for 2 hours on [1, 5, 5, 4] expect as result: [5.75, 5.75, 5.75, 5.75]
√ It will rain for 2 hours on [1, 5, 6, 4] expect as result: [6, 6, 6, 6]
√ It will rain for 2 hours on [4, 6, 5, 1] expect as result: [6, 6, 6, 6]
√ It will rain for 2 hours on [1, 5, 7, 4] expect as result: [5.5, 5.5, 7, 7]
√ It will rain for 2 hours on [4, 2] expect as result: [5, 5]
√ It will rain for 2 hours on [6, 2] expect as result: [6, 6]
√ It will rain for 2 hours on [1, 5, 5, 1] expect as result: [5, 5, 5, 5]
√ It will rain for 2 hours on [1, 6, 5, 1] expect as result: [4, 6, 5.5, 5.5]
√ It will rain for 2 hours on [1, 3, 4] expect as result: [4.666666666666667, 4.666666666666667, 4.666666666666667]
√ It will rain for 2 hours on [1, 3, 5, 7, 11] expect as result: [6.333333333333333, 6.333333333333333, 6.333333333333333, 7, 11]

Random rain amounts
√ It will rain for 5 hours on [5, 5] expect as result: [10, 10]
√ It will rain for 100 hours on [701, 384] expect as result: [701, 584]
√ It will rain for 100000 hours on [300, 300, 250000] expect as result: [150300, 150300, 250000]

Completely overflown landscapes
√ It will rain for 2 hours on [1, 5], expect a height of 5
√ It will rain for 3 hours on [4, 2], expect a height of 6
√ It will rain for 5 hours on [1, 5, 5, 1], expect a height of 8
√ It will rain for 2 hours on [1, 3, 4], expect a height of 4.666666666666667

34 passing (153ms)