{{ message }}

Instantly share code, notes, and snippets.

# joist/Puddles.java

Last active Dec 26, 2015
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 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[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; } }