Codility - BinaryGap in Elixir - stuck!

Questions / Help
1

I’m beating myself that I can’t figure it out, but if anybody could help me/guide me through I would really appreciate it.
So the problem itself:

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.
Write a function:
function solution(N);
that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.
For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..2,147,483,647].

And my first approach was:

defmodule Codility1BinaryGap do
  def largest_bg(number) do
    # in if statement I was trying filter all binary reps where I have at least two "1"s
    if Enum.count(Integer.digits(number, 2), fn x -> div(x, 1) == 1 end) >= 2 do
     # converting int to binary string represenatation: for int 68 -> "1000100"
      Integer.to_string(number, 2)
      # splitting "1000100" -> ["", "000", "00"]
      |> String.split("1")
      # counting length of each x in  ["", "000", "00"]
      |> Enum.map(fn x -> String.length(x) end)
      # getting max
      |> Enum.max()
    else
      0
    end
  end
end

It is ugly and not sufficient, but it worked except the only case where the provided number is 20 or "10100"
It has two "1"s and it passing if statement, but it is returning, obviously 2 instead of 1.

so, I’ve started differently using Enum.reduce where the main idea was:

acc = 0
#1.
if x == "0", do: acc + 1
#2.
if x == "1" -> need to insert acc to a list and reset acc to 0 and start over
#3.
at the end Enum.max() for the list where I stored everything

so having this simple example I can clearly see that acc collect 3 and 2 for "1000100":

defmodule Codility1BinaryGap do
  def largest_bg(number) do
    list = Integer.to_string(number, 2) |> String.graphemes()

    Enum.reduce(list, 0, fn x, acc ->
      if x == "0" do
        (acc + 1) |> IO.inspect(label: "IF: \n")
      else
        0 |> IO.inspect(label: "ELSE: \n")
      end
    end)
  end
end

ELSE:
: 0
IF:
: 1
IF:
: 2
IF:
: 3
ELSE:
: 0
IF:
: 1
IF:
: 2

So my question how properly insert acc to a list, reset it to zero and start over?
The solution is very easy in JS or Python since we can use and rebind variables

Thank you so much in advance for any possible help!

2 Likes
2

Your accumulator in Enum.reduce can be a more complex structure than a simple value. You could, for example, have a tuple that represents the current count of zero and a list of previous zero counts.

e.g.

{last_count, list_of_counts} = Enum.reduce(string_list, {0, []}, fn x, {current_count, list_of_counts} -> 
  # "if" version - I find it ugly
  count = if x == "0" do current_count + 1 else 0 end
  list_of_counts = if x == "0" do list_of_counts else [current_count | list_of_counts] end
  {count, list_of_counts}

  # or case version (delete one or other)
  case x == "0" do
    true -> {current_count + 1, list_of_counts}
    false -> {0, [current_count | list_of_counts}
  end
end

# Need to add last one 
list_of_counts = if last_count > 0 do [last_count | list_of_counts] else list_of_counts end

# Then you can get max value from the list, or whatever...
2 Likes
3

@mindok Thank you so much! I really appreciate your time and effort to help!
Let me fully absorb what is happening in your code and I will get back shortly!
Thanks again!

4

Enum.reduce/{2,3} is terse, and I use it plenty, but sometimes I have a hard time reading it and immediately understanding what is going on. Same goes for using it. At the end of the day it is just another way to write a recursive function, so when I am stuck it can be helpful to just write the recursive functions. On top of that, writing recursive functions to traverse a list in Elixir can be pretty straightforward thanks to pattern matching.

For example:

  def zeros(integer) when is_integer(integer) do
    Integer.digits(integer, 2)
    |> zeros(0, 0)
  end

  defp zeros([], _current_gap, max_gap), do: IO.puts max_gap
  defp zeros([bit | remaining_bits], current_gap, max_gap) do
    current_gap =
      case bit do
        0 -> current_gap + 1
        1 -> 0
      end

    max_gap =
      case current_gap do
        current_gap when current_gap > max_gap ->
          current_gap
        _ ->
          max_gap
      end

    zeros(remaining_bits, current_gap, max_gap)
  end
end
3 Likes
5

This is the perfect example of the problem when plain old good recursion is much more comprehensive and succinct than all the syntactic sugar.

defmodule BinGaps do
  def count(list, acc \\ {0, 0})

  # we are done, return result
  def count([], {max, _}), do: max
  # let’s count it
  def count([0|rest], {max, curr}),
    do: count(rest, {max, curr+1})
  # ok, we have new winner
  def count([1|rest], {max, curr}) when curr > max,
    do: count(rest, {curr, 0})
  # this was shorter, go ahead
  def count([1|rest], {max, _}),
    do: count(rest, {max, 0})
end

[20, 1041] |> Enum.map(fn number ->
  number
  |> Integer.digits(2)
  |> BinGaps.count()
end)
#⇒ [1, 5]
6 Likes
6

I think the recursive definition by @mudasobwa is what I would do. But just for fun here’s a different approach using a regex to split the number:

defmodule Zeros do
  def maxcount(integer) when is_integer(integer) do
    integer
    |> Integer.to_string
    |> String.split(~r/[^0]+/, trim: true)
    |> Enum.max_by(&String.length/1)
    |> String.length
  end
end

iex> Zeros.maxcount 100200004000000002
8
1 Like
7

Unfortunately, this is also vulnerable to the longest trailing zero block. It should be somewhat like:

Regex.scan(~r/0+(?!0|\z)/i, "10100")
#⇒ [["0"]]

# or, without EOF matcher
Regex.scan(~r/0+(?=1)/i, "10100")
1 Like
8

Beautiful people! I am really sorry for my late response here, but I just wanted to say thanks to everyone! I really appreciate your time!
Yeah, the solution from @mudasobwa looks the most concise. Thanks again!
Also, @mindok thanks for reminding that acc in Enum.reduce() might be more complex than just value: it helped me to reconsider many things I’ve implemented using Enum.reduce()
Thanks again all!

1 Like