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
:
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
, andn
, and to explain their meaning in longer comments.There's no need for
level_filler
to be a local function toinsideface_value
(it doesn't make use of any local variablescontext fromface_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.)The expression
int(levels(n)/n * 1.0)
is the same asint((levels(n) / n) * 1.0)
since multiplication and division have the same precedence and associate from left to right. So you convertthis expression convertslevels(n) / n
to a float and then back againto an int, which is pointless. Also, sincelevels(n)
isn * 9 * 10 ** (n - 1)
, when divided byn
the result is always9 * 10 ** (n - 1)
. It would be better to write this directly and avoid the useless multiplication byn
followed immediately by division byn
.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 asi // n
and evaluates to the floor of the division, not the ceiling.You make three calls to
levels(n)
in succession. It would be better to make just one call and remember the result.The purpose of
face_value(i)
function is to return the number which contains thei
th 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 i
th 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!