# 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
case = 1
for line in data:
print('{:.0%}'.format(case/len(data)), file=sys.stderr)
print('Case #{}: {}'.format(case,
f(line)))
case += 1

• @Heslacher done Commented Mar 27, 2017 at 6:20

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)

• Why not all_splits = ((line[:i], line[i:]) for i in range(1, len(line)))? Commented Mar 27, 2017 at 20:06
• @RenéG That's good too. Commented Mar 28, 2017 at 6:19
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.

• int(n) -- ya, that was copied from an earlier version that took chars. Oops. Commented Mar 27, 2017 at 15:59
• 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. Commented Mar 27, 2017 at 16:02
• Regarding overloading: ya, that's one of the things I'd like feedback on, idk if it's good or bad. Commented Mar 27, 2017 at 16:02
• 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. Commented Mar 27, 2017 at 16:03
• @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). Commented Mar 27, 2017 at 16:04