Instantly share code, notes, and snippets.

wh5a/Greplin Challenge #3 Set Sums Created Oct 14, 2010

What would you like to do?
 import Data.Array.ST; import Control.Monad.ST; import Data.Array import Control.Monad import Data.List numbers = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99] sources = reverse \$ init numbers {- Dynamic programming: build a table for 14 15 16 ... 99 (because 3, 4, 9 cannot be a sum) 3 4 9 .. 97 (because 99 cannot participate in a sum) For each entry, we fill in the combinations that can sum to the target. Start from the last row, we have: f(i, j) = if i>=j, [] else if i = j, [i] else, f(next_i, j) || f(next_i, j-i) Notice that we only reference the row right below us, so we could use a 1-D array instead of a 2-D table. Build the table bottom up, right to left. -} buildTable :: Array Int [[Int]] buildTable = runSTArray \$ do targets <- newArray (14,99) [] let f i = mapM_ g \$ reverse [14 .. 99] where g j = when (i <= j) \$ do if (i == j) then writeArray targets j [[i]] else unless (j-i < 14) \$ do not_take_i <- readArray targets j take_i <- readArray targets (j-i) case take_i of [] -> return () _ -> writeArray targets j \$ union not_take_i \$ map (i:) take_i mapM_ f sources return targets filterTable = zip numbers \$ map f numbers where f x = if x <= 14 then [] else let sets = buildTable!x in filter g sets g xs = case xs of [_] -> False _ -> True answer = sum \$ map length \$ snd \$ unzip filterTable {- A brute force solution isn't that slow either: main = print \$ length . filter (\x -> sum x `elem` a) . filter (\x -> length x > 1) \$ subsequences a where a = [3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81, 92, 95, 97, 99] -}