Real Ultimate Programming

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

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:

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

    """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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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…