public
Created

  • Download Gist
Greplin Challenge #3 Set Sums
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
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]
 
-}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.