Real Ultimate Programming

The Home for People Who Like to Flip Out and Write Code

Project Euler: Problem 16

I’ve just finished solving Problem 16. It was a fairly straightforward problem, and at first I couldn’t decide how I wanted to solve it, so I decided to do it both ways and compare them. Here’s the script with both versions of the solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    import math

    def pure_numeric_sum_of_digits(num):
        """
        Finds the sum of the digits in num (presumed to be base-10).
    
        This version of the method operates purely on numbers.
    
        >>> pure_numeric_sum_of_digits(2 ** 15)
        26
        """
        running_total = 0
        for n in xrange(int(math.log10(num)) + 1):
            running_total += num % 10
            num //= 10
        return running_total

    def string_based_sum_of_digits(num):
        """
        Finds the sum of the digits in num (presumed to be base-10).
    
        This version of the method works by using a string representation
        of num and converting individual characters to numbers so we can
        operate on it as a sequence.
    
        >>> string_based_sum_of_digits(2 ** 15)
        26
        """
        sum([int(digit) for digit in str(num)])

    def problem_16():
        """Solves Problem 16 at Project Euler."""
        return string_based_sum_of_digits(2 ** 1000)

    if __name__ == '__main__':
        print problem_16()

Clearly, the string-based solution is more compact, but it has to be slower, right? strings are slower than ints and all that. Thanks to the optimization efforts of the Python implementers, the string-based solution is actually ~167% faster on my machine (I used cProfile on a 10000-iteration loop to make these measurements).

Back to flipping out…