Real Ultimate Programming

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

Project Euler: Problem 13

Problem 13 was very straightforward to brute-force.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

    """Solves Problem 13 of Project Euler."""

    NUMBERS = [
                    37107287533902102798797998220837590246510135740250,
                    46376937677490009712648124896970078050417018260538,
                    74324986199524741059474233309513058123726617309629,
                    91942213363574161572522430563301811072406154908250,
                    23067588207539346171171980310421047513778063246676,
                    89261670696623633820136378418383684178734361726757,
                    28112879812849979408065481931592621691275889832738,
                    44274228917432520321923589422876796487670272189318,
                    47451445736001306439091167216856844588711603153276,
                    70386486105843025439939619828917593665686757934951,
                    62176457141856560629502157223196586755079324193331,
                    64906352462741904929101432445813822663347944758178,
                    92575867718337217661963751590579239728245598838407,
                    58203565325359399008402633568948830189458628227828,
                    80181199384826282014278194139940567587151170094390,
                    35398664372827112653829987240784473053190104293586,
                    86515506006295864861532075273371959191420517255829,
                    71693888707715466499115593487603532921714970056938,
                    54370070576826684624621495650076471787294438377604,
                    53282654108756828443191190634694037855217779295145,
                    36123272525000296071075082563815656710885258350721,
                    45876576172410976447339110607218265236877223636045,
                    17423706905851860660448207621209813287860733969412,
                    81142660418086830619328460811191061556940512689692,
                    51934325451728388641918047049293215058642563049483,
                    62467221648435076201727918039944693004732956340691,
                    15732444386908125794514089057706229429197107928209,
                    55037687525678773091862540744969844508330393682126,
                    18336384825330154686196124348767681297534375946515,
                    80386287592878490201521685554828717201219257766954,
                    78182833757993103614740356856449095527097864797581,
                    16726320100436897842553539920931837441497806860984,
                    48403098129077791799088218795327364475675590848030,
                    87086987551392711854517078544161852424320693150332,
                    59959406895756536782107074926966537676326235447210,
                    69793950679652694742597709739166693763042633987085,
                    41052684708299085211399427365734116182760315001271,
                    65378607361501080857009149939512557028198746004375,
                    35829035317434717326932123578154982629742552737307,
                    94953759765105305946966067683156574377167401875275,
                    88902802571733229619176668713819931811048770190271,
                    25267680276078003013678680992525463401061632866526,
                    36270218540497705585629946580636237993140746255962,
                    24074486908231174977792365466257246923322810917141,
                    91430288197103288597806669760892938638285025333403,
                    34413065578016127815921815005561868836468420090470,
                    23053081172816430487623791969842487255036638784583,
                    11487696932154902810424020138335124462181441773470,
                    63783299490636259666498587618221225225512486764533,
                    67720186971698544312419572409913959008952310058822,
                    95548255300263520781532296796249481641953868218774,
                    76085327132285723110424803456124867697064507995236,
                    37774242535411291684276865538926205024910326572967,
                    23701913275725675285653248258265463092207058596522,
                    29798860272258331913126375147341994889534765745501,
                    18495701454879288984856827726077713721403798879715,
                    38298203783031473527721580348144513491373226651381,
                    34829543829199918180278916522431027392251122869539,
                    40957953066405232632538044100059654939159879593635,
                    29746152185502371307642255121183693803580388584903,
                    41698116222072977186158236678424689157993532961922,
                    62467957194401269043877107275048102390895523597457,
                    23189706772547915061505504953922979530901129967519,
                    86188088225875314529584099251203829009407770775672,
                    11306739708304724483816533873502340845647058077308,
                    82959174767140363198008187129011875491310547126581,
                    97623331044818386269515456334926366572897563400500,
                    42846280183517070527831839425882145521227251250327,
                    55121603546981200581762165212827652751691296897789,
                    32238195734329339946437501907836945765883352399886,
                    75506164965184775180738168837861091527357929701337,
                    62177842752192623401942399639168044983993173312731,
                    32924185707147349566916674687634660915035914677504,
                    99518671430235219628894890102423325116913619626622,
                    73267460800591547471830798392868535206946944540724,
                    76841822524674417161514036427982273348055556214818,
                    97142617910342598647204516893989422179826088076852,
                    87783646182799346313767754307809363333018982642090,
                    10848802521674670883215120185883543223812876952786,
                    71329612474782464538636993009049310363619763878039,
                    62184073572399794223406235393808339651327408011116,
                    66627891981488087797941876876144230030984490851411,
                    60661826293682836764744779239180335110989069790714,
                    85786944089552990653640447425576083659976645795096,
                    66024396409905389607120198219976047599490197230297,
                    64913982680032973156037120041377903785566085089252,
                    16730939319872750275468906903707539413042652315011,
                    94809377245048795150954100921645863754710598436791,
                    78639167021187492431995700641917969777599028300699,
                    15368713711936614952811305876380278410754449733078,
                    40789923115535562561142322423255033685442488917353,
                    44889911501440648020369068063960672322193204149535,
                    41503128880339536053299340368006977710650566631954,
                    81234880673210146739058568557934581403627822703280,
                    82616570773948327592232845941706525094512325230608,
                    22918802058777319719839450180888072429661980811197,
                    77158542502016545090413245809786882778948721859617,
                    72107838435069186155435662884062257473692284509516,
                    20849603980134001723930671666823555245252804609722,
                    53503534226472524250874054075591789781264330331690
    ]

    def problem_13(nums_to_sum):
        """Find the first 10 digits of the sum of nums_to_sum."""
        return int(str(sum(nums_to_sum))[:10])

    if __name__ == '__main__':
        print problem_13(NUMBERS)

