Skip to content

Instantly share code, notes, and snippets.

@wh5a
Created October 14, 2010 05:44
Show Gist options
  • Save wh5a/625639 to your computer and use it in GitHub Desktop.
Save wh5a/625639 to your computer and use it in GitHub Desktop.
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]
-}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment