Project Euler 40: Champernownes's Constant

Question

I just finished Project Euler 40 with a brute force method. As usual, any optimizations would be helpful. (I feel like I'm getting better at this scripting thing)

from timeit import default_timer as timer

def product(n):
    from functools import reduce # Valid in Python 2.6+, required in Python 3
    from operator import mul
    return reduce(mul, n, 1)

def find_champernowne_index(d):
    constant = ""
    for k in xrange(1, d + 1):
        constant += str(k)
        if len(constant) >= d:
            return int(constant[d-1])

start = timer()
ans = product(find_champernowne_index(10**x) for x in range(0, 7))
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)

Answer 1

This probably plenty fast enough, but a brute force method strikes me as a very inefficient approach. I can think of a way that should be faster and more efficient, and avoids you constructing a million-character string.

Here are some suggestions/hints:

• You calculate the same constant string each time, despite the fact that it’s always going to be the same. Do you really need to construct it every time? (Or at all?)

• For every value of k you add to constant, you know how long it is. Do you actually need to add it to the string if you’re not going to look at it? Or could you just decrement that from the number of digits left before you get to the digit you want?

• How many one-digit numbers are in the string? And two-digit numbers? And so on.

My actual solution in spoiler text:

We can show that there are always \$ 9 \times 10^{n-1} \$ numbers which have \$n\$ digits, so by computing the sum \$ 9 + 90 + 900 + \dotsb \$ until we go over the target value, we can work out how many digits the number we land in has (say \$ N \$). You can then jump back to the start of the \$ N \$-digit numbers and count up from there. You don't even need to be constructing the string; you can just use lengths to work out where we end up.

Oh, and one style comment:

Quoting from PEP 8 on imports:

Imports are always put at the top of the file, just after any module comments and docstrings, and before module globals and constants.

Don’t put them inside your product definition. The way that Python caches module imports means that it won’t be a performance hit, but it does make it harder to find your module dependencies in a large file. I realise that this isn’t much of an issue in short snippets like this, but it’s a good habit to put your import statements in the standard location.