import Data.List (group)
import Graphics.Gnuplot.Simple
-- 1ª solución
-- ===========
longMayorHuecoBinario :: Int -> Int
longMayorHuecoBinario n =
maximum (0 : map length (huecosBinarios (decimalAbinario n)))
-- (decimalAbinario x) es la representación binaria del número c. Por
-- ejemplo,
-- decimalAbinario 20 == [0,0,1,0,1]
-- decimalAbinario 529 == [1,0,0,0,1,0,0,0,0,1]
decimalAbinario :: Int -> [Int]
decimalAbinario x
| x < 2 = [x]
| otherwise = x `mod` 2 : decimalAbinario (x `div` 2)
-- (huecosBinarios xs) es la lista de los ceros consecutivos de xs entre
-- dos elementos distintos de cero. Por ejemplo,
-- huecosBinarios [0,0,1,0,1] == [[0,0],[0]]
-- huecosBinarios [1,0,0,0,1,0,0,0,0,1] == [[0,0,0],[0,0,0,0]]
huecosBinarios :: [Int] -> [[Int]]
huecosBinarios xs =
[ys | ys <- group xs, 0 `elem` ys]
-- 2ª solución
-- ===========
longMayorHuecoBinario2 :: Int -> Int
longMayorHuecoBinario2 =
maximum . (0 :) . map length . huecosBinarios . decimalAbinario
-- 3ª solución
-- ===========
longMayorHuecoBinario3 :: Int -> Int
longMayorHuecoBinario3 = maximum . longHuecosBinarios
-- (longHuecosBinarios n) es la lista de las longitudes de los huecos
-- binarios de n. Por ejemplo,
-- longHuecosBinarios 20 == [2,1,0]
-- longHuecosBinarios 529 == [3,4,0]
longHuecosBinarios :: Int -> [Int]
longHuecosBinarios 1 = [0]
longHuecosBinarios n | mod n 2 == 1 = longHuecosBinarios (div n 2)
| mod n 4 == 2 = 1 : h : t
| otherwise = 1 + h : t
where (h : t) = longHuecosBinarios (div n 2)
-- Comparación de eficiencia
-- =========================
-- λ> maximum [longMayorHuecoBinario x | x <- [1..100000]]
-- 16
-- (5.51 secs, 941,090,272 bytes)
-- λ> maximum [longMayorHuecoBinario2 x | x <- [1..100000]]
-- 16
-- (5.54 secs, 933,093,168 bytes)
-- λ> maximum [longMayorHuecoBinario3 x | x <- [1..100000]]
-- 16
-- (6.00 secs, 966,584,848 bytes)
graficaLongMayorHuecoBinario :: Int -> IO ()
graficaLongMayorHuecoBinario n =
plotList [ Key Nothing
, Title ("graficaLongMayorHuecoBinario " ++ show n)
, PNG ("Huecos_binarios_" ++ show n ++ ".png")
]
[longMayorHuecoBinario k | k <- [0..n-1]]