benchmark.exs

Mix.install([:benchee])

sum = 100

list = Enum.map(1..100, fn _ -> Enum.random(0..10) end)

defmodule Nikiiv do
  @moduledoc """
  * Implement a method that will determinate if exists a range of
  * non-negative elements in an array that sum up to a specific non-
  * negative number
  *
  * Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3
  * Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7)
  *
  """

  def solution([h | t], target_sum) do
    find_solution([h], t, h, target_sum)
  end

  defp find_solution(_, _, target_sum, target_sum) when target_sum > 0, do: :OK
  defp find_solution(_, [0 | _], _, 0), do: :OK

  defp find_solution(arr, [h | t], current_sum, target_sum) when current_sum < target_sum do
    current_sum = current_sum + h
    find_solution(arr ++ [h], t, current_sum, target_sum)
  end

  defp find_solution([h | t], right, current_sum, target_sum) when current_sum > target_sum do
    current_sum = current_sum - h
    find_solution(t, right, current_sum, target_sum)
  end

  defp find_solution([], [h | t], _, target_sum), do: find_solution([h], t, h, target_sum)

  defp find_solution(_, [], current_sum, target_sum) when current_sum != target_sum do
    :KO
  end

  defp find_solution([], [], _, _), do: :KO
end

defmodule Nikiiv2 do
  def solve_problem(arr, target_sum) do
    tarr = List.to_tuple(arr)
    size = Kernel.length(arr)
    current_sum = elem(tarr, 0)
    left = 0
    right = 0
    solve(tarr, size, left, right, current_sum, target_sum)
  end

  defp solve(_, _, left, right, target_sum, target_sum) when left <= right, do: :ok

  defp solve(tarr, size, left, right, _current_sum, target_sum) when left > right do
    right = left
    current_sum = elem(tarr, left)
    solve(tarr, size, left, right, current_sum, target_sum)
  end

  defp solve(tarr, size, left, right, current_sum, target_sum)
       when current_sum < target_sum and right < size - 1 do
    right = right + 1
    current_sum = current_sum + elem(tarr, right)
    solve(tarr, size, left, right, current_sum, target_sum)
  end

  defp solve(tarr, size, left, right, current_sum, target_sum)
       when current_sum > target_sum and left <= right and left < size - 1 do
    current_sum = current_sum - elem(tarr, left)
    left = left + 1
    solve(tarr, size, left, right, current_sum, target_sum)
  end

  defp solve(_, _, _, _, current_sum, target_sum) when current_sum != target_sum, do: nil
end

defmodule Tomekowal do
  @moduledoc """
  * Implement a method that will determinate if exists a range of
  * non-negative elements in an array that sum up to a specific non-
  * negative number
  *
  * Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3
  * Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7)
  *
  """

  def solution([h | t], target_sum) do
    # start by taking first element as the current sublist
    find_solution([h], t, h, target_sum)
  end

  # defp find_solution(current_sublist, rest_of_list, current_sum, target_sum)
  # if target sum is zero, we require zero number somewhere
  # it is not enough to simply say that zero element sublist has zero length
  # NOTE: that edge case should be clarified because it complicates simple recursion
  # in which empty range sums up to zero (even if there no zeros)

  # we've found the sublist!
  # NOTE: previous solution where `target_sum` was twice in parameters was perfectly fine and idiomatic
  # However, in this particular example, I wanted to see three `when` clauses with `==`, `<` and `>`
  defp find_solution(current_sublist, _rest_of_list, current_sum, target_sum)
       when current_sum == target_sum and length(current_sublist) > 0,
       do: :OK

  # we need more, so we take add first element from the reset to the current sublist
  # NOTE: this merges a case where the current sum is too low AND where current_sublist has zero elements and both current_sum and target_sum are 0
  defp find_solution(current_sublist, [h | t] = _rest_of_list, current_sum, target_sum)
       when current_sum <= target_sum do
    find_solution(current_sublist ++ [h], t, current_sum + h, target_sum)
  end

  # we are over target, so we drop first item from the current sublist
  defp find_solution([h | t] = _current_sublist, rest_of_list, current_sum, target_sum)
       when current_sum > target_sum do
    find_solution(t, rest_of_list, current_sum - h, target_sum)
  end

  defp find_solution(_, _, _, _), do: :KO
end

defmodule Stefanluptak do
  @doc """
      iex> Sublist.find([1, 2, 3], 3)
      0..1

      iex> Sublist.find([1, 7, 1, 1, 1, 5, 6, 1], 3)
      2..4

      iex> Sublist.find([0, 4, 5, 1, 8, 9, 12, 3, 1], 7)
      nil
  """
  def find(list, sum, offset \\ 0)
  def find([], _sum, _offset), do: nil

  def find([_head | tail] = list, sum, offset) do
    list
    |> Enum.scan(0, &Kernel.+/2)
    |> Enum.find_index(&(&1 == sum))
    |> case do
      nil ->
        find(tail, sum, offset + 1)

      index ->
        Range.new(offset, index + offset)
    end
  end
end

