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.
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
http://massivealgorithms.blogspot.com/2016/06/simulate-rain-in-1-meter-side-walk.html
Last updated