Real Ultimate Programming

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

Project Euler: Problem 19

I recently solved Problem 19 from Project Euler. Since I don’t really enjoy date math, I decided to brute force it and use the datetime module from the standard library.

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

    from datetime import date


    def next_first_of_month_in_20th():
        """Generator to list every first of the month during the 20th century."""
        first = date(1901, 1, 1)
        yield first
        while first.year < 2001:
            if first.month == 12:
                first = first.replace(year=first.year + 1)
                first = first.replace(month=1)
            else:
                first = first.replace(month=first.month + 1)
            yield first


    def main():
        """
        Solve `Problem 19`_ from Project Euler.
        
        .. _`Problem 19`: http://projecteuler.net/index.php?section=problems&id;=19
        """
        return len([first for first in next_first_of_month_in_20th() if first.weekday() == 6])


    if __name__ == '__main__':
        print main()

Back to flipping out…

Project Euler, Problems 18 and 67

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.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69


    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:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

    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…

Project Euler: Problem 11, Redux

I’ve already solved Problem 11, but I didn’t really do a great job: I was doing twice as much work as I needed to. Since I was revisiting this code anyway, I decided to play around a little bit with zip and itertools. Here’s the new and improved solution:

Project Euler: Problem 11 
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

"""Solve Problem 11 from Project Euler."""
import itertools
import operator


OFFSET = 3
GRID = [
    [8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],
    [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0],
    [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65],
    [52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 36, 91],
    [22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
    [24, 47, 32, 60, 99, 3, 45, 2, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
    [32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
    [67, 26, 20, 68, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21],
    [24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
    [21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95],
    [78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92],
    [16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57],
    [86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
    [19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40],
    [4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
    [88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
    [4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36],
    [20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 4, 36, 16],
    [20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54],
    [1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48]
]
INVALID_COORDS_PRODUCT = 0


def _calc_down(row_index, col_index):
    """Calculate the product of the sequence going straight down from ``row_index``."""
    cols = itertools.repeat(col_index, OFFSET + 1)
    last_row = min(row_index + OFFSET + 1, len(GRID))
    coords = zip(xrange(row_index, last_row), cols)
    values = (GRID[row][col] for row, col in coords)
    return reduce(operator.mul, values)


def _calc_right(row_index, col_index):
    """Calculate the product of the sequence going straight right from ``col_index``."""
    rows = itertools.repeat(row_index, OFFSET + 1)
    last_col = min(col_index + OFFSET + 1, len(GRID[row_index]))
    coords = zip(rows, xrange(col_index, last_col))
    values = (GRID[row][col] for row, col in coords)
    return reduce(operator.mul, values)


def _calc_up_right(row_index, col_index):
    """Calculate the product of the sequence going up and to the right from (``row_index``, ``col_index``)."""
    last_row = max(row_index - OFFSET - 1, -1)
    last_col = min(col_index + OFFSET + 1, len(GRID[row_index]))
    coords = zip(xrange(row_index, last_row, -1), xrange(col_index, last_col))
    values = (GRID[row][col] for row, col in coords)
    return reduce(operator.mul, values)


def _calc_down_right(row_index, col_index):
    """Calculate the product of the sequence going down and to the right from (``row_index``, ``col_index``)."""
    last_row = min(row_index + OFFSET + 1, len(GRID))
    last_col = min(col_index + OFFSET + 1, len(GRID[row_index]))
    coords = zip(xrange(row_index, last_row), xrange(col_index, last_col))
    values = (GRID[row][col] for row, col in coords)
    return reduce(operator.mul, values)


def _get_max_product_for_coordinate(row, col):
    """Find the maximum product achievable from (``row``, ``col``)."""
    return max(_calc_up_right(row, col), _calc_right(row, col), _calc_down_right(row, col), _calc_down(row, col))


def problem_11():
    """Find the largest product of four adjacent elements."""
    products = set()
    for row in range(len(GRID)):
        for col in range(len(GRID[row])):
            products.add(_get_max_product_for_coordinate(row, col))
    return max(products)


if __name__ == '__main__':
    print problem_11()

Back to flipping out…

Review of Expert Python Programming, Part Four

Chapter 5: Writing a Package

A Common Pattern for All Packages

This section provides all the details necessary to create a namespaced package that consists of multiple eggs glued together by a master egg using distutils and setuptools. There are multiple subsections that cover everything you should need to build your project, register it with the Cheeseshop (or any other package index), and upload it for the world to enjoy.

How to Uninstall a Package

This section provides a short rationalization for why there isn’t a built-in uninstall command and the current workaround. It’s not mentioned in the book, but the author is currently working on improving distutils, and an uninstall command is on the agenda. The full details are in the Adding an Uninstall Function section of PEP 376.

The Template-Based Approach

After covering the basics of building and distributing a package in the previous section, this section focuses on using templates to reduce the tedium in creating consistent application skeletons. The tool used in this section is Python Paste. There are a couple of short examples using pre-existing templates.

Creating the Package Template

This section covers the process of creating a custom template that describes the structure introduce in the first section.

The rest of the chapter just covers generic aspects of the development cycle, such as version numbering, so I will skip it for this review.

Back to flipping out…