Qqwy · July 21, 2024 08:39 · Qqwy · Sep 6, 2023 · Qqwy · Sep 6, 2023
diff --git a/benchmarks.exs b/benchmarks.exs
 Mix.install([
  :benchee,
  {:okasaki, "~> 1.0"}, # <- used by Qqwy's Okasaki solution
  :nx, # <- used by Qqwy's Nx solution
  {:exla, "~> 0.5"}, # <- used by Qqwy's Nx solution
 ],
  config: [nx: [default_backend: EXLA.Backend]] # <- used by Qqwy's Nx solution
 )

 inputs = %{
  "100" => {100, Enum.map(1..1_000, fn _ -> Enum.random(0..10) end)},
  "10_000" => {1000, Enum.map(1..10_000, fn _ -> Enum.random(0..100) end)},
  "1_000_000" => {10_000, Enum.map(1..1_000_000, fn _ -> Enum.random(0..10_000) 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

 defmodule Wanton72 do
  def solution([h | t] = arr, target_sum) do
    find_solution(1, arr, 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, arr, t, current_sum, target_sum)
  end

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

  defp find_solution(0, _, [h | t] = right, _, target_sum) do
    find_solution(1, right, t, h, target_sum)
  end

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


 defmodule Qqwy do
  def valid?(list, target) do
    do_valid?(target, list, list, 0, 0)
  end

  defp do_valid?(target, _, _, current, length) when current == target and length > 0, do: true
  defp do_valid?(_, [], _, _, _), do: false
  defp do_valid?(_, _, [], _, _), do: false
  defp do_valid?(target, [h | hs], [l | ls], current, length) do
    cond do
      current <= target ->
        do_valid?(target, hs, [l | ls], current + h, length + 1)
      current >= target ->
        do_valid?(target, [h | hs], ls, current - l, length - 1)
    end
  end
 end

 defmodule QqwyOkasaki do
  @moduledoc """
  A straight-up 1:1 port of 100phlecs' solution but using queues from Okasaki library
  instead of Erlang's `:queue` module.

  Unfortunately, benchmarking shows that there is (a constant time) overhead,
  probably because of the extra Elixir struct wrapping the queue, and dispatching happening through protocols.
  """

  def solution([num | rst], target, queue_implementation \\ Okasaki.Implementations.ConstantQueue) do
    q = Okasaki.Queue.empty(implementation: queue_implementation)
    find(rst, Okasaki.Queue.insert(q, num), num, target)
  end

  defp find(lst, q, sum, target) when sum == target do
    case {lst, Okasaki.Queue.empty?(q)} do
      {[], true} ->
        nil

      {[num | rst], true} ->
        find(rst, Okasaki.Queue.insert(q, num), num, target)

      {_, false} ->
        :ok
    end
  end

  defp find([num | rest], q, sum, target) when sum < target,
    do: find(rest, Okasaki.Queue.insert(q, num), sum + num, target)

  defp find(lst, q, sum, target) when sum > target do
    {:ok, {prev, q}} = Okasaki.Queue.remove(q)
    find(lst, q, sum - prev, target)
  end

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

 defmodule QqwyNx do
  import Nx.Defn

  @moduledoc """
  A fun implementation using Nx tensors.

  Not actually fast, since the problem is not SIMD-friendly and JIT-compilation
  has a significant overhead when used on small input collections.
  """

  def valid?(list, target) do
    found =
      do_valid?(target, Nx.tensor([0 | list], backend: EXLA.Backend))
      |> Nx.to_number

    found == 1
  end

  defn do_valid?(target, tensor) do
    sums = Nx.cumulative_sum(tensor)
    {_, _, _, _, found} =
      while {target, sums, lower_index = 0, higher_index = 1, found = 0},
        (not found) and higher_index < Nx.flat_size(sums)
        do
        h = sums[higher_index]
        l = sums[lower_index]
        cond do
          h - l == target and lower_index < higher_index ->
            # Answer found: short-circuit
            found = 1
            {target, sums, lower_index, higher_index, found}

          h - l <= target ->
            # Below target: add next element to window
            higher_index = higher_index + 1
            {target, sums, lower_index, higher_index, found}

          h - l >= target ->
            # Above target: remove oldest element from window
            lower_index = lower_index + 1
            {target, sums, lower_index, higher_index, found}
          true ->
            # Unreachable but Nx compiler requires it
            {target, sums, lower_index, higher_index, found}
        end
      end
    found
  end
 end

 Benchee.run(
  %{
    "nikiiv" => fn {sum, list} -> Nikiiv.solution(list, sum) end,
    "nikiiv2" => fn {sum, list} -> Nikiiv2.solve_problem(list, sum) end,
    "tomekowal" => fn {sum, list} -> Tomekowal.solution(list, sum) end,
    "stefanluptak" => fn {sum, list} -> Stefanluptak.find(list, sum) end,
    "100phlecs" => fn {sum, list} -> M100phlecs.solution(list, sum) end,
    "eksperimental" => fn {sum, list} -> Eksperimental.valid?(list, sum) end,
    "qqwy_okasaki_constant" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.ConstantQueue) end,
    "qqwy_okasaki_amortized" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.AmortizedQueue) end,
    "qqwy_okasaki_erlang" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.ErlangQueue) end,
    "qqwy_nx" => fn {sum, list} -> QqwyNx.valid?(list, sum) end,
    "qqwy" => fn {sum, list} -> Qqwy.valid?(list, sum) end,
    "wanton7" => fn {sum, list} -> Wanton7.solution(list, sum) end,
    "wanton72" => fn {sum, list} -> Wanton72.solution(list, sum) end,
  },
  inputs: inputs,
  warmup: 0.5,
  time: 1,
  memory_time: 1,
  reduction_time: 1
 )
	Mix.install([
	:benchee,
	{:okasaki, "~> 1.0"}, # <- used by Qqwy's Okasaki solution
	:nx, # <- used by Qqwy's Nx solution
	{:exla, "~> 0.5"}, # <- used by Qqwy's Nx solution
	],
	config: [nx: [default_backend: EXLA.Backend]] # <- used by Qqwy's Nx solution
	)

	inputs = %{
	"100" => {100, Enum.map(1..1_000, fn _ -> Enum.random(0..10) end)},
	"10_000" => {1000, Enum.map(1..10_000, fn _ -> Enum.random(0..100) end)},
	"1_000_000" => {10_000, Enum.map(1..1_000_000, fn _ -> Enum.random(0..10_000) 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

	defmodule Wanton72 do
	def solution([h \| t] = arr, target_sum) do
	find_solution(1, arr, 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, arr, t, current_sum, target_sum)
	end

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

	defp find_solution(0, _, [h \| t] = right, _, target_sum) do
	find_solution(1, right, t, h, target_sum)
	end

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


	defmodule Qqwy do
	def valid?(list, target) do
	do_valid?(target, list, list, 0, 0)
	end

	defp do_valid?(target, _, _, current, length) when current == target and length > 0, do: true
	defp do_valid?(_, [], _, _, _), do: false
	defp do_valid?(_, _, [], _, _), do: false
	defp do_valid?(target, [h \| hs], [l \| ls], current, length) do
	cond do
	current <= target ->
	do_valid?(target, hs, [l \| ls], current + h, length + 1)
	current >= target ->
	do_valid?(target, [h \| hs], ls, current - l, length - 1)
	end
	end
	end

	defmodule QqwyOkasaki do
	@moduledoc """
	A straight-up 1:1 port of 100phlecs' solution but using queues from Okasaki library
	instead of Erlang's `:queue` module.

	Unfortunately, benchmarking shows that there is (a constant time) overhead,
	probably because of the extra Elixir struct wrapping the queue, and dispatching happening through protocols.
	"""

	def solution([num \| rst], target, queue_implementation \\ Okasaki.Implementations.ConstantQueue) do
	q = Okasaki.Queue.empty(implementation: queue_implementation)
	find(rst, Okasaki.Queue.insert(q, num), num, target)
	end

	defp find(lst, q, sum, target) when sum == target do
	case {lst, Okasaki.Queue.empty?(q)} do
	{[], true} ->
	nil

	{[num \| rst], true} ->
	find(rst, Okasaki.Queue.insert(q, num), num, target)

	{_, false} ->
	:ok
	end
	end

	defp find([num \| rest], q, sum, target) when sum < target,
	do: find(rest, Okasaki.Queue.insert(q, num), sum + num, target)

	defp find(lst, q, sum, target) when sum > target do
	{:ok, {prev, q}} = Okasaki.Queue.remove(q)
	find(lst, q, sum - prev, target)
	end

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

	defmodule QqwyNx do
	import Nx.Defn

	@moduledoc """
	A fun implementation using Nx tensors.

	Not actually fast, since the problem is not SIMD-friendly and JIT-compilation
	has a significant overhead when used on small input collections.
	"""

	def valid?(list, target) do
	found =
	do_valid?(target, Nx.tensor([0 \| list], backend: EXLA.Backend))
	\|> Nx.to_number

	found == 1
	end

	defn do_valid?(target, tensor) do
	sums = Nx.cumulative_sum(tensor)
	{_, _, _, _, found} =
	while {target, sums, lower_index = 0, higher_index = 1, found = 0},
	(not found) and higher_index < Nx.flat_size(sums)
	do
	h = sums[higher_index]
	l = sums[lower_index]
	cond do
	h - l == target and lower_index < higher_index ->
	# Answer found: short-circuit
	found = 1
	{target, sums, lower_index, higher_index, found}

	h - l <= target ->
	# Below target: add next element to window
	higher_index = higher_index + 1
	{target, sums, lower_index, higher_index, found}

	h - l >= target ->
	# Above target: remove oldest element from window
	lower_index = lower_index + 1
	{target, sums, lower_index, higher_index, found}
	true ->
	# Unreachable but Nx compiler requires it
	{target, sums, lower_index, higher_index, found}
	end
	end
	found
	end
	end

	Benchee.run(
	%{
	"nikiiv" => fn {sum, list} -> Nikiiv.solution(list, sum) end,
	"nikiiv2" => fn {sum, list} -> Nikiiv2.solve_problem(list, sum) end,
	"tomekowal" => fn {sum, list} -> Tomekowal.solution(list, sum) end,
	"stefanluptak" => fn {sum, list} -> Stefanluptak.find(list, sum) end,
	"100phlecs" => fn {sum, list} -> M100phlecs.solution(list, sum) end,
	"eksperimental" => fn {sum, list} -> Eksperimental.valid?(list, sum) end,
	"qqwy_okasaki_constant" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.ConstantQueue) end,
	"qqwy_okasaki_amortized" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.AmortizedQueue) end,
	"qqwy_okasaki_erlang" => fn {sum, list} -> QqwyOkasaki.solution(list, sum, Okasaki.Implementations.ErlangQueue) end,
	"qqwy_nx" => fn {sum, list} -> QqwyNx.valid?(list, sum) end,
	"qqwy" => fn {sum, list} -> Qqwy.valid?(list, sum) end,
	"wanton7" => fn {sum, list} -> Wanton7.solution(list, sum) end,
	"wanton72" => fn {sum, list} -> Wanton72.solution(list, sum) end,
	},
	inputs: inputs,
	warmup: 0.5,
	time: 1,
	memory_time: 1,
	reduction_time: 1
	)