Skip to content

Instantly share code, notes, and snippets.

@joist joist/Puddles.java
Last active Dec 26, 2015

Embed
What would you like to do?
My naive solution to a programmer puzzle I saw on hackernews. https://news.ycombinator.com/item?id=6639839 edit: Added the smart way of doing it too
public class Puddles
{
public static void main(String[] args) throws Exception
{
//set heights, need 2 or more
int[] groundheights = {2, 5, 1, 2, 3, 4, 7, 7, 6};
String gh = "Ground heights: ";
for (int i = 0; i<groundheights.length; i++)
{
if (i == 0) {
gh += groundheights[i];
} else {
gh += ", " + groundheights[i];
}
}
System.out.println(gh);
System.out.println("water: " + doDumb(groundheights));
System.out.println("water: " + doSmart(groundheights));
}
public static int doDumb(int[] groundheights)
{
//calculate water sheding to the left
int[] watershedleftheights = new int[groundheights.length];
watershedleftheights[0] = groundheights[0];
for (int i = 1; i<groundheights.length; i++)
{
if (groundheights[i] > watershedleftheights[i-1])
{
watershedleftheights[i] = groundheights[i];
} else {
watershedleftheights[i] = watershedleftheights[i-1];
}
}
//calculate water shedding to the right
int[] watershedrightheights = new int[groundheights.length];
watershedrightheights[groundheights.length-1] = groundheights[groundheights.length-1];
for (int i = groundheights.length-2; i>-1; i--)
{
if (groundheights[i] > watershedrightheights[i+1])
{
watershedrightheights[i] = groundheights[i];
} else {
watershedrightheights[i] = watershedrightheights[i+1];
}
}
//calc the volumes
int watervolume = 0;
for (int i = 0; i<groundheights.length;i++)
{
int lowestwatershed;
if (watershedleftheights[i] < watershedrightheights[i])
{
lowestwatershed = watershedleftheights[i];
} else {
lowestwatershed = watershedrightheights[i];
}
if (lowestwatershed > groundheights[i])
{
watervolume += lowestwatershed - groundheights[i];
}
}
return watervolume;
}
public static int doSmart(int[] groundheights)
{
//set the trace from left
int shedleftpointer = 0;
int shedlefttraceheight = 0;
//set the trace from right
int shedrightpointer = groundheights.length-1;
int shedrighttraceheight = 0;
int watervolume = 0;
//until the tracers overlap
while (shedleftpointer <= shedrightpointer)
{
//update the lower tracer, to prevent adding too much to watervolume
if (shedlefttraceheight < shedrighttraceheight)
{
//do left
if (shedlefttraceheight > groundheights[shedleftpointer])
{
//if watershed tracer larger than the current groundheight
//then water will pool in the cell, so add the volume
watervolume += shedlefttraceheight - groundheights[shedleftpointer];
} else {
//otherwise bump up the trace height or set it the same
shedlefttraceheight = groundheights[shedleftpointer];
}
shedleftpointer++;
} else {
//do right
if (shedrighttraceheight > groundheights[shedrightpointer])
{
watervolume += shedrighttraceheight - groundheights[shedrightpointer];
} else {
shedrighttraceheight = groundheights[shedrightpointer];
}
shedrightpointer--;
}
}
return watervolume;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.