This is my solution to Google Code Jam 2008 round 1C problem B (Ugly Numbers). I think it's very elegant. However, I wonder if it's too concise. What could I improve here?The problem:Once upon a time in a strange situation, people called a number ugly  if it was divisible by any of the one-digit primes (2, 3, 5 or 7).  Thus, 14 is ugly, but 13 is fine. 39 is ugly, but 121 is not. Note  that 0 is ugly. Also note that negative numbers can also be ugly; -14  and -39 are examples of such numbers.One day on your free time, you are gazing at a string of digits,  something like:123456You are amused by how many possibilities there are if you are allowed  to insert plus or minus signs between the digits. For example you can  make1 + 234 - 5 + 6 = 236which is ugly. Or123 + 4 - 56 = 71which is not ugly.It is easy to count the number of different ways you can play with the  digits: Between each two adjacent digits you may choose put a plus  sign, a minus sign, or nothing. Therefore, if you start with D digits  there are 3^D-1 expressions you can make.Note that it is fine to have leading zeros for a number. If the string  is 01023, then 01023, 0+1-02+3 and 01-023 are legal  expressions.Your task is simple: Among the 3^D-1 expressions, count how many of  them evaluate to an ugly number.InputThe first line of the input file contains the number of cases, N. Each  test case will be a single line containing a non-empty string of  decimal digits.OutputFor each test case, you should output a lineCase #X: Ywhere X is the case number, starting from 1, and Y is the number of  expressions that evaluate to an ugly number.Code:from functools import lru_cacheM = 2*3*5*7uglies = list(filter(lambda n: (int(n)%2 == 0 or                                int(n)%3 == 0 or                                int(n)%5 == 0 or                                int(n)%7 == 0),                     range(M)))@lru_cache(maxsize=None)def f(line, k=None):    if k == None:        return sum([f(line, k) for k in uglies])    return sum([        (1 if (int(line) % M) == k else 0),        sum([f(line[:p],               (k-int(line[p:])) % M)             for p in range(1, len(line))]),        sum([f(line[:p],               (k+int(line[p:])) % M)             for p in range(1, len(line))]),        ])if __name__ == '__main__':    import sys    data = sys.stdin.read().splitlines()[1:]    case = 1    for line in data:        print('{:.0%}'.format(case/len(data)), file=sys.stderr)        print('Case #{}: {}'.format(case,                                    f(line)))        case += 1
Solution to Google Code Jam 2008 round 1C problem B
python;programming challenge;python 3.x;dynamic programming
Since the k is None case does not share any code with the recursive case, it would definitely be better as a separate function. Also, the prefixes and suffixes are now computed twice. I would use a separate function to generate them, or in fact a generator.Here's how I would rearrange the code of f. Note the docstrings and more descriptive naming.def all_splits(line):    '''Split line into every possible pair of non-empty    prefix and suffix'''    for i in range(1, len(line)):        yield line[:i], line[i:]@lru_cache(maxsize=None)def count_k(line, k):    '''Count expressions that can be formed from line    and sum to k mod M'''    recursion_sum = sum(count_k(prefix, (k - int(suffix)) % M)                         + count_k(prefix, (k + int(suffix)) % M)                        for prefix, suffix in all_splits(line))    return ((int(line) % M) == k) + recursion_sumdef count_ugly(line):        '''Count expressions that can be formed from line    and sum to an ugly number mod M'''    return sum(count_k(line, k) for k in uglies)