Solution to Google Code Jam 2008 round 1C problem B

Question

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

Answer 1

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_sum

def 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)

Answer 2

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.