Programming Praxis – Subset Sums

In today’s Programming Praxis exercise, we have to solve the third part of the Greplin challenge, which is to find the amount of subsequences of a list of integers where the largest number is equal to the sum of the rest. Let’s get started, shall we?

A quick import:

import Data.List

In keeping with the spirit of the original challenge, we’re going to go with the naive but simple method, which is mostly just a matter of translating the problem description from English to Haskell syntax. The only extra element is tail, which is needed to get rid of an empty list element.

greplin3 :: [Integer] -> Int
greplin3 = length . filter (\s -> sum (init s) == last s) .
           tail . subsequences

Applying this function to the given list gives us the expected answer of 179.

main :: IO ()
main = print $ greplin3 [ 3, 4, 9,14,15,19,28,37,47,50,54
                        ,56,59,61,70,73,78,81,92,95,97,99]

The program runs in about 1.1 seconds, so for the challenge it’s fast enough. For the primes below 210 a more efficient algorithm will be needed though.

About these ads

Tags: , , , , , ,

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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: