Learning idiomatic Elixir - Q1

I’d do it this way:

defmodule CodingTest 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

Thoughts:

• The algorithm would be simpler if zero element sublist would be allowed for zero sum; In fact, it is so much simpler, that I am 90% sure that it was the intended solution (unless it is some kind of class about algorithms where you should look for edge cases)
• you can use [h | t] = _name to convey variable meaning
• you can use and in guards, so having length(current_sublist) > 0 drops one of the cases that started from scratch and merges it with the case where we have too little elements (they were doing the same thing conceptually - taking a new element from the rest of the list)
• it is often good practice to put all the terminal cases first and then all the recursive ones; however, this problem is simpler if we:

1. check if we have the solution
2. check if we should extend the current_sublist
3. check if we should shrink the current_sublist
4. stop if we can’t do any of those

We could potentially still put stop conditions first, but the check would be we would be more compiicated and I’d rather reduce the number of clauses.

I would probably do it this way. You can paste that code into the Livebook app and play more with it.

It’s less effective than the pure recursion in the solution above, but I find it much more readable.

Regarding the Elixir itself, function returning :OK or :KO is not very idiomatic. I understand you probably decided this way for the sake of simplicity, but it’s worth pointing out for future readers. My solution returns range of the correct sublist or nil.
Also, naming your Elixir project with a Test suffix is not a good idea too, because that’s usually used for the modules that contains tests. (e.g. MyApp.RegistrationTest is a module that is testing MyApp.Registration functionality).

defmodule Sublist 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

Actually an empty list cannot be a solution, so …
The solution I am after is O(n) and length on a list will increase the complexity.
I should’ve mentioned it. My initial solution disregarding the zero and empty list was pretty mich similar to yours

But there are some valid pointers like putting terminal cases first. Thanks

scan and find_index will increase the complexity. I am after O(n).
Thanks for pointing out the suffix shouldn’t be _test. I started with mix new coding_test

Here’s mind attempt to create less checks.

defmodule CodingTest 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

In order to maintain an O(n) runtime complexity, I reached for the :queue erlang module which allows O(1) inserts and pops for a FIFO data structure.

This allows us to maintain a ‘sliding window’ view of the list, moving the right side it when the range sum is too small and moving the left side when the range sum is too large.

Originally I reached for Enum.reduce but because we have to process nodes within the list more than once (see when sum > target function) recursion makes the most sense.

Idiomatic Elixir usually keeps atoms lowercase, and represents empty states either with nil or {:error, reason}, so I changed those values.

As to why I changed find_solution to find is just personal preference

Without the :queue data structure we could take advantage of Enum.reverse to simulate a queue, but then the runtime is no longer O(n), but O(n * k) where k is the max length of the simulated queue (I think, feel free to correct if wrong)

Edit: I found a case where my solution fails, which is the case where the range is at the very end of the list. It requires modifying the case of when sum == target:

  defp find(lst, q, sum, target) when sum == target do
    case {:queue.is_empty(q), lst} do
      {true, []} ->
        nil

      {true, [num | rst]} ->
        find(rst, :queue.in(num, q), num, target)

      {false, _} ->
        :ok
    end
  end

I’m sure there’s more elegant ways to solve this, but I went with this because it’s more readable to me.

Here’s a new test case to confirm it works:

    assert CodingTest.solution([1,7,1,1,1,5,13,1],14) == :ok

I updated the Livebook (here is where it is hosted)

Hi @nikiiv,
Here’s my solution.
This is as idiomatic as I could make it be.

Naming convention, guards, types, specs, pattern matching, optimization (avoids unnecessary traversing), documentation, doctests, and code formatting.

Feel free to study the code and ask questions.

Later on tonight when I’ve got a bit more of free time I will come back to make a few comments about your implementation and what’s idiomatic in Elixir.

– Cheers

defmodule Coding 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

All tests pass:

true = Coding.valid?([1, 7, 1, 1, 1, 5, 6, 1], 3)
false = Coding.valid?([0, 4, 5, 1, 8, 9, 12, 3, 1], 7)
true = Coding.valid?([1, 2, 3, 4], 6)
true = Coding.valid?([1, 7, 1, 1, 1, 5, 6, 1], 3)
false = Coding.valid?([0, 4, 5, 1, 8, 9, 12, 3, 1], 7)
true = Coding.valid?([5, 3, 3, 3, 4, 100], 13)
true = Coding.valid?([5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5], 0)
false = Coding.valid?([5, 4, 3, 2, 1, 1, 1, 2, 3, 4, 5], 0)

Thank you so much!
It gives a lot of color to how structure Elixir code.
The.problem with this implementation is the complexity. I am after O(n), though adding an element to the end of the list is spoiling my solution also

How adding elements to a list spoils your solution?
It may look complex but is the most optimal IMO.
You only keep what is needed, and stops as soon as a solution is found.

Because Elixir lists are single linked so adding an element to the end requires is an O(n) operation

Niki

My solution is of O(n²) complexity.
I cannot see how you can solve this problem linearly (O(n)).