Source

euler / python / 11-greatest-product.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#  11-greatest-product.py
#  euler
#
#  Created by Lars Yencken on 2012-06-14.
#  Copyright 2012 Lars Yencken. All rights reserved.
#

"""
What is the greatest product of four adjacent numbers in any direction (up,
down, left, right, or diagonally) in the 2020 grid?
"""

from operator import mul
import unittest

import numpy as np 

grid = np.array([
 [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],
])


def max_line(ls):
    "Return the maximum of products of four consecutive items, or zero."
    m = 0
    for i in xrange(len(ls) - 3):
        m = max(m, reduce(mul, ls[i:i+4]))
    return m

def greatest_product():
    m = 0

    # look for straight lines
    for i in xrange(20):
        m = max(m, max_line(grid[i, :]))
        m = max(m, max_line(grid[:, i]))

    # look for down-right diagonals
    for i in xrange(20 - 3):
        # build the diagonal
        diag_upper = [grid[i + j, j] for j in xrange(20 - i)]
        m = max(m, max_line(diag_upper))

        diag_lower = [grid[j, i + j] for j in xrange(20 - i)]
        m = max(m, max_line(diag_lower))

    # look for up-right diagonals
    for i in xrange(20 - 3):
        # build the diagonal
        diag_upper = [grid[i + j, 20 - j - 1] for j in xrange(20 - i)]
        m = max(m, max_line(diag_upper))

        diag_lower = [grid[j, 20 - (i + j) - 1] for j in xrange(20 - i)]
        m = max(m, max_line(diag_lower))

    return m

class GreatestProductTest(unittest.TestCase):
    def test_result(self):
        self.assertEqual(greatest_product(), 70600674)

if __name__ == '__main__':
    unittest.TextTestRunner(verbosity=2).run(unittest.makeSuite(GreatestProductTest))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.