Largest Binary Gap

Largest Binary Gap

I read about this problem and thought I would try it.  Later I found it is a question here too:
https://codility.com/programmers/lessons/1-iterations/binary_gap/

My first instinct was, "I know regex can do this, but I hate regex" (Which is also a good reason to get better at regex). 
I couldn't quite hoop the syntax so I moved on.  Here is what I came up with:

def max_binary_gap(n)
  max_gap = 0
  arr = n.to_s(2).chars
  while arr.size > 2 do 
    next_index = arr.index("1")
    break unless next_index
    arr.delete_at next_index
    next_index = arr.index("1")
    break unless next_index
    max_gap = next_index if next_index > max_gap
    arr.slice!(0...next_index)
  end
  max_gap
end

I came back to the regex approach, found this pattern /1(0+)(?=1)/, which uses lookahead to find the gaps nicely.  
I originally thought this would be much faster too.

max_binary_gap(n)
  arr = n.to_s(2).scan(/1(0+)(?=1)/).flatten
  arr.empty? ? 0 : arr.max.size
end

However, turns out they are about the same:

Benchmark.bmbm do |bm|
  bm.report('array indexing') do
    max_gap = 0
    arr = n.to_s(2).chars
    while arr.size > 2 do 
      next_index = arr.index("1")
      break unless next_index
      arr.delete_at next_index
      next_index = arr.index("1")
      break unless next_index
      max_gap = next_index if next_index > max_gap
      arr.slice!(0...next_index)
    end
    max_gap

    1000000.times do 
      n = rand(2147483647)
      max_binary_gap(n)
    end
  end

  bm.report('regex') do
    def max_binary_gap(n)
      arr = n.to_s(2).scan(/1(0+)(?=1)/).flatten
      arr.empty? ? 0 : arr.max.size
    end

    1000000.times do 
      n = rand(2147483647)
      max_binary_gap(n)
    end
  end
end

array indexing   6.600000   0.000000   6.600000 (  6.598933)
regex            6.770000   0.000000   6.770000 (  6.775859)



describe "solution" do
  def max_binary_gap(n)
    max_gap = 0
    arr = n.to_s(2).chars
    while arr.size > 2 do 
      next_index = arr.index("1")
      break unless next_index
      arr.delete_at next_index
      next_index = arr.index("1")
      break unless next_index
      max_gap = next_index if next_index > max_gap
      arr.slice!(0...next_index)
    end
    max_gap
  end

  context "example1" do
    it { expect(solution(1041)).to eq 5 }
  end

  context "example2" do
    it { expect(solution(15)).to eq 0 }
  end

  context "extremes" do
    it { expect(solution(1)).to eq 0 }
    it { expect(solution(5)).to eq 1 }
    it { expect(solution(2147483647)).to eq 0 }
  end

  context "trailing_zeroes" do
    it { expect(solution(6)).to eq 0 }
    it { expect(solution(328)).to eq 2 }
  end

  context "power_of_2" do
    it { expect(solution(16)).to eq 0 }
    it { expect(solution(1024)).to eq 0 }
  end

  context "simple1" do
    it { expect(solution(9)).to eq 2 }
    it { expect(solution(11)).to eq 1 }
  end

  context "simple2" do
    it { expect(solution(19)).to eq 2 }
    it { expect(solution(42)).to eq 1 }
  end

  context "simple3" do
    it { expect(solution(1162)).to eq 3 }
    it { expect(solution(5)).to eq 1 }
  end

  context "medium1" do
    it { expect(solution(51712)).to eq 2 }
    it { expect(solution(20)).to eq 1 }
  end

  context "medium2" do
    it { expect(solution(561892)).to eq 3 }
    it { expect(solution(9)).to eq 2 }
  end

  context "medium3" do
    it { expect(solution(66561)).to eq 9 }
  end

  context "large1" do
    it { expect(solution(6291457)).to eq 20 }
  end

  context "large2" do
    it { expect(solution(74901729)).to eq 4 }
  end

  context "large3" do
    it { expect(solution(805306369)).to eq 27 }
  end

  context "large4" do
    it { expect(solution(1376796946)).to eq 5 }
  end

  context "large5" do
    it { expect(solution(1073741825)).to eq 29 }
  end

  context "large6" do
    it { expect(solution(1610612737)).to eq 28 }
  end
end