Raindrop on Sidewalk

Description

Model raindrops falling on a sidewalk (sidewalk is 1m and raindrops are 1cm). How could we know when the sidewalk is completely wet.

Source: https://www.glassdoor.com/Interview/Model-raindrops-falling-on-a-sidewalk-sidewalk-is-1m-and-raindrops-are-1cm-if-I-remember-correctly-How-could-we-know-whe-QTN_1329533.htm

OR

you have 1 meter sidewalk, and randomly generate rain, the rain is 1 cm. simulate how many rain drops to cover all the 1 meter [-0.01~1].

Source: https://www.1point3acres.com/bbs/thread-176388-1-1.html

Solution

TreeSet Approach

Not sure why, but seems hard to converge (cover).

public class RaindropSidewalk {
    private TreeSet<double[]> sidewalk = new TreeSet<>(new Comparator<double[]>() {
        @Override
        public int compare(double[] a, double[] b) {
            return Double.compare(a[0], b[0]);
        }
    });

    public void addRainDrop(double center) {
        double[] range = new double[] {center - 0.5, center + 0.5};

        double[] left = sidewalk.floor(range);
        if (left != null && left[1] > range[0]) {
            range[0] = left[0];
            sidewalk.remove(left);
        }

        double[] right = sidewalk.ceiling(range);
        if (right != null && right[0] < range[1]) {
            range[1] = right[1];
            sidewalk.remove(right);
        }
        sidewalk.add(range);
    }

    public boolean isCovered() {
        if (sidewalk.size() == 1) {
            if (sidewalk.first()[0] <= 0 && sidewalk.first()[1] >= 100) {
                return true;
            }
        }
        return false;
    }

    public void printSideWalk() {
        System.out.println("--" + sidewalk.size());
        for (double[] rain: sidewalk) {
            System.out.println("::" + Arrays.toString(rain));
        }
    }
    public void print() {
        System.out.println("size ::" + sidewalk.size());
    }
    public static void main(String[] args) {
        Random rand = new Random();
        RaindropSidewalk s = new RaindropSidewalk();
        int count = 0;
        for (int rain = 0; rain <= 100; rain++)  {
            s.addRainDrop(rain);
            s.printSideWalk();
        }
        /*
        while (!s.isCovered()) {
            double rain = (double)rand.nextInt(101) + rand.nextDouble();
            s.addRainDrop(rain);
            count++;

            if (count % 1e5 == 0) {
                s.print();
            }
            if (count % 1e7 == 0) {
                s.printSideWalk();
            }
            if (count > 1e9) {
                break;
            }
        }
        System.out.println("count: " + count);
        */
    }
}

Interval Approach

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=176388&extra=&page=1

public class RainDrop {
        static class Interval {
                double left = 0, right = 0.01;

                boolean isWet() { 
                        return left >= right;
                }
        }

        public static void main(String[] args) {
                simulateRainDrop();
        }

        public static 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;
                                        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;
                                        if (ileft > sidewalk[idx].left) {
                                                sidewalk[idx].left = ileft;
                                                if (sidewalk[idx].isWet())
                                                        ++wetCnt;
                                        }
                                }
                        }
                }
                System.out.println(cnt);
        }
}

Another Interval approach

class Main {
    //start is the distance to 0, end is the distance to 1
    //both start and end fall into [0, 1]
    public class Interval {
        public double start;
        public double end;
        public boolean isCovered;
        public Interval() {
            this.start = 0;
            this.end = 0;
            this.isCovered = false;
        }
    }
    public class SideWalk {
        private int curOccupiedCount;
        public int count;
        public Interval[] intervals;
        public SideWalk(int count) {
            this.curOccupiedCount = 0;
            this.count = count;
            this.intervals = new Interval[count];
            for (int i = 0; i < this.count; i++) {
                this.intervals[i] = new Interval();
            }
        }
        // 1.68..2.68
        public void DropRain(double start, double end) {
            int index = (int) Math.floor(start);
            if (index >= 0) {
                if (Math.abs(start - index) < 0.00001) {
                    if (!this.intervals[index].isCovered) {
                        this.curOccupiedCount++;
                        this.intervals[index].isCovered = true;
                    }
                    return;
                }
                if (!this.intervals[index].isCovered) {
                    this.intervals[index].end = Math.max(this.intervals[index].end, index + 1 - start);
                    if (this.intervals[index].start + this.intervals[index].end >= 1) {
                        this.intervals[index].isCovered = true;
                        this.curOccupiedCount++;
                    }
                }
            }
            if (index + 1 < this.count) {
                if (!this.intervals[index + 1].isCovered) {
                    this.intervals[index + 1].start = Math.max(this.intervals[index + 1].start, end - index - 1);
                    if (this.intervals[index + 1].start + this.intervals[index + 1].end >= 1) {
                        this.intervals[index + 1].isCovered = true;
                        this.curOccupiedCount++;
                    }
                }
            }
        }
        public boolean hasOccupied() {
            return this.curOccupiedCount == this.count;
        }
    }

    public void SimulateRainDrop() {
        SideWalk sideWalk = new SideWalk(100);
        while (!sideWalk.hasOccupied()) {
            Random random = new Random();
            double start = random.nextInt(101) - 1 + random.nextDouble();
            double end = start + 1;
            sideWalk.DropRain(start, end);
            System.out.println(start + ", " + end);
        }
        System.out.println("occupied!");
    }
    public static void main(String[] args) {
        Main m = new Main();
        m.SimulateRainDrop();
    }
}

Reference

https://www.glassdoor.com/Interview/Model-raindrops-falling-on-a-sidewalk-sidewalk-is-1m-and-raindrops-are-1cm-if-I-remember-correctly-How-could-we-know-whe-QTN_1329533.htm

http://massivealgorithms.blogspot.com/2016/06/simulate-rain-in-1-meter-side-walk.html

https://www.1point3acres.com/bbs/thread-176388-1-1.html