Project Euler, Problems 18 and 67 - Real Ultimate Programming

I recently finished up Problem 18 (and shortly thereafter, Problem 67). This was a fairly interesting problem, because I like graph theory even if I’m bad at it, and I immediately thought graph theory when I read this problem.

I started creating Vertex and Edge classes, but quickly decided that was too heavyweight for such a small problem. Instead, I chose to use a list of lists where the left-hand child of a node is stored in the next row on the same column and the right-hand child is stored in the next row and the next column.

This made representing and using the data fairly straightforward, but I kept running into the problem of doing an exhaustive search. I knew this was suboptimal (and completely unsuited for the related Problem 67), but I was so locked into thinking of the triangle from the top-down I made things over-complicated.

Eventually, I decided I needed to reset my thinking and Googled for hints. Once I started thinking of the problem from the bottom up (since the graph, after all, is not directed), the solution became clear. Since I didn’t need the actual path, I modified the existing data structure to minimize memory requirements.

    def find_max_sum(triangle):
        """
        Find the maximum sum for a path from the top to the bottom of ``triangle``.
    
        >>> test = [[3,], \
                [7, 5], \
                [2, 4, 6], \
                [8, 5, 9, 3]]
        >>> find_max_sum(test)
        23
        """
        while len(triangle) > 1:
            _reduce_triangle(triangle)
        return triangle[0][0]


    def _reduce_triangle(to_reduce):
        """
        Reduce ``to_reduce`` in place by rolling up the maximum path info one row.
    
        Don't return anything to emphasize the in-place nature of this function.
    
        >>> test = [[3,], \
                [7, 5], \
                [2, 4, 6], \
                [8, 5, 9, 3]]
        >>> _reduce_triangle(test)
        >>> test
        [[3], [7, 5], [10, 13, 15]]
        >>> _reduce_triangle(test)
        >>> test
        [[3], [20, 20]]
        >>> _reduce_triangle(test)
        >>> test
        [[23]]
        """
        last_row = to_reduce[-1]
        for index in xrange(len(to_reduce) - 1):
            to_reduce[-2][index] += max(last_row[index:index + 2])
        del to_reduce[-1]


    def main():
        """
        Solve `Problem 18`_ of Project Euler.
    
        .. _Problem 18: http://projecteuler.net/index.php?section=problems&id;=18
        """
        actual = [[75,],
                 [95, 64],
                 [17, 47, 82],
                 [18, 35, 87, 10],
                 [20, 4, 82, 47, 65],
                 [19, 1, 23, 75, 3, 34],
                 [88, 2, 77, 73, 7, 63, 67],
                 [99, 65, 4, 28, 6, 16, 70, 92],
                 [41, 41, 26, 56, 83, 40, 80, 70, 33],
                 [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
                 [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
                 [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
                 [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
                 [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
                 [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]]
        print find_max_sum(actual)


    if __name__ == '__main__':
        main()

Starting with this, the solution for Problem 67 is trivial: just write some code to parse the triangle out of a text file instead of coding it directly into the source code:

    def find_max_sum(triangle):
        """
        Find the maximum sum for a path from the top to the bottom of ``triangle``.
    
        >>> test = [[3,], \
                [7, 5], \
                [2, 4, 6], \
                [8, 5, 9, 3]]
        >>> find_max_sum(test)
        23
        """
        while len(triangle) > 1:
            _reduce_triangle(triangle)
        return triangle[0][0]


    def _reduce_triangle(to_reduce):
        """
        Reduce ``to_reduce`` in place by rolling up the maximum path info one row.
    
        Don't return anything to emphasize the in-place nature of this function.
    
        >>> test = [[3,], \
                [7, 5], \
                [2, 4, 6], \
                [8, 5, 9, 3]]
        >>> _reduce_triangle(test)
        >>> test
        [[3], [7, 5], [10, 13, 15]]
        >>> _reduce_triangle(test)
        >>> test
        [[3], [20, 20]]
        >>> _reduce_triangle(test)
        >>> test
        [[23]]
        """
        last_row = to_reduce[-1]
        for index in xrange(len(to_reduce) - 1):
            to_reduce[-2][index] += max(last_row[index:index + 2])
        del to_reduce[-1]


    def _parse_triangle_from_file(data_file):
        """
        Parse out the triangle data from ``data_file``.
    
        >>> _parse_triangle_from_file('test_triangle.txt')
        [[3], [7, 5], [10, 13, 15]]
        """
        triangle = []
        with open(data_file, 'r') as triangle_file:
            for line in triangle_file:
                triangle.append([int(x) for x in line.split()])
        return triangle


    def main():
        """
        Solve `Problem 67`_ of Project Euler.
    
        .. _Problem 67: http://projecteuler.net/index.php?section=problems&id;=67
        """
        print find_max_sum(_parse_triangle_from_file('triangle.txt'))


    if __name__ == '__main__':
        main()

Back to flipping out…