nekedome / project-euler

solutions/problem11.py

"""
Project Euler Problem 11: Largest Product In A Grid
===================================================

.. module:: solutions.problem11
   :synopsis: My solution to problem #11.

The source code for this problem can be
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem11.py>`_.

Problem Statement
#################

In the :math:`20 \\times 20` grid below, four numbers along a diagonal line have been marked in red.

.. math::

    08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08 \\\\
    49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00 \\\\
    81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65 \\\\
    52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,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,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50 \\\\
    32,98,81,28,64,23,67,10,\\color{red}{26},38,40,67,59,54,70,66,18,38,64,70 \\\\
    67,26,20,68,02,62,12,20,95,\\color{red}{63},94,39,63,08,40,91,66,49,94,21 \\\\
    24,55,58,05,66,73,99,26,97,17,\\color{red}{78},78,96,83,14,88,34,89,63,72 \\\\
    21,36,23,09,75,00,76,44,20,45,35,\\color{red}{14},00,61,33,97,34,31,33,95 \\\\
    78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92 \\\\
    16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57 \\\\
    86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58 \\\\
    19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40 \\\\
    04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66 \\\\
    88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69 \\\\
    04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36 \\\\
    20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16 \\\\
    20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54 \\\\
    01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48

The product of these numbers is
:math:`\\color{red}{26} \\times \\color{red}{63} \\times \\color{red}{78} \\times \\color{red}{14} = 1788696`.

This line is too long as per the coding-style (110/100).

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in

This line is too long as per the coding-style (117/100).

the :math:`20 \\times 20` grid?

Solution Discussion
###################

Multiplication is associative, which means 'up' and 'down' are equivalent as are 'left' and 'right'. This means we

This line is too long as per the coding-style (114/100).

can simply consider the vertical and horizontal cases to cover all four directions. Similarly, this logic reduces the

This line is too long as per the coding-style (117/100).

number of diagonal directions; 'lower left to upper right' is equivalent to 'upper right to lower left', and 'upper left

This line is too long as per the coding-style (120/100).

to lower right' is equivalent to 'lower right to upper left'.

So, simply search (exhaustively) for the greatest product in each of these four cases and then find the maximum of

This line is too long as per the coding-style (114/100).

those four scores.

Solution Implementation
#######################

.. literalinclude:: ../../solutions/problem11.py
   :language: python
   :lines: 64-
"""

from functools import reduce
from operator import mul
from typing import List


def horizontal(grid: List[List[int]], run_len: int) -> int:
    """ Find the maximal `run_len` long product in the horizontal direction

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the horizontal direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name m does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    for i in range(n):
        for j in range(m - run_len + 1):
            subset = grid[i][j:j+run_len]
            product = reduce(mul, subset, 1)
            answer = max(answer, product)
    return answer


def vertical(grid: List[List[int]], run_len: int) -> int:

This code seems to be duplicated in your project.

    """ Find the maximal `run_len` long product in the vertical direction

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the vertical direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name m does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    for i in range(n - run_len + 1):
        for j in range(m):
            product = 1
            for k in range(run_len):
                product *= grid[i+k][j]
            answer = max(answer, product)
    return answer


def diagonal_natural(grid: List[List[int]], run_len: int) -> int:

This code seems to be duplicated in your project.

    """ Find the maximal `run_len` long product in the 'natural' diagonal direction

    The 'natural' diagonal is defined as top-left to bottom-right when viewed in the C-array style convention.

This line is too long as per the coding-style (110/100).

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the natural diagonal direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name m does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    for i in range(n - run_len+1):
        for j in range(m - run_len+1):
            product = 1
            for k in range(run_len):
                product *= grid[i+k][j+k]
            answer = max(answer, product)
    return answer


def diagonal_reverse(grid: List[List[int]], run_len: int) -> int:

This code seems to be duplicated in your project.

    """ Find the maximal `run_len` long product in the 'reverse' diagonal direction

    The 'reverse' diagonal is defined as bottom-left to top-right when viewed in the C-array style convention.

This line is too long as per the coding-style (110/100).

    :param grid: the two-dimensional integer grid
    :param run_len: the product run-length
    :return: the maximum `run_len` long product in the reverse diagonal direction from `grid`
    """

    answer = 0
    n, m = len(grid), len(grid[0])

The name n does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

The name m does not conform to the variable naming conventions ((([a-z][a-z0-9_]{2,30})|(_[a-z0-9_]*))$).

    for i in range(run_len - 1, n):
        for j in range(m - run_len+1):
            product = 1
            for k in range(run_len):
                product *= grid[i-k][j+k]
            answer = max(answer, product)
    return answer


def solve():
    """ Compute the answer to Project Euler's problem #11 """

    # Build two-dimensional array of integers
    grid = """
        08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
        49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
        81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
        52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 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 03 45 02 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 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
        24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
        21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
        78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
        16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
        86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
        19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
        04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
        88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
        04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
        20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
        20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
        01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
    """
    grid = [row.strip() for row in grid.split("\n")]
    grid = [[int(cell) for cell in row.split(" ")] for row in grid if row != ""]

    # Search for maximal run_len long products in each direction
    run_len = 4
    answers = [horizontal(grid, run_len), vertical(grid, run_len),
               diagonal_natural(grid, run_len), diagonal_reverse(grid, run_len)]

    # Identify the maximum of those partial answers
    answer = max(answers)
    return answer


expected_answer = 70600674

The name expected_answer does not conform to the constant naming conventions ((([A-Z_][A-Z0-9_]*)|(__.*__))$).