Skip to main content
add some loop invariants
Source Link
Gareth Rees
  • 49.7k
  • 3
  • 129
  • 210

The discipline of writing down what each function actually does will make it easier for youryou 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:

  1. 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 just 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.

  2. There's no need for level_filler to be a local function toinside face_value (it doesn't make use of any local variablescontext 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.)

  3. 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 you convertthis expression converts levels(n) / n to a float and then back againto 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.

  4. 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.

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

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

     >>> face_value(2)
     3
    

Luckily this bug doesn't affect the result, because after the incorrect face_value(9) == 10 you get the correct result for face_value(10).

The line that's at fault is the yield 1. In some sense you knew that this was incorrect, because you compensate for itthe error with your test if i == 1: return 1!

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 couldcan easily inline it into face_value. And then various other simplifications become possible. Here's my version of your face_value:

Having computed which number contains the ith digit, youwe 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(99)
    4
    >>> 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!

The discipline of writing down what each function actually does will make it easier for your 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:

  1. 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 just contain a number whose meaning is hard to capture in a short name. Long names 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.

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

  3. 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 left to right. So you convert levels(n) / n to float and then back again, 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.

  4. 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.

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

  6. The purpose of face_value(i) function is to return the number which contains the ith digit. This is where there's the bug:

     >>> face_value(2)
     3
    

Luckily this bug doesn't affect the result, because after the incorrect face_value(9) == 10 you get the correct result for face_value(10).

The line that's at fault is the yield 1. In some sense you knew that this was incorrect, because you compensate for it with your if i == 1: return 1!

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 could easily inline it into face_value. And then various other simplifications become possible. Here's my version of your face_value:

Having computed which number contains the ith digit, you 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(99)
    4
    >>> 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:
        # 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 the last doctest is quite thorough!

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:

  1. 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.

  2. 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.)

  3. 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.

  4. 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.

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

  6. 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!

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:

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!

Source Link
Gareth Rees
  • 49.7k
  • 3
  • 129
  • 210

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 your 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)
  1. 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 just contain a number whose meaning is hard to capture in a short name. Long names 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.

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

  3. 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 left to right. So you convert levels(n) / n to float and then back again, 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.

  4. 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.

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

  6. The purpose of face_value(i) function is to return the number which contains the ith digit. This is where there's the bug:

     >>> face_value(2)
     3
    

Luckily this bug doesn't affect the result, because after the incorrect face_value(9) == 10 you get the correct result for face_value(10).

The line that's at fault is the yield 1. In some sense you knew that this was incorrect, because you compensate for it with your 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 could 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, you 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(99)
    4
    >>> 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:
        # 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 the last doctest is quite thorough!