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

• Heslacher: Please add a language tag. Please add the problem description to your question. Please use a title which describes the code in question.
• Elliot Gorokhovsky: @Heslacher done

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)

• Elliot Gorokhovsky: Why not all_splits = ((line[:i], line[i:]) for i in range(1, len(line)))?
• Janne Karila: @RenéG That's good too.

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.

• Elliot Gorokhovsky: int(n) -- ya, that was copied from an earlier version that took chars. Oops.
• Elliot Gorokhovsky: Regarding correctness: ya, if this were production code, I'd prove it. It doesn't allow a - before the first digit because p starts at 1. If p started at 0 then it would count operators before the first digit.
• Elliot Gorokhovsky: Regarding overloading: ya, that's one of the things I'd like feedback on, idk if it's good or bad.
• Elliot Gorokhovsky: Regarding using strings instead of ints: wouldn't I have to split it into a list of ints, and then combine them together every time I want to take modulus? Sounds like more work.
• Peter Taylor: @RenéG, I'm pretty sure that it does allow a - before the first digit: what does k-int(line[p:]) mean if it's not putting a - before the first digit? (I know why I think it works, but the fact that we disagree on what it's doing, let alone why it's correct, reinforces the need to comment clearly why it works).