Skip to content

Instantly share code, notes, and snippets.

@jbosse

jbosse/rain.ex

Last active February 6, 2021 03:38
Show Gist options
  • Save jbosse/bea80d713e6362b331b8c94c1df12db9 to your computer and use it in GitHub Desktop.
Save jbosse/bea80d713e6362b331b8c94c1df12db9 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jbosse revised this gist Feb 6, 2021. No changes.
  2. jbosse revised this gist Feb 6, 2021. 1 changed file with 44 additions and 0 deletions.
    44 changes: 44 additions & 0 deletions rain_v4.ex
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,44 @@
    defmodule Rain do

    def trap(heights) do
    state = %{
    heights: heights,
    answer: 0,
    index_l: 0,
    index_r: Enum.count(heights) - 1,
    max_l: 0,
    max_r: 0,
    }
    loop(state)
    end

    defp loop(%{index_l: il, index_r: ir} = state) when il < ir do
    loop_state = state
    |> Map.put(:height_l, Enum.at(state.heights, il))
    |> Map.put(:height_r, Enum.at(state.heights, ir))
    scan(loop_state)
    end
    defp loop(%{answer: a}), do: a

    defp scan(%{height_l: hl, height_r: hr, max_l: ml} = loop_state) when hl < hr and hl >= ml do
    new_loop_state = %{loop_state | index_l: loop_state.index_l + 1, max_l: hl}
    loop(new_loop_state)
    end

    defp scan(%{height_l: hl, height_r: hr} = loop_state) when hl < hr do
    trapped = loop_state.max_l - hl
    new_loop_state = %{loop_state | index_l: loop_state.index_l + 1, answer: loop_state.answer + trapped}
    loop(new_loop_state)
    end

    defp scan(%{height_r: hr, max_r: mr} = loop_state) when hr >= mr do
    new_loop_state = %{loop_state | index_r: loop_state.index_r - 1, max_r: hr}
    loop(new_loop_state)
    end

    defp scan(loop_state) do
    trapped = loop_state.max_r - loop_state.height_r
    new_loop_state = %{loop_state | index_r: loop_state.index_r - 1, answer: loop_state.answer + trapped}
    loop(new_loop_state)
    end
    end
  3. jbosse revised this gist Feb 6, 2021. 1 changed file with 44 additions and 0 deletions.
    44 changes: 44 additions & 0 deletions rain_v3.ex
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,44 @@
    defmodule Rain do

    def trap(heights) do
    answer = 0
    index_l = 0
    index_r = Enum.count(heights) - 1
    max_l = 0
    max_r = 0
    loop(heights, answer, index_l, index_r, max_l, max_r)
    end

    defp loop(heights, answer, index_l, index_r, max_l, max_r) when index_l < index_r do
    height_l = Enum.at(heights, index_l)
    height_r = Enum.at(heights, index_r)
    scan(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r)
    end
    defp loop(_heights, answer, _index_l, _index_r, _max_l, _max_r), do: answer

    defp scan(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) when height_l < height_r and height_l >= max_l do
    new_index_l = index_l + 1
    new_max_l = height_l
    loop(heights, answer, new_index_l, index_r, new_max_l, max_r)
    end

    defp scan(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) when height_l < height_r do
    new_index_l = index_l + 1
    trapped = max_l - height_l
    new_answer = answer + trapped
    loop(heights, new_answer, new_index_l, index_r, max_l, max_r)
    end

    defp scan(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) when height_r >= max_r do
    new_index_r = index_r - 1
    new_max_r = height_r
    loop(heights, answer, index_l, new_index_r, max_l, new_max_r)
    end

    defp scan(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) do
    new_index_r = index_r - 1
    trapped = max_r - height_r
    new_answer = answer + trapped
    loop(heights, new_answer, index_l, new_index_r, max_l, max_r)
    end
    end
  4. jbosse revised this gist Feb 6, 2021. 1 changed file with 35 additions and 0 deletions.
    35 changes: 35 additions & 0 deletions rain_v2.ex
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,35 @@
    defmodule Rain do

    def trap(heights) do
    answer = 0
    index_l = 0
    index_r = Enum.count(heights) - 1
    max_l = 0
    max_r = 0
    count(heights, answer, index_l, index_r, max_l, max_r)
    end

    defp count(heights, answer, index_l, index_r, max_l, max_r) when index_l < index_r do
    height_l = Enum.at(heights, index_l)
    height_r = Enum.at(heights, index_r)
    cond do
    height_l < height_r ->
    cond do
    height_l >= max_l ->
    count(heights, answer, index_l + 1, index_r, height_l, max_r)
    true ->
    trapped = max_l - height_l
    count(heights, answer + trapped, index_l + 1, index_r, max_l, max_r)
    end
    true ->
    cond do
    height_r >= max_r ->
    count(heights, answer, index_l, index_r - 1, max_l, height_r)
    true ->
    trapped = max_r - height_r
    count(heights, answer + trapped, index_l, index_r - 1, max_l, max_r)
    end
    end
    end
    defp count(_heights, answer, _index_l, _index_r, _max_l, _max_r), do: answer
    end
  5. jbosse created this gist Feb 6, 2021.
    36 changes: 36 additions & 0 deletions rain.ex
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,36 @@
    defmodule Rain do

    def trap(heights) do
    answer = 0
    index_l = 0
    index_r = Enum.count(heights) - 1
    max_l = 0
    max_r = 0
    count(heights, answer, index_l, index_r, max_l, max_r)
    end

    defp count(heights, answer, index_l, index_r, max_l, max_r) when index_l < index_r do
    height_l = Enum.at(heights, index_l)
    height_r = Enum.at(heights, index_r)
    count(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r)
    end
    defp count(_heights, answer, _index_l, _index_r, _max_l, _max_r), do: answer

    defp count(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) when height_l < height_r and height_l >= max_l do
    count(heights, answer, index_l + 1, index_r, height_l, max_r)
    end

    defp count(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) when height_l < height_r do
    trapped = max_l - height_l
    count(heights, answer + trapped, index_l + 1, index_r, max_l, max_r)
    end

    defp count(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) when height_r >= max_r do
    count(heights, answer, index_l, index_r - 1, max_l, height_r)
    end

    defp count(heights, answer, index_l, index_r, max_l, max_r, height_l, height_r) do
    trapped = max_r - height_r
    count(heights, answer + trapped, index_l, index_r - 1, max_l, max_r)
    end
    end
    13 changes: 13 additions & 0 deletions rain_test.exs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,13 @@
    defmodule RainTest do
    use ExUnit.Case

    test "calculates trapped rain" do
    assert Rain.trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
    assert Rain.trap([4,2,0,3,2,5]) == 9
    assert Rain.trap([4,2,0,5,5,3]) == 6
    assert Rain.trap([0,1,2,1,2,1,2,3,4,3,2,1,2,0]) == 3
    assert Rain.trap([5,0,5,5,5,5,1,5,5,2,5,5]) == 12
    assert Rain.trap([1,2,3,4,5,4,3,4,5,5,4,3,2,1,2,3]) == 8
    assert Rain.trap([5,5,5,5,5]) == 0
    end
    end