CODEWITHSUNDEEP
algorithmfunctional-programmingelixir
jnnks
jnnks

Reputation: 896

Translating imperative Algorithm to Elixir

I have an algorithm in python which I need to implement in a functional programming language, Elixir.

input:

output:

Basically I want to translate this python sample code to Elixir:

input = ["A", "B", "C", "D", "E", "F"]
tuples = list(zip(input, input[1:]))
# --> [("A", "B"), ("B", "C"), ..., ("E", "F")]

# this is a black box -> database result
results = [False, True, True, False, True]

[first_item, *_] = input
biglist = []; smalllist = [first_item]
for (left, right), result in zip(tuples, results):
    if result:
        # valid tuple, keep filling current bucket
        smalllist.append(right)
    else:
        # invalid tuple
        biglist.append(smalllist)
        smalllist = [right]
        
if len(smalllist) > 0:
    biglist.append(smalllist)

print(biglist)
[["A"],  ["B",  "C",  "D"],  ["E", "F"]]
#     fls,   tru,  tru,   fls,   tru

What is the Elixir-way for that problem?

Upvotes: 1

Views: 139

Answers (3)

jnnks
jnnks

Reputation: 896

I came up with my own solution after some more Elixir training that avoids anonymous functions and uses tail recursion:

tokens = ["A", "B", "C", "D", "E", "F"]
connections = [false, true, true, true, true]

defmodule Builder do
  def run(tokens, conns) do
    # use the first token as group
    {:ok, groups} = group(tl(tokens), conns, [hd(tokens)], [])
    Enum.reverse(groups)
  end

  # no more tokens and conns -> all good
  defp group([], [], group, all_groups), do: {:ok, [Enum.reverse(group) | all_groups]}
  
  # something is wrong, unequal amount of tokens and conns
  defp group(_, [], _, _), do: {:error, "too many tokens"} 
  defp group([], _, _, _), do: {:error, "too many conns"}

  # process tokens with tail recursion
  defp group([t | tokens], [valid_connection | conns], group, all_groups) do
    if valid_connection do
      # add token to current group
      group(tokens, conns, [t | group], all_groups) 
    else
      # add group to final list and start new group
      group(tokens, conns, [t], [Enum.reverse(group) | all_groups])
    end
  end
end

Builder.run(tokens, connections)

Upvotes: 0

JasonTrue
JasonTrue

Reputation: 19609

A similar solution, using Enum.chunk_while/4

defmodule Chunky do
  def collect([], _), do: []

  def collect([hd | rest], acceptance_list) do
    rest
    |> Enum.zip(acceptance_list)
    |> Enum.chunk_while(
      [hd],
      fn
        {next, true}, candidate_list ->
          {:cont, [next | candidate_list]}
        {next, false}, candidate_list ->
          {:cont, Enum.reverse(candidate_list), [next]}
      end,
      fn
        [] = acc -> {:cont, acc}
        [_ | _] = candidate_list -> {:cont, Enum.reverse(candidate_list), []}
      end
    )
  end
end

I skipped the first zip because the value from it was being ignored anyway (Missed that the first several passes through).

In the first pattern match case in the chunk_while, in the event the prior acceptance was false, we replace the sublist with the "next" item and emit the reversed chunk.

For the second case, in the event the prior acceptance was false, we replace the sublist with the "next" item and emit the reversed chunk.

A small caveat to this approach is that, under the covers, chunk_while does more or less what Adam's solution does: it reverses the list each chunk. So effectively this requires an additional reversal behind the scenes, which doesn't cost that much with this data size but might of concern for larger lists.

Although it's possible it will demand slightly less cognitive load.

I turned this into a /2 function just for my own convenience while testing; you can run it like this:

list = ["A", "B", "C", "D", "E", "F"]
acceptance = [false, true, true, false, true]

Chunky.collect(list, acceptance)

I did not do it in the example above, because the overhead added wasn't worth it given the small list size, but for larger lists you may find it useful to replace the Enum.xyz functions with their Stream.xyz equivalents.

Upvotes: 2

Adam Millerchip
Adam Millerchip

Reputation: 23091

This is the exact transliteration. There's probably a much better way to do it though, maybe I'll come back to it later if nobody else does.

defmodule Example do
  def run do
    input = ~w(A B C D E F)
    tuples = Enum.zip(input, tl(input))

    results = [false, true, true, false, true]
    combined = Enum.zip(tuples, results)

    first_item = hd(input)
    small_list = [first_item]
    big_list = []

    {small_list, big_list} =
      Enum.reduce(combined, {small_list, big_list}, fn
        {{_left, right}, true}, {small_list, big_list} ->
          {[right | small_list], big_list}

        {{_left, right}, false}, {small_list, big_list} ->
          {[right], [Enum.reverse(small_list) | big_list]}
      end)

    case small_list do
      [] -> big_list
      _ -> [Enum.reverse(small_list) | big_list]
    end
    |> Enum.reverse()
  end
end

Output:

[["A"], ["B", "C", "D"], ["E", "F"]]

Upvotes: 2

Related Questions