defmodule M100phlecs do
  def solution([num | rst], target) do
    q = :queue.new()
    find(rst, :queue.in(num, q), num, target)
  end

  defp find([], _, _, _), do: nil

  defp find([num | rst], q, sum, target) when sum == target do
    if :queue.is_empty(q), do: find(rst, :queue.in(num, q), num, target), else: :ok
  end

  defp find([num | rest], q, sum, target) when sum < target,
    do: find(rest, :queue.in(num, q), sum + num, target)

  defp find(lst, q, sum, target) when sum > target do
    {{:value, prev}, q} = :queue.out(q)
    find(lst, q, sum - prev, target)
  end
end

defmodule Eksperimental do
  @moduledoc """
  Implement a function that will determinate if exists a range consecutive of
  non-negative elements in an list, that sum up to a specific non-negative number.
  """

  @type element :: non_neg_integer()
  @type element_list :: nonempty_list(element())
  @type sum :: non_neg_integer()

  defguardp is_non_neg_integer(term) when is_integer(term) and term >= 0

  @doc """
  Determinate whether consecutive number of non-negative integers in an list
  sum up to a specific non-negative number. Returns `true` if this condition is
  met, otherwise returns `false`.

  ## Examples

      # The sum of the elements in range 2 to 4 is 3
      iex> Coding.valid?([1,7,1,1,1,5,6,1], 3)
      true

      # No range sums to 7
      iex> Coding.valid?([0,4,5,1,8,9,12,3,1], 7)
      false

  """
  @spec valid?(element_list(), sum()) :: boolean()
  def valid?(list, target_sum)
      when is_list(list) and list != [] and is_non_neg_integer(target_sum) and target_sum >= 0 do
    result =
      Enum.reduce_while(list, [], fn
        # If element is target_sum, we immediately return
        ^target_sum, _acc ->
          {:halt, true}

        element, acc ->
          case sum_list(acc, element, target_sum) do
            true ->
              {:halt, true}

            new_list ->
              {:cont, [element | new_list]}
          end
      end)

    case result do
      true -> true
      list when is_list(list) -> false
    end
  end

  @spec sum_list(
          nonempty_list(sum()),
          element(),
          sum()
        ) :: true | list()
  defp sum_list(list, element, target_sum)
       when is_list(list) and is_non_neg_integer(element) and is_non_neg_integer(target_sum) do
    Enum.reduce_while(list, [], fn sum, acc ->
      case sum(sum, element, target_sum) do
        {:halt, true} ->
          # We abort inmediately
          {:halt, true}

        {:halt, _sum} ->
          # We do not include this result
          {:cont, acc}

        # This is an optimization.
        # We don't need to store 0
        {:cont, 0} ->
          {:cont, acc}

        {:cont, sum} ->
          # We add this result
          {:cont, [sum | acc]}
      end
    end)
  end

  @spec sum(
          nonempty_list(sum()),
          element(),
          sum()
        ) :: true | list()
  defp sum(sum, element, target_sum) when sum + element == target_sum,
    do: {:halt, true}

  defp sum(sum, element, target_sum) when sum + element < target_sum,
    do: {:cont, sum + element}

  defp sum(sum, element, _target_sum),
    do: {:halt, sum + element}
end

defmodule Wanton7 do
  @moduledoc """
  * Implement a method that will determinate if exists a range of
  * non-negative elements in an array that sum up to a specific non-
  * negative number
  *
  * Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3
  * Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7)
  *
  """

  def solution([h | t], target_sum) do
    find_solution(1, [h], t, h, target_sum)
  end

  defp find_solution(_, _, _, target_sum, target_sum) when target_sum > 0, do: :OK
  defp find_solution(_, _, [0 | _], _, 0), do: :OK

  defp find_solution(size, arr, [h | t], current_sum, target_sum) when current_sum < target_sum do
    current_sum = current_sum + h
    find_solution(size + 1, [h | arr], t, current_sum, target_sum)
  end

  defp find_solution(size, arr, right, current_sum, target_sum) when current_sum > target_sum do
    size = size - 1
    current_sum = current_sum - Enum.at(arr, size)
    find_solution(size, arr, right, current_sum, target_sum)
  end

  defp find_solution(0, _, [h | t], _, target_sum), do: find_solution(1, [h], t, h, target_sum)

  defp find_solution(_, _, [], current_sum, target_sum) when current_sum != target_sum, do: :KO
  defp find_solution(0, _, [], _, _), do: :KO
end

Benchee.run(
  %{
    "nikiiv" => fn -> Nikiiv.solution(list, sum) end,
    "nikiiv2" => fn -> Nikiiv2.solve_problem(list, sum) end,
    "tomekowal" => fn -> Tomekowal.solution(list, sum) end,
    "stefanluptak" => fn -> Stefanluptak.find(list, sum) end,
    "100phlecs" => fn -> M100phlecs.solution(list, sum) end,
    "eksperimental" => fn -> Eksperimental.valid?(list, sum) end,
    "wanton7" => fn -> Wanton7.solution(list, sum) end
  },
  time: 5,
  memory_time: 5
)

See https://gist.github.com/Qqwy/74653e58fddf3e69a7d5fd05065bca8a for an updated version with more implementations and different input sizes 😊