Posts Tagged ‘greplin’

Programming Praxis – Subset Sums

November 9, 2010

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.

Programming Praxis – Fibonacci Primes

October 29, 2010

Today’s Programming Praxis exercise comes from the same challenge as the longest palindrome exercise from two weeks ago. The goal is to write a function that calculates the sum of the factors of 1 plus the first prime fibonacci number higher than the input number. Let’s get started, shall we?

To generate the fibonacci numbers, we use the well-known one-liner.

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Getting the factors of a number is done via simple trial division. Unlike the Scheme solution, we don’t repeat factors, since the original challenge says not to.

factors :: Integer -> [Integer]
factors = f 2 where
    f d n | n < d        = []
          | mod n d == 0 = d : f (d + 1) (div n d)
          | otherwise    = f (d + 1) n

We could write some fancy algorithm to check primality, but since we already have a function to calculate factors, why bother? Since the only factor of a prime number will be itself, we can just use that as a check. Initally I just used the isPrime function from Data.Numbers.Primes for this, but looking through the source code I realized I could replace it with this version. Obviously this won’t work too well on large numbers, but for our test case it’s fast enough.

isPrime :: Integer -> Bool
isPrime n = factors n == [n]

The top-level function does what it says on the tin: look through the fibonacci numbers to find one that’s greater than n and prime, add one and return the sum of the factors.

greplin :: Integer -> Integer
greplin n = head [sum $ factors (f + 1) | f <- fibs, f > n, isPrime f]

All that’s left is to apply it to the test number:

main :: IO ()
main = print $ greplin 227000

As expected, we get 352 as a result. And, in the spirit of the contest, which is to do these challenges quickly, I think this one took me about 20 minutes.