## 2009-03-30

### 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 w/ both versions of the solution:

``````
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? `String`s are slower than `int`s 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...

blog comments powered by Disqus