# My Weblog

## 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.