Water Trapping - Dynamic Programming

trapping_water.js

// Given n non-negative integers representing an elevation map where the width
// of each bar is 1, compute how much water it is able to trap after raining.
const test = require('tape');

const trapped = bars => {
  let index = 0;
  let left_wall = 0;
  let right_wall = 0;
  const last = bars.length - 1;
  let area = 0;
  while (index < last) {
    const current = bars[index];
    left_wall = bars[left_wall] > current ? left_wall : index;
    const omg = bars.slice(index + 1, last).findIndex((bar, i) => bar >= left_wall && i > 1 && bars[i-1] < bar && bar > bars[i+1]);
    console.log(omg)
    right_wall = omg === -1 ? last : omg + 1 + index;
    area += findAreaUnderWater(bars.slice(left_wall, right_wall + 1));
    index = right_wall;
    continue;
  }
  return area;
};

const findAreaUnderWater = list => {
  const len = list.length;
  const left = list[0];
  const right = list[len - 1];
  const between = list.slice(1, len - 1);
  const water_line = Math.min(left, right);
  return between
    .map(bar => (water_line > bar ? water_line - bar : 0))
    .reduce((a, b) => a + b, 0);
};

test('Trapping Water', t => {
  t.equals(trapped([0, 0, 0]), 0);
  t.equals(trapped([1, 0, 1]), 1);
  t.equals(trapped([1, 0, 1, 0, 2, 5, 1, 3]), 4);
  t.equals(trapped([0, 1, 0, 5, 4, 0, 1]), 2);
  t.equals(trapped([1, 5]), 0);
  t.equals(trapped([]), 0);
  t.equals(trapped([0, 1, 2, 5, 4, 3, 1]), 0);
  t.equals(trapped([2,0,1,2]), 3);
  // t.equals(trapped([5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5]), 25);
  t.end();
});