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

No comments yet.

## Leave a Reply