Trapping Rain Water

Gemfile

source "https://rubygems.org"

gem "minitest"

trappable_volume.rb

# 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.

def trappableVolume(depthMap)
  maxLeft = Array.new(depthMap.size, 0)
  maxRight = Array.new(depthMap.size, 0)

  maxObserved = depthMap[0]
  depthMap.each_with_index do |x, i|
    maxLeft[i] = maxObserved = [x, maxObserved].max
  end

  maxObserved = depthMap.last
  depthMap.to_enum.with_index.reverse_each do |x, i|
    maxRight[i] = maxObserved = [x, maxObserved].max
  end

  depthMap.zip(maxLeft, maxRight).collect do |a|
    [a[1], a[2]].min - a[0]
  end.reduce(0, :+)
end

trappable_volume_test.rb

require 'minitest/autorun'
require "./trappable_volume.rb"

class TrappableVolumeTest < Minitest::Test
  def test_null_fill
    depthMap = []
    assert_equal 0, trappableVolume(depthMap)
  end

  def test_zero_fill
    depthMap = [0]
    assert_equal 0, trappableVolume(depthMap)
  end

  def test_basic_fill
    depthMap = [2, 0, 2]
    assert_equal 2, trappableVolume(depthMap)
  end

  def test_other_basic_fill
    depthMap = [2, 0, 0, 2]
    assert_equal 4, trappableVolume(depthMap)
  end

  def test_more_fill
    depthMap = [3, 0, 0, 2, 0, 4]
    assert_equal 10, trappableVolume(depthMap)
  end

  def test_still_more_fill
    depthMap = [4, 0, 0, 2, 0, 3]
    assert_equal 10, trappableVolume(depthMap)
  end

  def test_tricky_unblocked_end
    depthMap = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    assert_equal 6, trappableVolume(depthMap)
  end
end