Project Euler: Problem 14

Problem 14 was a fairly straightforward problem to solve, but I liked it a lot. One reason I liked it is that I enjoy playing with mathematical sequences, but also because it marked my first foray into TDD in Python. I'd heard about doctest, and I really like the concept, so I decided to use it when solving this problem. Here's the code I used to find the solution:

"""Solves Problem 14 from Project Euler."""

def _gen_sequence(seed, cur_sequence = None):
    """Generates a sequence following the rules from Problem 14.
    >>> _gen_sequence(13)
    [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]"""
    if not cur_sequence:
        cur_sequence = []
    if seed == 1:
        return cur_sequence
    elif seed % 2:
        return _gen_sequence(3 * seed + 1, cur_sequence)
        return _gen_sequence(seed / 2, cur_sequence)

def problem_14(upper_bound):
    """Finds the seed (< upper_bound and > 500000) for the longest sequence.

    >>> problem_14(502873)
    cur_answer = 0, 0  # Track the length too, just out of curiosity.
    for seed in reversed(xrange(500001, upper_bound, 2)):
        cur_length = len(_gen_sequence(seed))
        if cur_length > cur_answer[1]:
            cur_answer = seed, cur_length
    return cur_answer[0]

if __name__ == '__main__':
    print problem_14(1000000)

You can execute these tests (assuming Python 2.6) from the command-line with python -m doctest -v problem14.py. The output will resemble:

    [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
1 items had no tests:
2 items passed all tests:
   1 tests in problem14._gen_sequence
   1 tests in problem14.problem_14
2 tests in 3 items.
2 passed and 0 failed.
Test passed.

Not only does doctest make it easy to do TDD, it reminds me somewhat of literate programming. It's obviously not the same, but I think it encourages the sort of documentation that Knuth would approve. I know it definitely made me think more about documenting these simple functions.

Back to flipping out...

blog comments powered by Disqus