Solution to Google Code Jam 2008 round 1C problem B 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:
  
  123456
  
  You 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
  make
  
  1 + 234 - 5 + 6 = 236
  
  which is ugly. Or
  
  123 + 4 - 56 = 71
  
  which 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.
  
  Input
  
  The 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.
  
  Output
  
  For each test case, you should output a line
  
  Case #X: Y
  
  where 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_cache

M = 2*3*5*7
uglies = 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
M = 2*3*5*7
uglies = 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)))


Why the int(...) calls? Surely range returns integers?



@lru_cache(maxsize=None)
def f(line, k=None):
    if k == None:
        return sum([f(line, k) for k in uglies])


I'm not really a Python programmer so I'm not sure how Pythonic it is, but to me this overloading is a code smell. I would prefer to split out one function which takes just the line and another which does the real work.

Also, what is k? I managed to figure it out by reverse engineering, but a short comment would have helped a lot.



    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))]),
        ])


Again, it would be nice to have a short comment explaining why the recursion works on suffixes (and proving that it's correct, which isn't obvious, because it would seem to allow inserting a - before the first digit of the line in contradiction to the spec).

It would also be nice to see a justification for working on string slices rather than using integers with div/mod by powers of 10.