## Project Euler 329

Project Euler 329 is related to probability. Just follow the problem in Haskell because of recursive nature of problem and Haskell both ;). I was trying to solve it using dynamic programming to make it faster but could not succeed so just pure recursion. If some how i could update the Map by ” prod ” [ M.insert ( i , (x:xs) ) prod m ] and use it for further calculations. Any way its take couple of minutes on my slow PC .

import Data.List import qualified Data.Map as M import Data.Ratio isprime :: Integer -> Bool isprime n | n<=1 = False | otherwise = all ( (/=0) . mod n ) . takeWhile (\x -> x*x<=n ) $ [2..] m_1 , m_2 , m :: M.Map ( Integer , String ) ( Ratio Integer ) m_1 = M.fromList[ if isprime i then ( (i,"P") , (%) 2 3 ) else ( (i,"P") , (%) 1 3 ) | i <-[1..500]] m_2 = M.fromList[ if isprime i then ( (i,"N") , (%) 1 3 ) else ( (i,"N") , (%) 2 3 ) | i <-[1..500]] m = M.union m_1 m_2 calprob::Integer -> String -> M.Map ( Integer , String ) ( Ratio Integer ) -> ( Ratio Integer ) calprob i [x] m = case M.lookup ( i , [x] ) m of Just t -> t _ -> error " some thing wrong with your preprocessing\n" calprob i (x:xs) m = let Just t = M.lookup ( i , [x] ) m prod = ( if i == 1 then t * calprob ( i+1 ) xs m else if i == 500 then t*calprob ( i-1 ) xs m else t * ( % ) 1 2 * ( calprob ( i - 1 ) xs m + calprob ( i + 1 ) xs m ) ) in prod main = putStrLn . show $ ( (%) 1 500 ) * ( sum . map (\x -> calprob x "PPPPNNPPPNPPNPN" m ) $ [1..500] )

Advertisements

No comments yet.

Advertisements

## Leave a Reply