Of course, the proper solution would be a sliding window within the original structure
The problem with Elixir is that it lacks an internal O(1) access data structure outside of tuples and to solve this one, one needs O(1) access. There are two ways I’ve found so far to solve it. Either use :queue or convert the List to tuple (given that it is fixed size and we won’t be changing the size, it should work).
I don’t know much yet of Elixir and BEAM internals, this may not be super optimal but..
defmodule CodingChallange 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
if Mix.env() != :test, do: Slog.log(["LESS CASE", tarr,size," left:",left, " right:", right, "curretn_sum:" ,current_sum, "target_sum", target_sum])
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
if Mix.env() != :test, do: Slog.log(["GREATER CASE", tarr,size," left:",left, " right:", right, "curretn_sum:" ,current_sum, "target_sum", target_sum])
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
Tests:
defmodule CodingChallangeTest do
use ExUnit.Case
doctest CodingChallange
test "check solution" do
assert CodingChallange.solve_problem([1,2,3,4],6) == :ok
assert CodingChallange.solve_problem([1,7,1,1,1,5,6,1],3) == :ok
assert CodingChallange.solve_problem([0,4,5,1,8,9,12,3,1],7) == nil
assert CodingChallange.solve_problem([5,3,3,3,4,100],13) == :ok
assert CodingChallange.solve_problem([5,4,3,2,1,0,1,2,3,4,5],0) == :ok
assert CodingChallange.solve_problem([5,4,3,2,1,1,1,2,3,4,5],0) == nil
end
end
TBH I find the lack of proper arrays a bit frustrating. The Arrays module doesn’t explicitly state that the access time is O(1). Outside of that so far Elixir is a delight
In my line of work (and probably everybody else’s) there are like 15% of code that executes 90% of the time and performance needs to be optimal. I am at the phase where I research Elixir for the appropriate data structures to ditch Java and Akka in Elixir’s favor. Over the years I developed the habit of reading the internal implementation to make sure I won’t get tricked by assuming a one line of code would execute in linear time, but I don’t read Elixir’s code that easily yet
so maybe someone else can check how does this perform.