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

Notes on acts-as-taggable-on

If you're using acts-as-taggable-on, you may have noticed the documentation is a bit… sparse. The following are some of the more helpful resources I've found.

• The README from Acts as Taggable on Steroids (the inspriation for acts-as-taggable-on)
• crunchytoast.com has a nice documentation effort

Finally, I ran into errors with trying to build a tag cloud when there were no tags to count. My solution was to embed

    @tags = Post.tag_counts || []

(or similar) into whichever method on the controller was responsible for the page to contain the tag cloud so that the default is an empty list instead of nil.

Back to flipping out...

Mental Note: In Rails 2.3, application.rb -> application_controller.rb

Rails 2.3.2 apparently forgot to rename app/controllers/application.rb to app/controllers/application_controller.rb, so Getting Started with Rails fails with the following error:

uninitialized constant ApplicationController

A simple mv should fix things right up.

Back to flipping out...

Sneak Attack: Reversion

Reversion has to be one of the more clever applications of object serialization I've come across lately.

Back to flipping out...

Project Euler: Problem 15

This one took me a while, largely because I didn't understand what they meant by backtracking. I was thinking of backtracking to a particular point, so I kept trying to use acyclic graphs, sometimes called forests. That's not really what they meant, though. In the context of Problem 15, no backtracking just means you can't go up and you can't go left. After working a 3x3 version of the problem, I thought the values looked a little familiar; I was right. It's a counting problem we covered in combinatorics oh so many years ago: Permutations with Repeated Elements. There are 40 steps to any given path (we have to go 20 steps down and 20 steps right). Since the definition of backtracking makes any given move down indistinguishable from any other move down, and any given move right indistinguishable from any other move right, the answer is 40!/(20!20!).

Back to flipping out...