My Weblog

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] )

```