cue-programming-challenge.py

# A trivial code for The Cue Programming Challenge
# URL: http://challenge.cueup.com/

# Level 1: The Longest Substring That Is The Same In Reverse

def filter_candidates(src_text):
    """Pick all the candidate substrings from the text."""

    candidates = []
    for i in range(len(src_text)):
        c = src_text[i]
        for j in range(i + 1, len(src_text)):
            if c == src_text[j]:
                candidates.append(src_text[i:j+1])
    return candidates

def sort_candidates(candidates):
    """Sort candidate substrings by their length."""

    def cmp(s1, s2):
        l1, l2 = len(s1), len(s2)
        if l1 < l2:
            return 1
        elif l1 > l2:
            return -1
        else:
            return 0

    candidates.sort(cmp)
    return candidates

def same_in_reverse(s):
    """Check if the given string is the same in reverse."""

    for i in range(len(s) / 2):
        if s[i] != s[-(i+1)]:
            return False
    return True


def find_longest_one(src_text):
    """Find the longest substring that is the same in reverse."""

    candidates = sort_candidates(filter_candidates(src_text))
    for s in candidates:
        if same_in_reverse(s):
            return s
    return False

# Level 2: The Smallest Fibonacci Number Greater Than X

def fibonacci(lower_bound):
    """Generate fibonacci numbers greater than the given bound."""

    a, b = 0, 1
    while True:
        x = a + b
        if lower_bound < x:
            yield x
        a = b
        b = x

def is_prime(x):
    """Check if the given number is a prime number."""

    if x <= 1:
        return False

    import math

    i = 2
    while i <= math.sqrt(x):
        if x % i == 0:
            return False
        i += 1
    return True

def smallest_prime_fibonacci(lower_bound):
    """Calculate the smallest prime fibonacci number greater than the bound."""

    for x in fibonacci(lower_bound):
        if is_prime(x):
            return x

def prime_divisors_sum(x):
    """Calculate the sum of prime divisors of the given number."""

    prime_divisors = []
    i = 2
    while i <= x:
        if is_prime(i) and x % i == 0:
            prime_divisors.append(i)
        i += 1

    print prime_divisors
    return reduce(lambda x, y: x + y, prime_divisors)

# Level 3: The Number Of Subsets Where The Largest Number Is The Sum Of The
#          Remaining Numbers

def read_numbers(filename):
    """Read the list of numbers in a file."""

    import csv
    with open(filename, 'r') as csvfile:
        reader = csv.reader(csvfile)
        return [ int(item) for item in reader.next() ]

def sums(numbers):
    """Generate sums of subsets of the numbers."""

    subsets = [[]]
    for x in numbers:
        subsets.extend([s + [x] for s in subsets])

    for s in subsets:
        yield reduce(lambda x, y: x + y, s, 0)

def find_num_subsets(numbers):
    """Find the number of subsets where the largest one is the sum of others."""

    numbers.sort()

    count = 0
    for i in range(len(numbers)):
        for sum in sums(numbers[:i]):
            if sum == numbers[i]:
                count += 1
    return count