# 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 – Elliot Gorokhovsky Mar 27 '17 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)))? – Elliot Gorokhovsky Mar 27 '17 at 20:06
• @RenéG That's good too. – Janne Karila Mar 28 '17 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. – Elliot Gorokhovsky Mar 27 '17 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. – Elliot Gorokhovsky Mar 27 '17 at 16:02
• Regarding overloading: ya, that's one of the things I'd like feedback on, idk if it's good or bad. – Elliot Gorokhovsky Mar 27 '17 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. – Elliot Gorokhovsky Mar 27 '17 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). – Peter Taylor Mar 27 '17 at 16:04