Back to flipping out…

Project Euler: Problem 12

Problem 12 brings back an interesting mathematical concept: triangular numbers. Triangular numbers (and the formula for finding one) are the slightly more sophisticated approach I mentioned in my writeup for Problem 6. Writing a generator for triangular numbers is easy enough, as is writing some logic to factorize (not prime factorize) a number. Given those two, the solution is easy enough.

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

    """Solves Problem 12 of Project Euler."""

    import math

    def factors(to_factor):
        """Find the factors of to_factor."""
        factors = []
        divisor = 1
        while (divisor <= int(math.sqrt(to_factor))):
            if not to_factor % divisor:
                quotient = to_factor / divisor
                factors.append(divisor)
                factors.append(quotient)
            divisor += 1

        return factors

    def triangular_numbers():
        """Generate the triangular numbers."""
        current = 0
        position = 1
        while True:
            current += position
            position += 1
            yield current

    def problem_12(min_divisors):
        """Finds the first triangular number to have more than 500 divisors."""
        for triangular in triangular_numbers():
            cur_factors = factors(triangular)
            if len(cur_factors) > min_divisors:
                return triangular

    if __name__ == '__main__':
        print problem_12(500)

Back to flipping out…

Project Euler: Problem 11

Problem 11 is fairly straightforward to brute-force, although my solution uses more code than is strictly necessary. Since one of the things I enjoy most about Python is its support for functional programming concepts, I went with a reduce-based 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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

    """Solves Problem 11 from Project Euler."""

    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_TUPLE = 0,

    def _build_up(row_index, col_index):
        """Build the sequence going straight up from row_index."""
        if row_index < OFFSET:
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index - 1][col_index],
                GRID[row_index - 2][col_index],
                GRID[row_index - 3][col_index])

    def _build_down(row_index, col_index):
        """Build the sequence going straight down from row_index."""
        if row_index + OFFSET >= len(GRID):
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index + 1][col_index],
                GRID[row_index + 2][col_index],
                GRID[row_index + 3][col_index])

    def _build_left(row_index, col_index):
        """Build the sequence going straight left from col_index."""
        if col_index < OFFSET:
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index][col_index - 1],
                GRID[row_index][col_index - 2],
                GRID[row_index][col_index - 3])

    def _build_right(row_index, col_index):
        """Build the sequence going straight right from row_index."""
        if col_index + OFFSET >= len(GRID[row_index]):
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index][col_index + 1],
                GRID[row_index][col_index + 2],
                GRID[row_index][col_index + 3])

    def _build_up_right(row_index, col_index):
        """Build the sequence going up and to the right from \
        (row_index, col_index)."""
        if row_index < OFFSET:
            return INVALID_COORDS_TUPLE
        if col_index + OFFSET >= len(GRID[row_index]):
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index - 1][col_index + 1],
                GRID[row_index - 2][col_index + 2],
                GRID[row_index - 3][col_index + 3])

    def _build_down_right(row_index, col_index):
        """Build the sequence going down and to the right from \
        (row_index, col_index)."""
        if row_index + OFFSET >= len(GRID):
            return INVALID_COORDS_TUPLE
        if col_index + OFFSET >= len(GRID[row_index]):
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index + 1][col_index + 1],
                GRID[row_index + 2][col_index + 2],
                GRID[row_index + 3][col_index + 3])

    def _build_down_left(row_index, col_index):
        """Build the sequence going down and to the left from \
        (row_index, col_index)."""
        if row_index + OFFSET >= len(GRID):
            return INVALID_COORDS_TUPLE
        if col_index < OFFSET:
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index + 1][col_index - 1],
                GRID[row_index + 2][col_index - 2],
                GRID[row_index + 3][col_index - 3])

    def _build_up_left(row_index, col_index):
        """Build the sequence going down and to the left from \
        (row_index, col_index)."""
        if row_index < OFFSET:
            return INVALID_COORDS_TUPLE
        if col_index < OFFSET:
            return INVALID_COORDS_TUPLE

        return (GRID[row_index][col_index],
                GRID[row_index - 1][col_index - 1],
                GRID[row_index - 2][col_index - 2],
                GRID[row_index - 3][col_index - 3])

    def _build_all_possible_sequences():
        """Build a set of all possible 4-element sequences."""
        sequences = set()
        for row in range(len(GRID)):
            for col in range(len(GRID[row])):
                sequences.add(_build_up(row, col))
                sequences.add(_build_down(row, col))
                sequences.add(_build_left(row, col))
                sequences.add(_build_right(row, col))
                sequences.add(_build_up_right(row, col))
                sequences.add(_build_down_right(row, col))
                sequences.add(_build_down_left(row, col))
                sequences.add(_build_up_left(row, col))
        return sequences

    def problem_11():
        """Find the largest product of four adjacent elements."""
        products = [reduce(operator.mul, sequence)
                    for sequence in _build_all_possible_sequences()]
        return max(products)

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

