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 = []
cur_sequence.append(seed)
if seed == 1:
return cur_sequence
elif seed % 2:
return _gen_sequence(3 * seed + 1, cur_sequence)
else:
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)
502137
"""
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:
Trying:
_gen_sequence(13)
Expecting:
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
ok
Trying:
problem_14(502873)
Expecting:
502137
ok
1 items had no tests:
problem14
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...
