falling-water.js

main.js

// 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