Simulate rain

Simulate rain drops on a 1 meter wide walk way. Each rain drop is going to cover 1 centimeter of the walkway. Assume that a rain drop randomly falls from any position within the meter and falls straight down.
Find out how many rain drops it takes to wet the whole walkway.

Solution

Obviously, the number of rain drop it takes to wet the whole walkway is not fixed because of the randomness in rain generation.

Rain Generation

What we can do is to generate the center of each rain drop with the built-in random function between [0, 1.00001] meter.
If a drop occurs at position 0.921, the area that gets wet will be [0.921 - 0.005, 0.921 + 0.005] = [0.916, 0.926].
If a second drop falls at position 0.918, the area that gets will be [0.913, 0.923].
Then merge the overlapped areas. At this point [0.913, 0.926] of the 1-meter-walkway is wet.
The moment that [0,1] the whole meter is wet, the simulation can stop and return the count of raindrops by far.

Walkway

So how to abstract the walkway in our code to make it easier to keep track of the wet area?

One way is to keep track all the intervals of rain drop areas and merge them every round until eventually left with a single interval [0,1].
The process to merge intervals is going to take O(logN) time if we apply binary search on finding where the current rain drop locates in the set of intervals.

A better way is to have an array of size 100 in which each element notes 1 centimeter on the walkway.

class Centimeter {
    double left;
    double right;
}

Initialize left = 0 and right = 0.01. [left, right] is the dry area in the centimeter.
The walkway can be represented as

Centimeter[] walkway = new Centimeter[100];

When the first raindrop falls on [0.916, 0.926],
find the the 91st centimeter which is walkway[90] and change it’s right dry boundary to 0.006;
find the 92nd centimeter walkway[91] and change it’s left dry boundary to 0.006.

When a second drop falls on [0.913, 0.923],
find walkway[90] and change right boundary to 0.003;
find walkway[91] and see if walkway[91].left is greater than 0.003. Since it is, which means [0, 0.003] has been wet already, so do NOT update walkway[91].left.

Whenever a centimeter has a left boundary >= right boundary, the whole centimeter is wet through. Then the count of wet centimeters can increment.

When the count of wet centimeters hits 100, the whole walkway is wet through.

Implementation

class Interval {
    double left = 0, right = 0.01;
    boolean isWet() {
        return left >= right;
    }
}
public void simulateRainDrop() {
    Interval[] sidewalk = new Interval[100];
    for (int i = 0; i < 100; i++) {
        sidewalk[i] = new Interval();
    }
    int cnt = 0, wetCnt = 0;
    while (wetCnt < 100) {
        ++cnt;
        double p = Math.random();
        double left = p - 0.005;
        double right = p + 0.005;
        if (left >= 0) {
            int idx = (int) (left / 0.01);
            if (!sidewalk[idx].isWet()) {
                double iright = left - idx * 0.01;  //update seg[i].right with left bound of rain
                if (iright < sidewalk[idx].right) {
                    sidewalk[idx].right = iright;
                    if (sidewalk[idx].isWet())
                        ++wetCnt;
                }
            }
        }
        if (right <= 1) {
            int idx = (int) (right / 0.01);
            if (!sidewalk[idx].isWet()) {
                double ileft = right - idx * 0.01;//update seg[i + 1].left with right bound of rain
                if (ileft > sidewalk[idx].left) {
                    sidewalk[idx].left = ileft;
                    if (sidewalk[idx].isWet())
                        ++wetCnt;
                }
            }
        }
    }
    System.out.println(cnt);
}