Skip to content

Instantly share code, notes, and snippets.

@speric
Last active March 4, 2016 20:54
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save speric/134697dd05b5938bdf07 to your computer and use it in GitHub Desktop.
Histogram Solution

Solution

defmodule HistogramCup do
  @moduledoc """
  You are given an input list whose each element represents the height of a line towers.
  The width of every tower is 1. It starts raining. How much water is collected between the towers?

  Input: [1,5,3,7,2] , Output: 2 units
  Explanation: 2 units of water collected between towers of height 5 and 7

     *
     *
   *w*
   *w*
   ***
   ****
  *****
  """

  @doc """
  total_water returns the total unit amount of water held by the towers in the given list

  iex(1)> list = [1,5,3,7,2]
  [1, 5, 3, 7, 2]
  iex(2)> HistogramCup.total_water(list)
  2
  """
  @spec total_water(list) :: number
  def total_water(list) do
    total_water(list, 0) + total_water(Enum.reverse(list), 0)
  end

  defp total_water([head | tail], acc) do
    trough = Enum.take_while(tail, &(&1 <= head))
    if trough == tail, do: acc, else: total_water(new_tail(trough, tail), acc + volume(head, trough, 0))
  end

  defp volume(start, [head | tail], accumulator) do
    volume(start, tail, (start - head) + accumulator)
  end

  defp volume(_, _, accumulator), do: accumulator

  defp new_tail(trough, tail), do: Enum.drop(tail, Enum.count(trough))
end

Test

defmodule HistogramCupTest do
  use ExUnit.Case
  @target HistogramCup
  
  test "Handles a cup where there's no inside" do
    input = [3, 7, 7, 2]
    assert @target.total_water(input) == 0
  end

  test "Sums the water held for a small example" do
    input = [1, 5, 3, 7, 2]
    assert @target.total_water(input) == 2
  end

  test "Sums the water held for a large example" do
    input = [2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1]
    assert @target.total_water(input) == 35
  end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment