My Weblog

Blog about programming and math

SPOJ 1166. Dead Fraction

SPOJ 1166. Dead Fraction is from UVA. The algorithm for solving this problem is discussed here [ See Gatis post ]. Simple implementation in Haskell.

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

readInt :: BS.ByteString -> Integer
readInt x = case BS.readInteger x of 
		Nothing -> 0
		Just ( t , _ ) -> t 

solve :: BS.ByteString -> [ Ratio Integer ]
solve xs = solverHelp ( BS.pack  "" ) xs 

solverHelp :: BS.ByteString -> BS.ByteString -> [Ratio Integer ]
solverHelp x ys 
   | BS.null ys == True = []
   | otherwise = 
     let 
	a =  readInt x 
	b =  readInt ys
        x' = BS.length x 
	y' = BS.length ys 
	c = (%)  a ( 10^x' )
	d = (%)  b ( 10^x' * ( 10^y' - 1 ) )
     in ( c + d ) : solverHelp ( BS.append  x  ( BS.pack [BS.head ys] ) ) ( BS.tail ys )  


format::BS.ByteString -> BS.ByteString
format xs =  BS.takeWhile ( /='.') . BS.drop 2 $ xs 

final :: [Ratio Integer] -> BS.ByteString
final xs = x where 
	a  = minimumBy ( \x  y -> compare ( denominator x ) ( denominator y)  ) xs 
	x = BS.append ( BS.append ( BS.pack.show $ ( numerator a ) )  ( BS.pack  "/" ) ) ( BS.pack.show $ ( denominator a  ) )

main = BS.interact $ BS.unlines . map ( final . solve . format ) . init . BS.lines 
Advertisements

June 1, 2011 - Posted by | Programming | ,

No comments yet.

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: