dominator :: [Int] -> Int
dominator a
  | count > length a `div` 2 = index
  | otherwise                = -1
  where
    (size, value, index) = foldl step (0, 0, 0) (zip [0 ..] a)
    step (sz, val, idx) (k, v)
      | sz == 0   = (1, v, k)
      | val /= v  = (sz - 1, val, idx)
      | otherwise = (sz + 1, val, idx)

    candidate = if size > 0 then value else -1
    count     = length (filter (== candidate) a)

equiLeader :: [Int] -> Int
equiLeader a = length (filter isEqui (zip3 [0 ..] a prefixLeaderCounts))
  where
    n = length a

    (size, value) = foldl step (0, 0) a
    step (sz, val) v
      | sz == 0   = (1, v)
      | val /= v  = (sz - 1, val)
      | otherwise = (sz + 1, val)

    candidate   = if size > 0 then value else -1
    leaderCount = length (filter (== candidate) a)
    leader      = if leaderCount > n `div` 2 then candidate else -1

    prefixLeaderCounts = scanl1 (+) [if v == leader then 1 else 0 | v <- a]

    isEqui (k, _, lLeaderCount) =
      let leftHalf     = (k + 1) `div` 2
          rightHalf     = (n - k - 1) `div` 2
          rLeaderCount = leaderCount - lLeaderCount
      in  lLeaderCount > leftHalf && rLeaderCount > rightHalf

import Data.Array (Array, listArray, (!))
import qualified Data.Sequence as Seq
import Data.Sequence (Seq, ViewL (..), viewl, (|>))
import qualified Data.Set as Set

fibFrog :: [Int] -> Int
fibFrog a = go (Seq.singleton (-1, 0)) (Set.singleton (-1))
  where
    n = length a
    leaves = listArray (0, n - 1) a :: Array Int Int

    -- distinct Fibonacci jump lengths, up to the first one exceeding n
    jumps = takeWhile (<= n) fibJumps
      where
        fibJumps = 1 : 2 : zipWith (+) fibJumps (tail fibJumps)

    go :: Seq (Int, Int) -> Set.Set Int -> Int
    go queue visited = case viewl queue of
      EmptyL -> -1
      (pos, steps) :< rest
        | any (\j -> pos + j == n) jumps -> steps + 1
        | otherwise ->
            let (queue', visited') = foldl (enqueue pos steps) (rest, visited) jumps
            in  go queue' visited'

    enqueue pos steps (q, visited) j
      | idx >= 0 && idx < n && leaves ! idx == 1 && not (Set.member idx visited) =
          (q |> (idx, steps + 1), Set.insert idx visited)
      | otherwise = (q, visited)
      where
        idx = pos + j

fish :: [Int] -> [Int] -> Int
fish a b = size - dead
  where
    size      = length a
    (dead, _) = foldl step (0, []) (zip a b)

    step (d, stack) (ai, bi)
      | bi == 1   = (d, ai : stack)
      | otherwise = fight ai stack d

    fight _  []             d = (d, [])
    fight ai (top : tops) d
      | ai > top  = fight ai tops (d + 1)
      | otherwise = (d + 1, top : tops)

import Data.Array (Array, listArray, (!))

flags :: [Int] -> Int
flags a = result
  where
    n   = length a
    arr = listArray (0, n - 1) a :: Array Int Int
    at i
      | i >= 0 && i < n = arr ! i
      | otherwise       = 0

    isPeak i = i > 0 && i < n && arr ! (i - 1) < arr ! i && arr ! i > at (i + 1)

    nextArr :: Array Int Int
    nextArr = listArray (0, n - 1) [compute i | i <- [0 .. n - 1]]
      where
        compute i
          | i == n - 1 = if isPeak i then i else -1
          | isPeak i   = i
          | otherwise  = nextArr ! (i + 1)

    result = go 1 0
    go i best
      | i * (i - 1) > n = best
      | otherwise       = go (i + 1) (max best (countFlags i))

    countFlags i = walk 0 0
      where
        walk pos num
          | not (pos < n && num < i) = num
          | nextArr ! pos == -1      = num
          | otherwise                = walk (nextArr ! pos + i) (num + 1)

frogJmp :: Int -> Int -> Int -> Int
frogJmp x y d = ceiling (fromIntegral (y - x) / fromIntegral d :: Double)

import qualified Data.Set as Set

frogRiverOne :: Int -> [Int] -> Int
frogRiverOne x a = go (zip [0 ..] a) Set.empty
  where
    go [] _ = -1
    go ((k, i) : rest) seen
      | i <= x && not (Set.member i seen) =
          let seen' = Set.insert i seen
          in  if Set.size seen' == x then k else go rest seen'
      | otherwise = go rest seen

genomicRangeQuery :: String -> [Int] -> [Int] -> [Int]
genomicRangeQuery s p q = [classify (substr pi' qi) | (pi', qi) <- zip p q]
  where
    substr pi' qi = take (qi - pi' + 1) (drop pi' s)
    classify sub
      | 'A' `elem` sub = 1
      | 'C' `elem` sub = 2
      | 'G' `elem` sub = 3
      | otherwise      = 4

isIPv4Address :: String -> Bool
isIPv4Address s = length parts == 4 && all valid parts
  where
    parts = splitOn '.' s

    splitOn c str = foldr step [""] str
      where
        step ch acc@(cur : rest)
          | ch == c   = "" : acc
          | otherwise = (ch : cur) : rest

    valid p =
      not (null p)
        && all (`elem` ['0' .. '9']) p
        && case reads p :: [(Int, String)] of
             [(n, "")] -> n <= 255 && show n == p
             _         -> False

import Data.Array (Array, listArray, (!))
import Data.Bits (shiftL, (.&.))

ladder :: [Int] -> [Int] -> [Int]
ladder a b = [fibArr ! (ai + 1) .&. ((1 `shiftL` bi) - 1) | (ai, bi) <- zip a b]
  where
    maxA       = maximum a
    globalMask = (1 `shiftL` maximum b) - 1
    fibs       = 0 : 1 : zipWith (\x y -> (x + y) .&. globalMask) fibs (tail fibs)
    fibArr     = listArray (0, maxA + 1) (take (maxA + 2) fibs) :: Array Int Int