Of course, this isn’t the best fit for a functional solution. For one thing, it wastes an awful lot of memory. The more imperative approach below runs in less than half the time on my box, and it’s (a little) less code, to boot. The lesson, as always: KISS.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

    """Solves Problem 11 from Project Euler."""

    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_up(row_index, col_index):
        """Build the sequence going straight up from row_index."""
        if row_index < OFFSET:
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index - 1][col_index] * \
                GRID[row_index - 2][col_index] * \
                GRID[row_index - 3][col_index]

    def _calc_down(row_index, col_index):
        """Build the sequence going straight down from row_index."""
        if row_index + OFFSET >= len(GRID):
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index + 1][col_index] * \
                GRID[row_index + 2][col_index] * \
                GRID[row_index + 3][col_index]

    def _calc_left(row_index, col_index):
        """Build the sequence going straight left from col_index."""
        if col_index < OFFSET:
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index][col_index - 1] * \
                GRID[row_index][col_index - 2] * \
                GRID[row_index][col_index - 3]

    def _calc_right(row_index, col_index):
        """Build the sequence going straight right from row_index."""
        if col_index + OFFSET >= len(GRID[row_index]):
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index][col_index + 1] * \
                GRID[row_index][col_index + 2] * \
                GRID[row_index][col_index + 3]

    def _calc_up_right(row_index, col_index):
        """Build the sequence going up and to the right from \
        (row_index, col_index)."""
        if row_index < OFFSET:
            return INVALID_COORDS_PRODUCT
        if col_index + OFFSET >= len(GRID[row_index]):
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index - 1][col_index + 1] * \
                GRID[row_index - 2][col_index + 2] * \
                GRID[row_index - 3][col_index + 3]

    def _calc_down_right(row_index, col_index):
        """Build the sequence going down and to the right from \
        (row_index, col_index)."""
        if row_index + OFFSET >= len(GRID):
            return INVALID_COORDS_PRODUCT
        if col_index + OFFSET >= len(GRID[row_index]):
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index + 1][col_index + 1] * \
                GRID[row_index + 2][col_index + 2] * \
                GRID[row_index + 3][col_index + 3]

    def _calc_down_left(row_index, col_index):
        """Build the sequence going down and to the left from \
        (row_index, col_index)."""
        if row_index + OFFSET >= len(GRID):
            return INVALID_COORDS_PRODUCT
        if col_index < OFFSET:
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index + 1][col_index - 1] * \
                GRID[row_index + 2][col_index - 2] * \
                GRID[row_index + 3][col_index - 3]

    def _calc_up_left(row_index, col_index):
        """Build the sequence going down and to the left from \
        (row_index, col_index)."""
        if row_index < OFFSET:
            return INVALID_COORDS_PRODUCT
        if col_index < OFFSET:
            return INVALID_COORDS_PRODUCT

        return GRID[row_index][col_index] * \
                GRID[row_index - 1][col_index - 1] * \
                GRID[row_index - 2][col_index - 2] * \
                GRID[row_index - 3][col_index - 3]

    def _calc_all_possible_sequences():
        """Build a set of all possible 4-element sequences."""
        products = set()
        for row in range(len(GRID)):
            for col in range(len(GRID[row])):
                products.add(_calc_up(row, col))
                products.add(_calc_down(row, col))
                products.add(_calc_left(row, col))
                products.add(_calc_right(row, col))
                products.add(_calc_up_right(row, col))
                products.add(_calc_down_right(row, col))
                products.add(_calc_down_left(row, col))
                products.add(_calc_up_left(row, col))
        return products

    def problem_11():
        """Find the largest product of four adjacent elements."""
        return max(_calc_all_possible_sequences())

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

