Haskell, Sum to Zero
Problem description: Sum to Zero
You are given an array of integers. Count the numbers of ways in which the sum of 4 elements in this array results in zero.
Descriptive Haskell solution:
-- Cons a value onto the beginning -- of every element in a list (•) = map . (:) -- Find the combinations of a list combs = foldr (\y vs -> vs ++ (y • vs)) [[]] -- Given a number k and a list vs -- The length of vs must equal k -- And the sum of vs must equal 0 predicate k vs = (length vs == k) && (sum vs == 0) -- Find the combinations of a list -- Filtered by the predicate filtered_combs k = filter (predicate k) . combs -- Count the number of filtered combinations process k = length . filtered_combs k
MONOLITHIC Haskell version
cthulhu k = length . filter (\xs -> length xs == k && sum xs == 0) . foldr (\y vs -> vs ++ (map (y:) vs)) [[]]
I’m aware that there is likely a more efficient way of computing this – in which only those combinations that are of the correct length are computed – maybe I’ll work on that next…
