Euler Problem 105 – Disjoint Sets

The interesting thing about this one was that I had to figure out how to load a file in Haskell by using IO inside a Monad. Maybe something pretty basic, but still a novel concept. And a little weird.

This solution could be considered a brute force solution, but it still runs in about 45 seconds on an old PC. The routine first reads the file, splits the lines, then converts the strings into Integers.

For each set, it calculates the perfect series of sub-sets (tricky understanding disjoint sets), then creates a test series against the criteria. Then it simply sums up each set if the sub-set counts are the same.

Now to solve for related problems 103 and 106.

import Data.List
import Data.List.Split

testSubs :: [Integer] -> [Integer] -> Bool
testSubs b c
	| sb /= sc && lb > lc && sb > sc = True
	| sb /= sc && lb <= lc = True 
	| otherwise = False
	where
		sb = sum b
		sc = sum c
		lb = length b
		lc = length c

isSpecial :: [Integer] -> Bool
isSpecial set
	| perfectSet == testSet = True
	| otherwise = False
	where
		list = init $ tail $ subsequences set
		perfectSet = [(b,c)| b <- list, c <- list, b /= c]
		testSet = [(b,c)| b <- list, c <- list, b /= c && testSubs b c]
		
main = do
	raw <- readFile "sets.txt"
	print $ sum [sum $ clean x | x <- [splitOn "," y | y <- lines raw], isSpecial $ clean x]
	where
		clean = map read

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 )

Connecting to %s