Greplin Challenge.py

# http://challenge.greplin.com/
# author: Thomas Shaddox
# twitter @baddox
# facebook.com/tshaddox
# tshaddox.com

def one():
    s = "Fourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanew\
    nationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreated\
    equalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartio\
    nsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzh\
    atwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthose\
    whoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperth\
    atweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecann\
    othallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrate\
    ditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlong\
    rememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforustheliving\
    rathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethus\
    farsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremaini\
    ngbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh\
    ichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesed\
    eadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreed\
    omandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromth\
    eearth"

    def is_palindrome(string):
        return (string == string[::-1])
    
    longest_palindrome = ""
        
    for i in range(len(s)):
        for j in range(i, len(s)):
            if (is_palindrome(s[i:j]) and j - i > len(longest_palindrome)):
                longest_palindrome = s[i:j]
    return longest_palindrome

def two(x):
    def fib_numbers():
        a = 0
        b = 1
        while True:
            yield a
            a, b = b, a + b

    def divisors(n):
        from math import sqrt, ceil
        d = []
        for i in range(2, ceil(sqrt(n))):
            if (n % i == 0):
                d.append(i)
        return d

    def is_prime(x):
        return (len(divisors(x)) == 0)

    def first_prime_fib(lower_limit=0):
        fibs = fib_numbers()
        while True:
            f = fibs.next()
            if (f > lower_limit and is_prime(f)):
                return f

    def sum_prime_divisors(x):
        return sum([x for x in divisors(x) if is_prime(x)])
            
    return sum_prime_divisors(first_prime_fib(x) + 1)

def three():
    # There are 2^n subsets of a list with n elements.
    # Fun fact: the power set of a countably infinite set (such as the
    # natural numbers) is uncountably infinite.

    s = (3, 4, 9, 14, 15, 19, 28, 37, 47, 50, 54, 56, 59, 61, 70, 73, 78, 81,
        92, 95, 97, 99)

    # Stolen from http://docs.python.org/library/itertools.html#recipes
    # My idea was to use binary digits to represent set membership.
    from itertools import chain, combinations
    def powerset(iterable):
        s = list(iterable)
        return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
    
    def is_intrasummed(set):
        if set:
            return (max(set) * 2 == sum(set))

    count = 0
        
    for subset in powerset(s):
        if (is_intrasummed(subset)):
            count = count + 1
    
    return count
    
if __name__ == "__main__":
    print "1: ", one()
    print "2: ", two(227000)
    print "3: ", three()