Back to flipping out…

Project Euler: Problem 10

I just finished up Problem 10; given my earlier work on Problem 7, it was trivial to adapt it and arrive at the following program.

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 10 for Project Euler."""
    import math

    def is_prime(candidate, known_primes):
        """Determines whether candidate is prime by trial division using \
        known_primes.

        For this function to work, known_primes *must* be accurate.
        """
        last_possible = math.sqrt(candidate)
        for current_prime in known_primes:
            if current_prime > last_possible:
                break
            if not candidate % current_prime:
                return False
        return True

    def primes_generator(upper_bound):
        """A generator for all the primes < upper_bound."""
        candidates = xrange(2, upper_bound)
        primes = []
        for n in candidates:
            if is_prime(n, primes):
                primes.append(n)
                yield n

    def problem_10():
        """Sum the primes less than 2 million."""
        return sum(primes_generator(2000000))

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

Back to flipping out…

Project Euler: Problem 9

Problem 9 deals with one of the more interesting things I learned in high school geometry: Pythagorean triples. In high school, I just memorized the 2 most common ones (3, 4, 5 and 5, 12, 13) and thought to myself: Wouldn’t it be cool if I could generate all of these? But that was in the before time; Wikipedia didn’t exist and my text book wasn’t cool enough to dwell on them. At any rate, now I know Euclid’s formula for generating Pythagorean triples:

m ** 2 - n ** 2, 2 * m * n, m ** 2 + n ** 2

Here’s the script I used to solve the actual problem:

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

    """Solves Problem 9 from Project Euler."""
    import operator

    def triples(upper_bound):
        """Generator for Pythagorean Triples (represented as tuples).

        Uses Euclid's formula to generate Pythagorean Triples
        (see http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple).
        """
        for m in xrange(2, upper_bound):
            for n in xrange(1, m):
                yield m ** 2 - n ** 2, 2 * m * n, m ** 2 + n ** 2
    # Only uncomment if the triples we get from the original Euclid's are insufficient.
    # for k in xrange(1, upper_bound):
    #     yield k * (m ** 2 - n ** 2), k * (2 * m * n), k * (m ** 2 + n ** 2)

    def problem_9():
        """Finds the product of the Pythagorean Triple where a + b + c = 1000."""
        for triple in triples(1000):
            if sum(triple) == 1000:
                return reduce(operator.mul, triple)
        return 0

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

Back to flipping out…

Project Euler: Problem 8

Just finished up with Problem 8. Brute-forcing it was pretty straightforward, so I decided to play about with some of the more functional aspects of Python. Enter reduce. Here’s the original version I used to solve the problem.

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

    """Solves Problem 8 from Project Euler."""

    def problem_8(num_in_question):
        """Finds and returns the greatest product of 5 consecutive digits \
        of num_in_question."""
        to_process = str(num_in_question)
        offset = 0
        highest_product = 0
        last_possible_start = len(to_process) - 5
        while (offset < last_possible_start):
            digits = [int(digit) for digit in to_process[offset:offset + 5]]
            product = 1
            for n in digits:
                product *= n

            if product > highest_product:
                highest_product = product

            offset += 1

        return highest_product

    if __name__ == '__main__':
        print problem_8("73167176531330624919225119674426574742355349194934\
    96983520312774506326239578318016984801869478851843\
    85861560789112949495459501737958331952853208805511\
    12540698747158523863050715693290963295227443043557\
    66896648950445244523161731856403098711121722383113\
    62229893423380308135336276614282806444486645238749\
    30358907296290491560440772390713810515859307960866\
    70172427121883998797908792274921901699720888093776\
    65727333001053367881220235421809751254540594752243\
    52584907711670556013604839586446706324415722155397\
    53697817977846174064955149290862569321978468622482\
    83972241375657056057490261407972968652414535100474\
    82166370484403199890008895243450658541227588666881\
    16427171479924442928230863465674813919123162824586\
    17866458359124566529476545682848912883142607690042\
    24219022671055626321111109370544217506941658960408\
    07198403850962455444362981230987879927244284909188\
    84580156166097919133875499200524063689912560717606\
    05886116467109405077541002256983155200055935729725\
    71636269561882670428252483600823257530420752963450")

And here’s the same problem_8 function using reduce:

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

    def problem_8(num_in_question):
        """Finds and returns the greatest product of 5 consecutive digits \
        of num_in_question."""
        to_process = str(num_in_question)
        offset = 0
        highest_product = 0
        last_possible_start = len(to_process) - 5
        while (offset < last_possible_start):
            digits = [int(digit) for digit in to_process[offset:offset + 5]]
            product = reduce(operator.mul, digits)

            if product > highest_product:
                highest_product = product

            offset += 1

        return highest_product

Pretty similar: 1 less line of code, 1 more line of imports, almost identical performance. I guess it all comes down to taste. One note: if you’re doing functional programming and need to use a function supported by the operator module, that’s the recommended way of doing it. Since it’s part of the standard library, it’s more obvious what’s going on than a comparable lambda, plus they’re implemented in C to give better performance. But since we’re getting all functional, we might as well do it all the way. Here’s another version:

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

    def problem_8(num_in_question):
        """Finds and returns the greatest product of 5 consecutive digits \
        of num_in_question.

        This function expects num_in_question to be a string so we can
        slice it into 5-digit sequences.
        """
        SEQUENCE_LENGTH = 5
        sequences = [num_in_question[offset:offset + SEQUENCE_LENGTH] \
            for offset in range(len(num_in_question) - SEQUENCE_LENGTH)]
        nums = []
        for sequence in sequences:
            nums.append([int(num) for num in sequence])

        return max([reduce(operator.mul, num_list) for num_list in nums])

Back to flipping out…

Project Euler: Problem 7, Redux

Remember how I mentioned the Sieve wasn’t the most performant solution)? Here’s a much faster solution. On my system the time dropped from 11.661 seconds to .332 seconds. Also, it makes use of one of my favorite features in Python, so far: generators.

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

    """Solves Problem 7 from Project Euler."""
    import math
    import sys


    def is_prime(candidate, known_primes):
        """Determines whether candidate is prime by trial division using \
        known_primes.

        For this function to work, known_primes *must* be accurate.
        """
        last_possible = math.sqrt(candidate)
        for current_prime in known_primes:
            if current_prime > last_possible:
                break
            if not candidate % current_prime:
                return False
        return True


    def primes_generator():
        """A generator for all the primes <= sys.maxint."""
        candidates = xrange(2, sys.maxint)
        primes = []
        for n in candidates:
            if is_prime(n, primes):
                primes.append(n)
                yield n


    def problem_7(n):
        """Finds the nth prime number."""
        primes = primes_generator()
        i = 0
        while i < n - 1:
            i += 1
            primes.next()
        return primes.next()


    if __name__ == '__main__':
        print problem_7(10001)

Back to flipping out…

Project Euler: Problem 7

My new math trick of the day? Upper and lower bounds on the nth prime:

n * ln(n) + n * ln(ln(n - 1)) is less than p[n] is less than n * ln(n) + n * ln(ln(n)) for n greater than or equal to 6

Using this little nugget, I can give myself an upper bound on the numbers I need to test for primality and unleash the Sieve of Eratosthenes on Problem 7. Yes, I realize the Sieve isn’t the most performant way to do most of these tests; I just think it’s a really elegant solution for finding primes and it isn’t slow enough to be an issue for most numbers of this size. At any rate, here’s my script:

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

    """Solves Problem 7 from Project Euler."""
    import math

    FIRST_SIX_PRIMES = {1:2, 2:3, 3:5, 4:7, 5:11, 6:13}

    def e_sieve(upper_bound):
        """Uses the Sieve of Eratosthenes to get a list of the primes up to max."""
        primes = []
        candidates = range(2, upper_bound)
        while candidates:
            head = candidates[0]
            primes.append(head)
            candidates = [n for n in candidates[1:] if n % head]

        return primes

    def problem_7(n):
        """Finds the nth prime number.

        Thanks to
        http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
        we know that it will be less than n * ln(n) + n * ln(ln(n))
        (for n >= 6).
        """
        if n < 6:
            return FIRST_SIX_PRIMES[n]

        upper_bound = int(n * math.log(n) + n * math.log(math.log(n)))

        primes = e_sieve(upper_bound)
        return primes[n - 1]

    if __name__ == '__main__':
        print problem_7(10001)

Back to flipping out…

Project Euler: Problem 6

I just finished up Problem 6. This one was really straightforward. The interesting part was learning a new math trick: Square Pyramidal Numbers. Here’s the most brute-force way (I thought of) to solve it:

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

    """Solves Problem 6 from Project Euler."""
    def sum_of_squares(upper_bound):
        """Sums the squares of all the natural numbers from 1 to \
        upper_bound (inclusive)."""
        return sum(n ** 2 for n in range(1, upper_bound + 1))


    def square_of_sums(upper_bound):
        """Sums all the numbers from 1 to upper_bound."""
        return (sum(range(1, upper_bound + 1)) ** 2)


    def problem_6(n):
        """Finds the difference between the square of the sums and the \
        sum of the squares for the first n natural numbers."""
        return square_of_sums(n) - sum_of_squares(n)


    if __name__ == '__main__':
        print problem_6(100)

Even though this solution has the worst Big O, it wasn’t noticeably slower than any of the others for numbers the size of the ones here.

I used a slightly more sophisticated approach because I remembered an insight for summing the first N natural numbers, discovered by none other than Gauss himself (especially entertaining to use Gauss to solve problems on Project Euler, I know): n * (n + 1)) / 2. I fell back on brute force for the sum of squares part, though.

Solution I Used

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

    """Solves Problem 6 from Project Euler."""
    def sum_of_squares(upper_bound):
        """Sums the squares of all the natural numbers from 1 to \
        upper_bound (inclusive)."""
        return sum(n ** 2 for n in range(1, upper_bound + 1))


    def square_of_sums(upper_bound):
        """Sums all the numbers from 1 to upper_bound."""
        # Use Gauss' insight about n/2 * (n + 1).
        return (upper_bound * (upper_bound + 1) / 2) ** 2


    def problem_6(n):
        """Finds the difference between the square of the sums and the \
        sum of the squares for the first n natural numbers."""
        return square_of_sums(n) - sum_of_squares(n)


    if __name__ == '__main__':
        print problem_6(100)

Since there was a math trick for solving the summing problem, I suspected there was one for the sum of squares problem, as well. A quick Google revealed: Square Pyramidal Numbers. I wish I had known about this when I was doing stupid brain teasers; I always knew I was wasting too much time counting squares.

Least Brutish Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    """Solves Problem 6 from Project Euler."""
    def sum_of_squares(upper_bound):
        """Sums the squares of all the natural numbers from 1 to \
        upper_bound (inclusive)."""
        # Use the rule for square pyramidal numbers
        # (http://en.wikipedia.org/wiki/Square_pyramidal_number).
        return ((2 * upper_bound ** 3) + (3 * upper_bound ** 2) + upper_bound) / 6


    def square_of_sums(upper_bound):
        """Sums all the numbers from 1 to upper_bound."""
        # Use Gauss' insight about n/2 * (n + 1).
        return (upper_bound * (upper_bound + 1) / 2) ** 2


    def problem_6(n):
        """Finds the difference between the square of the sums and the \
        sum of the squares for the first n natural numbers."""
        return square_of_sums(n) - sum_of_squares(n)


    if __name__ == '__main__':
        print problem_6(100)

All in all, I’m really glad I started working these problems. I’ve usually learned/remembered at least one interesting math trick or Python trick during each one I solved, or at least had good programming practice (KISS) driven home.

Back to flipping out…