My Weblog

Blog about programming and math

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 
Advertisements

November 17, 2011 - Posted by | Programming | , , ,

2 Comments »

  1. Hi,

    I think the number of the form of 2^x are the only ones which will terminate.. Is my logic correct?

    Comment by Ashish | November 20, 2011 | Reply

    • Yes its correct. If n is power of 2 then n & ( n – 1 ) will be 0.

      Comment by tiwari_mukesh | November 20, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: