Help me make my Python code clearer

Question

Here's my solution to Project Euler problem 40.

import operator
import math

def levels(n):
    return 9 * n * 10 ** (n - 1)

def face_value(i):
    def level_filler(i):
        n = 1
        yield 1

        while i > levels(n):
            yield int(levels(n)/n * 1.0)
            i -= levels(n)
            n += 1

        yield int(math.ceil(i / n * 1.0))

    if i == 1: return 1
    else:
        return sum(level_filler(i))

def d(i):
    j = str(face_value(i))
    k = len(j)
    l = sum(levels(x) for x in xrange(1, k)) + 1
    m = (i-l)%k

    return int(j[m])


# d(1) * d(10) * d(100) * d(1000) * d(10000) * d(100000) * d(1000000)
print(reduce(operator.mul, (d(10**i) for i in xrange(7))))

It answers without building the actual string, and gets the value of d(i) in (quasi-)linear time.

The problem is that it's messy and I feel it's not easy to read. I cannot even find proper names for my variables.

I was wondering if anyone could give me a code review tell me how my ideas are unclear and how can I express them better.

(I tested the code on Python 2.6)

Answer 1

1. Bug

Your program contains a bug. The second digit of 123456... is 2, but:

>>> d(2)
3

However, solving Project Euler problem 40 only relies on you having the correct result for d(10**i), and this you got right.

2. Improving your solution

1. There are no docstrings, so even though I have solved Project Euler problem 40 myself, it took me a while to figure out what your functions are doing. Even if you struggle to pick good names for functions (and this can be very hard), you can always make things clearer with a brief description and some examples.

   There are also no doctests. Even a handful of doctests might well have found the bug.

   The discipline of writing down what each function actually does will make it easier for you to choose good names. For example, once you have written the docstring for your function levels, it should be clear that a better name would be something like total_digits:

   def total_digits(n):
       """
       Return the total number of digits among all the `n`-digit decimal
       numbers.
   
       >>> total_digits(1) # 1 to 9 (note that 0 is not included)
       9
       >>> total_digits(2) # 10 to 99
       180
       """
       return n * 9 * 10 ** (n - 1)
   

2. Choosing good names for variables is particularly hard when writing mathematical code (as when solving problems from Project Euler). It's typical of mathematical code that variables contain a number whose meaning is hard to capture in a short name. Long names would end up making your code hard to read, so it's often the case that the best approach is to give your variables arbitrary names like i, j, m, and n, and to explain their meaning in longer comments.

3. There's no need for level_filler to be a local function inside face_value (it doesn't make use of any context from face_value). If you moved it out to the top level then it would be easier to test it. (But in fact, it will be better just to remove it, as I will explain below.)

4. The expression int(levels(n)/n * 1.0) is the same as int((levels(n) / n) * 1.0) since multiplication and division have the same precedence and associate from left to right. So this expression converts levels(n) / n to a float and then back to an int, which is pointless. Also, since levels(n) is n * 9 * 10 ** (n - 1), when divided by n the result is always 9 * 10 ** (n - 1). It would be better to write this directly and avoid the useless multiplication by n followed immediately by division by n.

5. Similarly the expression int(math.ceil(i / n * 1.0)) doesn't do what you think it does: the division happens before the multiplication, so in Python 2 (where / truncates the result) this expression is actually the same as i // n and evaluates to the floor of the division, not the ceiling.

6. You make three calls to levels(n) in succession. It would be better to make just one call and remember the result.

7. The purpose of face_value(i) function is to return the number which contains the ith digit. This is where the bug lives:

   >>> face_value(2)
   3
   

   In some sense you knew that this was incorrect, because you compensate for the error with your test if i == 1: return 1!

3. A better solution?

My own approach to this problem would be to simplify the structure as much as possible. The function levels is so simple (just a single expression) that we can easily inline it into face_value. And then various other simplifications become possible. Here's my version of your face_value:

def number_containing(i):
    """
    Return the number containing the `i`th digit in the sequence
    123456789101112...

    >>> number_containing(5)
    5
    >>> number_containing(13)
    11
    >>> number_containing(99)
    54
    >>> number_containing(100)
    55
    """
    n = 1                       # Number of digits.
    first = 1                   # The first n-digit number.
    count = 9                   # Count of n-digit numbers.
    while True:
        # The i-th digit is in the j-th n-digit number (but not if
        # there are more than j n-digit numbers).
        j = (i + n - 1) // n
        if j <= count:
            return first + j - 1
        first += count
        i -= n * count
        n += 1
        count *= 10

Having computed which number contains the ith digit, we then have to work out which digit it is, which you do using another sum over levels. In fact, it is much simpler to work out which digit you want at the same time as you work out which number this digit comes from. If you look at my function above, you'll see that all the information is already present at the point where we return the result. So it's easy just to return the digit at this point:

def d(i):
    """
    Return the `i`th digit of the sequence 123456789101112...

    >>> d(5)
    5
    >>> d(15)
    2
    >>> d(100)
    5
    >>> sequence = ''.join(str(i) for i in xrange(1, 10001))
    >>> all(d(i + 1) == int(digit) for i, digit in enumerate(sequence))
    True
    """
    n = 1                       # Number of digits.
    first = 1                   # The first n-digit number.
    count = 9                   # Count of n-digit numbers.
    while True:
        # Check the loop invariants.
        assert first == 10 ** (n - 1)
        assert count == 9 * first

        # The i-th digit is in the j-th n-digit number (but not if
        # there are more than j n-digit numbers).
        j = (i + n - 1) // n
        if j <= count:
            return int(str(first + j - 1)[(i - 1) % n])
        first += count
        i -= n * count
        n += 1
        count *= 10

Note that the last doctest is quite thorough!