Longest binary gap coding puzzle

BinaryGap.hs

{-
# PROBLEM

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:

  * class Solution { public int solution(int 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].

# NOTES

I was told I don't have to worry about the binary conversion. This
took me 14 minutes to complete.

I quickly put this together, sorry if it's hard to read!

This runs benchmark with the Criterion package!

# BENCHMARK RESULTS

Summary: the "haskell expert" solution is the fastest.

benchmarking foo/friend
time                 6.709 ms   (6.541 ms .. 6.994 ms)
                     0.977 R²   (0.954 R² .. 0.994 R²)
mean                 6.916 ms   (6.746 ms .. 7.181 ms)
std dev              606.7 μs   (407.4 μs .. 781.6 μs)
variance introduced by outliers: 51% (severely inflated)

benchmarking foo/friend2
time                 5.463 ms   (5.007 ms .. 5.875 ms)
                     0.975 R²   (0.965 R² .. 0.993 R²)
mean                 4.937 ms   (4.842 ms .. 5.116 ms)
std dev              370.9 μs   (204.6 μs .. 538.6 μs)
variance introduced by outliers: 47% (moderately inflated)

benchmarking foo/me
time                 31.07 ms   (29.21 ms .. 32.16 ms)
                     0.991 R²   (0.977 R² .. 0.999 R²)
mean                 35.63 ms   (34.23 ms .. 37.42 ms)
std dev              3.197 ms   (2.338 ms .. 4.117 ms)
variance introduced by outliers: 36% (moderately inflated)

benchmarking foo/haskell expert
time                 4.483 ms   (4.359 ms .. 4.667 ms)
                     0.980 R²   (0.965 R² .. 0.991 R²)
mean                 4.738 ms   (4.600 ms .. 4.904 ms)
std dev              454.9 μs   (330.4 μs .. 555.3 μs)
variance introduced by outliers: 60% (severely inflated)

-}

module Main where

import Data.Bits
import Data.List

import Criterion
import Criterion.Main


-- Used by my solution as well as the expert haskell solution.
type Binary = [Bool]


-- Convert decimal to bool. Used by both my non functional example and the
-- expert functional example.
convert' :: Int -> Binary
convert' i = let sz = finiteBitSize i in map (testBit i) [sz-1,sz-2..0]


-- My solution which avoids using any functions just as a challenge, although,
-- I think this was a bad exercise in the end because I should've gone for a more
-- functional approach.
--
-- See the "solve" function which is the expert haskell solution.
startBinRunLen :: Int -> Int
startBinRunLen n = binRunLen False 0 0 (convert' n)
 where
  binRunLen :: Bool -> Int -> Int -> Binary -> Int
  binRunLen _ hiScore _ [] = hiScore
  binRunLen oneEncountered hiScore pendingScore binary@(b:bs)
    | (not oneEncountered) && b = binRunLen True hiScore pendingScore bs
    | (not oneEncountered) && not b = binRunLen False hiScore pendingScore bs
    | oneEncountered && not b = binRunLen oneEncountered hiScore (pendingScore + 1) bs
    | oneEncountered && b = binRunLen oneEncountered (max hiScore pendingScore) 0 bs


-- Expert Haskell solution. I didn't write this. Actually functional.
solve :: Int -> Int
solve = maximum . (0:) . map length . filter (not . head) . dropWhile (not . head) . group . convert' 


{- My friend told me this is the most efficient algo they found.

It's my rough conversion from this golang code:

  func binaryGap(N int) int {
      res := 0.0
      currentIndex := -1
      for i := 0; N > 0; i++ {
          currentDigit := N % 2
          if currentDigit == 1 {
              if currentIndex > -1 {
                  res = math.Max(res, float64(i-currentIndex))
              }
              currentIndex = i
          }
          N /= 2
      }
      return int(res)
  }

-}
startFriendBinGap :: Int -> Int
startFriendBinGap n = friendBinGap n 0.0 (-1) 0
 where
  friendBinGap :: Int -> Double -> Int -> Int -> Int
  friendBinGap inputN res currentIndex counterI
    | inputN <= 0 = if floor res > 0 then floor res - 1 else 0
    | currentDigit == 1 =
        let newRes = if currentIndex > -1
                       then max res (fromIntegral $ counterI - currentIndex)
                       else res :: Double--FIXME: float64
        in friendBinGap newInputN newRes (counterI) (counterI + 1)
    | otherwise = friendBinGap newInputN res currentIndex (counterI + 1)
   where
    newInputN = inputN `div` 2
    currentDigit = inputN `mod` 2


{- This is another solution from my friend. It builds on the
solution they found. They realized they could simply avoid
messing with types altogether.

Converted from this code:

  func Solution(N int) int {
      max, count := 0, -1
      for N > 0 {
          if N%2 == 1 {
              if max < count {
                  max = count
              }
              count = 0
          } else if count != -1 {
              count++
          }
          N /= 2
      }
      return max
  }

-}
startSomething :: Int -> Int
startSomething n = something n 0 (-1)
 where
  something :: Int -> Int -> Int -> Int
  something inputN max' count
    | inputN <= 0 = max'
    | inputN `mod` 2 == 1 =
        something newInputN (max max' count) 0
    | count /= (-1) = something newInputN max' (count + 1)
    | otherwise = something newInputN max' count
   where
    newInputN = inputN `div` 2


-- Test on these inputs, roughly as described by the problem.
benchmarkCriteria :: [Int]
benchmarkCriteria = [1..647]


main = defaultMain [
   bgroup "foo" [ bench "friend" $ nf (map startFriendBinGap) benchmarkCriteria
                , bench "friend2" $ nf (map startSomething) benchmarkCriteria
                , bench "me" $ nf (map startBinRunLen) benchmarkCriteria
                , bench "haskell expert" $ nf (map solve) benchmarkCriteria
                ]
   ]