Unfolding Elixir

WARNING: not for the allergy prone people! 🙂

Last Elixir problem from exercism.io was related to how to detect stuff a person is allergic to, based on her allergy index / flags.

For example, given these allergens:

@allergens %{
  1 => "eggs",
  2 => "peanuts",
  4 => "shellfish",
  8 => "strawberries",
  16 => "tomatoes",
  32 => "chocolate",
  64 => "pollen",
  128 => "cats"
}

A person with allergy index 5 would be allergic to eggs and shellfish.

Since index flags are powers of two, a simple solution is:

import Bitwise

def allergic_to(flags) do
  @allergens |> Enum.filter(fn({flag, _}) ->
    (flags &&& flag) != 0
  end) |> Dict.values
end

This uses the Bitwise.&&&/2 bitwise AND operator, and it works 😀

But, what originally came to my mind was something like this (pseudo code):

• take first allergen who’s value is lesser or equal to person’s allergy index / flags
• deduct allergen’s value from allergy index and add it to the list
• repeat until remaining value reaches zero

So, for the sake of exercise (this is exercism.io after all), I wanted to see how this could be implemented. Enum.reduce/3 was the initial thought, but it can’t really work since collection elements are visited only once. Here’s the code that works for most cases:

def allergic_to(flags) do
  @allergens |> Enum.reverse |> Enum.reduce({[], flags}, fn({flag, allergen}, {allergies, remaining}) ->
    if flag <= remaining do
      {[allergen | allergies], remaining - flag}
    else
      {allergies, remaining}
    end
  end) |> elem(0)
end

Unfortunately, it gives the wrong result for allergic index 509 for example.

Namely, it traverses allergens 128, 64 etc. in sequence and this includes peanuts as well. But, the idea was to reuse a specific allergen as long as it’s value is lesser than or equal to the remaining allergic index.

So, the formula should actually be: 509 – 128 = 381 – 128 = 253 – 128 = 125 – 64 = 61 – 32 = 29 – 16 = 13 – 8 = 5 – 4 = 1 – 1 = 0. And, the allergens would be 128, 64, 32, 16, 8, 4 and 1. Allergen 2, peanuts, would be excluded.

So, I needed a way to turn allergic index and allergens into a loop that could reuse allergens as needed.

Stream.unfold/2 to the rescue! Basically, it can turn anything into a stream, since you define a starting point and a function that calculates the next value. As long as you don’t return nil, the stream continues. And because of the next function, it is as flexible as you want it to be.

With that in mind, here’s what the Stream.unfold/2 solution looks like:

def allergic_to(flags) do
  Stream.unfold({flags, @allergens |> Enum.max |> elem(0)}, fn({_, 0}) -> nil; ({remaining, flag}) ->
    if flag <= remaining do
      {@allergens[flag], {remaining - flag, flag}}
    else
      {nil, {remaining, Bitwise.bsr(flag, 1)}}
    end
  end) |> Enum.to_list |> Enum.reject(&(!&1))
end

It’s not beautiful or easy to read as the Bitwise.&&&/2 solution, but, as mentioned before, this was just an exercise and a nice way to see how Stream.unfold/2 works.

As always, you can find the entire code at Github.