Created
October 6, 2017 03:14
-
-
Save jasonkuhrt/43a4c3db726ce71f11cffaa5dc87577a to your computer and use it in GitHub Desktop.
falling-water.js
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Falling water | |
// Calculate the area of sum of areas of water that would be captured in | |
// valleys of water along a series of constant-width variable-height columns. | |
// The geometry is grid based meaning there are no curves in this world. | |
const log = console.log | |
const sumPools = (cs) => { | |
let start = null | |
let end = null | |
let currentPoolArea = 0 | |
let areaSum = 0 | |
for (let i=0; i < cs.length; i++) { | |
// Detect pool ending | |
if (start !== null && (i === cs.length - 1 || cs[start] <= cs[i])) { | |
end = i | |
// Detect pool starting | |
} else if (start === null && cs[i] < cs[i-1]) { | |
start = i - 1 | |
currentPoolArea += cs[start] - cs[i] | |
// Detect pool content | |
} else if (start !== null) { | |
currentPoolArea += cs[start] - cs[i] | |
} | |
log(start, end, currentPoolArea) | |
// Once we have found a pool, compute its size and | |
// reset our state so that we can continue searching | |
if (start !== null && end !== null) { | |
log("computing pool of gross size %s", currentPoolArea) | |
// Water will only rise as high as the lowest column, | |
// therefore find the rectangle between start<>end above | |
// said min and subtract it from the pool | |
let overflowW = end - (start === 0 ? 1 : start) | |
let overflowH = | |
(cs[start] > cs[end] ? cs[start] : cs[end]) // max | |
- | |
(cs[start] > cs[end] ? cs[end] : cs[start]) // min | |
let overflowArea = overflowH * overflowW | |
// log('overflowW x overflowH', overflowW, overflowH) | |
// log('overflowArea', overflowArea) | |
areaSum += currentPoolArea - overflowArea | |
currentPoolArea = 0 | |
start = null | |
end = null | |
} | |
} | |
return areaSum | |
} | |
const test = (testCases) => { | |
testCases.forEach((c, i) => { | |
log("case #%s ==> %s === %s", i, sumPools(c.input), c.output) | |
}) | |
} | |
test([ | |
// // zero cases | |
// { input: [0], output: 0 }, | |
// { input: [1,1], output: 0 }, | |
// { input: [1,2,3,4,5], output: 0 }, | |
// // trivial case, first fall appears to make start = i0 (10) | |
// { input: [10,1,1,10], output: 18 }, | |
// // harder, see how start = i1 (5) here, not i0, depends on end | |
// { input: [10,5,0,0,5], output: 10 }, | |
// // two trivial pools | |
// { input: [10,1,1,10,1,1,10], output: 36 }, | |
// // two harder pools | |
// { input: [10,5,0,0,5,5,4,0,0,4], output: 18 }, | |
{ input: [10,0,5,0,2], output: 7 }, | |
]) | |
module.exports = sumPools |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment