SPOJ 9948. Will it ever stop

SPOJ 9948. Will it ever stop is related to cycle detection. A simple and excellent problem to understand the cycle detection algorithm. Accepted Haskell code

import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as BS


solve :: Integer -> BS.ByteString
solve 1 =  BS.pack $ "TAK"
solve n = helpSolve n ( bCycle n ) where 
        helpSolve a b  
           | a == 1 || b == 1 =  BS.pack $ "TAK"
           | a == b =  BS.pack $ "NIE"
           | otherwise = helpSolve  ( bCycle a )  ( bCycle . bCycle $ b ) 

bCycle :: Integer -> Integer 
bCycle n 
  | even n = div n 2  
  | otherwise = 3 * n + 3 

reaD :: BS.ByteString -> Integer 
reaD = fst . fromJust . BS.readInteger 

main = BS.interact $   solve . reaD 

This solution is suggested by Hendrik.

import Data.Bits

reaD :: String -> Integer 
reaD = read 

main = interact $ (\n -> if  (.&.) n ( n - 1)== 0  then "TAK" else "NIE" ) . reaD 

About these ads