Learning idiomatic Elixir - Q1

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 :slight_smile:

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)