My Weblog

Blog about programming and math

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

May 29, 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: