Skip to content

Instantly share code, notes, and snippets.

@JBarna
Last active June 17, 2018 18:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JBarna/0e0cd6dac3de0d8937c946e1f7e3f160 to your computer and use it in GitHub Desktop.
Save JBarna/0e0cd6dac3de0d8937c946e1f7e3f160 to your computer and use it in GitHub Desktop.
const hill = [4, 2, 4, 1, 5, 3, 16, 6, 17, 19, 4, 13, 5, 3, 10, 10, 13, 6, 2, 1, 5, 15,
13, 19, 16, 9, 13, 1, 7, 18, 20, 13, 9, 7, 2, 10, 8, 18, 4, 7, 5, 8, 10, 13,
7, 18, 19, 2, 19, 8, 10, 10, 17, 6, 6, 20, 20, 11, 10, 11, 13, 9, 7, 1, 10,
5, 12, 16, 10, 7, 15, 13, 12, 10, 1, 1, 4, 2, 16, 10, 20, 17, 11, 19, 19, 20,
9, 10, 17, 9, 18, 8, 10, 18, 8, 19, 16, 17, 3, 1]
// now traverse
const previousPoints = []
var waterUnits = 0
for (var currentIndex = 0; currentIndex < hill.length; currentIndex++) {
let currentSpot = hill[currentIndex],
previousSpot = hill[currentIndex - 1],
nextSpot = hill[currentIndex + 1];
function findPreviousMatchingPoint(height) {
for (var previousPointsIt = 0; previousPointsIt < previousPoints.length; previousPointsIt++) {
const previousPointIndex = previousPoints[previousPointsIt]
const previousPointHeight = hill[previousPointIndex]
if (previousPointHeight >= height) {
return previousPointIndex
}
}
}
// if the spot previous was lower than us, we need to calculate the captured water
if (previousSpot != null && previousSpot < currentSpot) {
// for each unit of increase, find the most recent point that matches that height
// and calculate the water units based on distance of that point
for (let unitHeight = previousSpot + 1; unitHeight <= currentSpot; unitHeight++) {
const matchingPointIndex = findPreviousMatchingPoint(unitHeight)
if (matchingPointIndex != null) {
waterUnits += ((currentIndex - matchingPointIndex) - 1)
}
}
}
// detect if this is a point and store it for future use if it is
if (previousSpot != null && previousSpot < currentSpot ||
nextSpot != null && nextSpot < currentSpot) {
previousPoints.unshift(currentIndex)
}
}
console.log(previousPoints, waterUnits)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment