Jumps.hs

{-# LANGUAGE OverloadedLists #-}
module Main where

import Data.Vector.Unboxed (Vector(..), fromList, (!?))
import Data.List
import Data.Maybe  (isJust)

import qualified Data.Vector.Unboxed as V

hasCycle1 :: (V.Unbox a, Eq a) => Vector a -> Bool
hasCycle1 l = isJust $ V.find (uncurry (==)) $ V.zip l $ every 2 l
  where
    every n xs = let
      xs' = V.drop (n-1) xs
      in if V.null xs' then V.empty else V.head xs' `V.cons` every n (V.tail xs')

hasCycle2 :: (V.Unbox a, Eq a, Show a) => Vector a -> Bool
hasCycle2 l = V.any check . V.indexed . V.take (V.length l `div` 2) $ l
  where
    check (i, a) = a == l V.! (2*i+1)
    {-# INLINE check #-}

calculateJumps :: Vector Int -> Maybe Int
calculateJumps l
      | V.null l          = Nothing
      | hasCycle2 indexes = Nothing
      | otherwise         = Just $ V.length indexes
  where
    indexes = generateIndexes l

generateIndexes :: Vector Int -> Vector Int
generateIndexes vec = V.unfoldr gen (vec,0)
  where gen (v,i) = case v !? i of
                      Just i' -> Just (i+i',(v,i+i'))
                      Nothing -> Nothing

main :: IO ()
main = print $ calculateJumps $ V.replicate 100000 1