Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Here's my solution for Project Euler Problem 30. Any optimizations in time, space, or style would be greatly appreciated.

from timeit import default_timer as timer

def digit_powers(exponent):
    def power(k):
        return int(k) ** exponent
    if exponent <= 1:
        return "The exponent must be at least 2."
    else:
        total_sum = 0
        upper_bound = (exponent + 1) * (9 ** exponent)
        for number in range(10, upper_bound + 1):
            digits = [x for x in str(number)]
            if number == sum(map(power, digits)):
                total_sum += number
        return total_sum

start = timer()
ans = digit_powers(5)
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)
share|improve this question

2 Answers 2

up vote 4 down vote accepted

In looking at your code, it seems well written and solves the problem in a straight forward manner. The one thing I would do is to remove the else after your argument check and remove a level of indent. That just helps to keep things flat... Flat is better than nested.

Now onto optimization and potentially making it more complex than it needs to be in order to make it faster. In these problems it seems like a reasonable thing to do even though....Simple is better than complex.

Here are a couple things I looked at as potential issues:

  1. When doing the sum(map(power, digits)), you are calculating the power of each digit many times. If this was a much more expensive calculation then only calculating 1 time is even more important.
  2. In this problem there is a conversion from int->str->int. If you can breakdown the digits without converting them it saves some time. It seems like a good thing to know how to do just in case your ever trying a different language where skipping those transitions may be even faster.

To address these, I did two things:

  1. Pre-calculate 1-9 powers and store the results in a dictionary so they don't get recalculated (Memoization). It lets me look them up very quickly without calculating each time.
  2. Separate the digits using math.log10 as to avoid the int->str->int conversion.

The first item is fairly straight forward, calculating for each digit:

powers = {}
for a in range(10):
    powers[a] = a ** exponent

The second part is a little trickier, what it does is uses math.log10 which gives a count of the digits, then it does a mod 10 to get the right most digit, looks up that power to add to the total and then finally does integer division to divide by 10 effectively moving the decimal place 1 position to the left (dropping the right most digit we just dealt with). This is probably a little different between Python 2/3 due to changes in int/float division. It is basically doing what you are using [x for x in str(number)] to do but without converting to string and adding the power of 5 dict lookup as it goes along:

savei = i
for _ in range(int(math.log10(i)) + 1):
    digit = i % 10
    total += powers[digit]
    i //= 10

Applying those changes to the code make it about twice as fast. Here is what I end up with for the function:

import math

def digit_powers(exponent):
    if exponent <= 1:
        return "The exponent must be at least 2."

    powers = {}
    answer = 0
    # Get the powers
    for a in range(10):
        powers[a] = a ** exponent

    limit = (exponent + 1) * (9 ** exponent)

    # Search for them
    for i in range(10, limit):
        savei = i
        total = 0

        for _ in range(int(math.log10(i)) + 1):
            digit = i % 10
            total += powers[digit]
            i //= 10

        if (total == savei):
            answer += total

    return answer
share|improve this answer

You can make this much faster by precalculating the powers of each digit. Also note that the order of processing for digits doesn't matter so this code starts with the ones place. Here's what I came up with, and on my machine it ran 4x faster than the original code:

def digit_powers(exponent):      
    if exponent <= 1:
        return "The exponent must be at least 2."
    powdigits = [i**exponent for i in range(10)]   
    total_sum = 0
    upper_bound = (exponent + 1) * powdigits[9]
    for number in range(10, upper_bound + 1):
        partialsum = tempnum = number
        while tempnum:
            partialsum -= powdigits[tempnum%10]
            tempnum /= 10
        if not partialsum:
            total_sum += number
    return total_sum
share|improve this answer
    
I like how you avoided the math import... for some reason didn't think of doing that. Also using a comprehension for the powdigits is nice. –  clutton Apr 20 at 20:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.