My Weblog

Blog about programming and math

Project Euler 103

Project Euler Problem 103 . I started solving this problem assuming that given algorithm will not produce correct result for n= 7. I took the search space [20..50] and generated all the combination of 7. For each combination , i generated all the subsets and checked for the property
Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

S(B) S(C); that is, sums of subsets cannot be equal.
If B contains more elements than C then S(B) S(C).

According to my complexity analysis , the complexity of brute force algorithm is O ( (50-20+1) Choose 7 * ( n + n^2 ) ) where n = 2^7 which is O( 31 Choose 7 * n^2 ) = 43 082 956 800. I wrote a Haskell solution and after running it 2 hours on my five years old PC , it did not produce any result .Searching on net , a blog suggested that given algorithm on Euler will work for n = 7 and it will produce optimal solution and to my complete surprise it worked. In the forum no one brute forced it in Haskell so i am not sure if its possible to solve this problem in Haskell. Brute force algorithm did not produce the result on my PC but may be on faster PC it can produce result . subset and combination codes are borrowed from David Tran’s blog.
Edit : Improved brute force using sorting the subsets based on their sum. Now answer is withing couple of minutes. Complexity O( 25 Choose 7 * n log n) where n = 2^7. Go Haskell go 🙂

import Data.List

subset::[a] ->[[a]]
subset [] = [[]]
subset (x:xs) = subset xs ++ map (x:)  (subset xs) 



combination :: [a] -> Int -> [[a]]
combination _   0    = [[]]
combination []  _    = []
combination (x:xs) n = ( map (x:)  (combination xs (n-1)) ) ++ combination xs n

fun ::(Num a, Ord a ) => [a] -> [a] -> Bool
fun y x = 
   case intersect y x == []  of 
      True ->   if ( if l_a > l_b then s_a > s_b else if l_a < l_b then  s_a < s_b else s_a /= s_b )  then True else False where 
				s_a = sum y 
				s_b = sum x 
				l_a = length y
				l_b = length x 
      _    -> True


checkOptimum ::(Num a , Ord a ) => [a] -> Bool
checkOptimum xs = optimumHelper  (sortBy (\a b -> compare ( sum a ) ( sum b) ) . tail.subset $ xs )   where
	optimumHelper [x,y] = if fun x y then True else False 
        optimumHelper  (x:y:ys)  = if fun x y  then optimumHelper  (y:ys) else False 


				


main = do 
	let lst_1 = filter checkOptimum $ combination [20..45] 7
            ans = foldl' (\(acc , list )  x -> if  sum x  < acc then ( sum x  , x )  else ( acc , list) ) ( 1000 , [] ) lst_1		
	print ans 

Haskell code which produced result .

import Data.List 


m :: [Integer]
m = [0,11, 18, 19, 20, 22, 25]

solve = concatMap show . map (+20) $ m
Advertisements

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