Dynamic programming - translating JS to Elixir

Question

I'm trying to translate the following toy dynamic programming problem to Elixir but struggling to see how to do it given there is no early return in Elixir.

It should return a valid combination from "numbers" that sum to "targetSum"

const howSum = (targetSum, numbers) => {

  if (targetSum === 0) return [];
  if (targetSum < 0) return null;

  for (let num of numbers) {
    const remainder = targetSum - num;
    const remainderResult = howSum(remainder, numbers);
    if (remainderResult !== null) {
      return [...remainderResult, num];
    }
  }

  return null;

}

console.log(howSum(7, [2, 3])) // [3,2,2]

I can get below the Elixir version to log all possible solutions with a list comprehension, but how can I get the function to return the first solution found and return/stop at that point?

defmodule HowSum do
  @doc """
  Can you make target_sum from numbers list
  You can use individual numbers as many times as you like
  """
  def sum(0, _numbers, _), do: []
  def sum(target_sum, _numbers, _) when target_sum < 0, do: nil

  def sum(target_sum, numbers, path) do
    for number <- numbers do
      remainder = target_sum - number
      result = sum(remainder, numbers, path ++ [number])

      if result == [] do
        IO.inspect(path ++ [number])
      end
    end
  end
  
end

UPDATE

This is my solution which doesn't seem idiomatic but works using an Agent :-)

defmodule HowSum do
  def cache do
    Agent.start_link(fn -> nil end, name: :solution)
  end

  @doc """
  Can you make target_sum from numbers list
  You can use individual numbers as many times as you like
  """
  def sum(0, _numbers, _), do: []
  def sum(target_sum, _numbers, _) when target_sum < 0, do: nil

  def sum(target_sum, numbers, path) do
    solution = Agent.get(:solution, & &1)

    if !solution do
      for number <- numbers do
        remainder = target_sum - number
        result = sum(remainder, numbers, path ++ [number])

        if result == [] do
          Agent.update(:solution, &(&1 = path ++ [number]))
        end
      end
    end

    Agent.get(:solution, & &1)
  end
end

user_13979518 · Answer

Enum.find/2 / Enum.find_index/2 / Enum.find_value/2 are very useful for this kind of case when you expect to return at some point in a "loop". Enum.reduce_while/3 is useful for more generic algorithms where you need some accumulator as well as early returns.

Here is a solution using Enum.find_value/2 based on your javascript implementation:

defmodule HowSum do
  def sum(target_sum, number) do
    target_sum |> do_sum(number) |> Enum.reverse()
  end
  
  defp do_sum(0, _numbers), do: []
  defp do_sum(target_sum, _numbers) when target_sum < 0, do: nil

  defp do_sum(target_sum, numbers) do
    Enum.find_value(numbers, fn number ->
      remainder = target_sum - number
      result = do_sum(remainder, numbers)

      if result != nil do
        [number | result]
      end
    end)
  end
end


HowSum.sum(7, [2, 3])  # [3, 2, 2]

Please note that this is highly inefficient to build a list by appending at the end, because you would need to clone it at each step. So I replaced result ++ [number] by [number | result], moved the recursive function as a private do_ function, and called Enum.reverse/1 on its result. This is very common when working with recursive functions.

Dynamic programming - translating JS to Elixir

1 Answers