Project Euler # 11 largest product in a grid in Python

Question

In the ×ばつ20 grid below, four numbers along a diagonal line have been marked in red. The product of these numbers is 26 ×ばつかける 63 ×ばつかける 78 ×ばつかける 14 =わ 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the ×ばつ20 grid?

Here's my implementation in Python and I had to implement the getting the matrix's diagonals thing and I was wondering whether there is some Python library that includes a similar function.

from functools import reduce
from operator import mul
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
"""
def get_matrix_rows(matrix):
 """Return a list of lists containing n * n matrix rows."""
 return [[int(number) for number in row.split()] for row in matrix.rstrip().split('\n')]
def get_matrix_columns(matrix_rows):
 """Return a list of lists containing n * n matrix columns."""
 return [[row[column_index] for row in matrix_rows] for column_index in range(len(matrix_rows))]
def get_non_diagonal_partitions(rows, columns, size):
 """Generate up, down, right & left partitions of length size for n * n matrix."""
 for index in range(len(rows) - size + 1):
 for row in rows:
 yield row[index: index + size]
 for column in columns:
 yield column[index: index + size]
def get_modified_matrix_columns(modified_matrix_rows):
 """Return a list of lists containing columns of n * m matrix n != m is True."""
 columns = []
 for column_index in range(len(modified_matrix_rows[0])):
 temp = []
 for index in range(len(modified_matrix_rows)):
 temp.append(modified_matrix_rows[index][column_index])
 columns.append(temp)
 return columns
def get_matrix_diagonals(matrix_rows):
 """Return matrix right & left diagonals by modifying the matrix to the right and to the left."""
 matrix_modified_right = []
 matrix_modified_left = []
 right_start_count = len(matrix_rows) - 1
 right_end_count = 0
 left_start_count = 0
 left_end_count = len(matrix_rows) - 1
 for index in range(len(matrix_rows)):
 matrix_modified_right.append(right_start_count * [0] + matrix_rows[index] + [0] * right_end_count)
 right_start_count -= 1
 right_end_count += 1
 for index in range(len(matrix_rows)):
 matrix_modified_left.append(left_start_count * [0] + matrix_rows[index] + [0] * left_end_count)
 left_start_count += 1
 left_end_count -= 1
 right_diagonals = \
 [[number for number in row if number != 0] for row in get_modified_matrix_columns(matrix_modified_right)]
 left_diagonals = \
 [[number for number in row if number != 0] for row in get_modified_matrix_columns(matrix_modified_left)]
 return right_diagonals, left_diagonals
def get_diagonal_partitions(matrix_rows, size):
 """Return right and left partitions of length size for n * n matrix."""
 right_diagonals, left_diagonals = get_matrix_diagonals(matrix_rows)
 all_diagonals = [diagonal for diagonal in right_diagonals + left_diagonals if len(diagonal) >= size]
 valid_diagonals = [diagonal for diagonal in all_diagonals if len(diagonal) == size]
 for diagonal in all_diagonals:
 if diagonal not in valid_diagonals:
 length = len(diagonal)
 for count in range(length - size + 1):
 valid_diagonals.append(diagonal[count: count + size])
 return valid_diagonals
def get_matrix_maximum_partition(partition_size, matrix_rows):
 """Return matrix partition of length partition_size with maximum number product."""
 matrix_columns = get_matrix_columns(matrix_rows)
 non_diagonal_partitions = get_non_diagonal_partitions(matrix_rows, matrix_columns, partition_size)
 diagonal_partitions = get_diagonal_partitions(matrix_rows, partition_size)
 all_partitions = list(non_diagonal_partitions) + diagonal_partitions
 products = [reduce(mul, partition) for partition in all_partitions]
 return max(products)
if __name__ == '__main__':
 matrix = get_matrix_rows(grid)
 print(get_matrix_maximum_partition(4, matrix))

• dfhwze: Are you really still a beginner? :p
• AJNeufeld: Sadly, @dfhwze, until they demonstrate that they can learn to solve the problem the smart way, instead of the brute force way, their Python skills may be improving but their problem solving skills might not.
• dfhwze: @AJNeufeld At least the readability has improved since the initial questions. I still remember those massive amounts of nested if-statements.
• dfhwze: We have kindly hinted to you (a couple of times) to absorb the feedback you get and try to use that in next questions. It seems you keep coming up with the same old strategy.
• dfhwze: I was too lazy to write a comprehension syntax and I know it's wrong Suppose the reviewers were also too lazy to write a good review..

Answer 1

Interesting, you recently posted an analysis of container performance, and found something like a 4-to-1 advantage of list comprehension over list.append(). Yet your code contains:

 temp = []
 for index in range(len(modified_matrix_rows)):
 temp.append(modified_matrix_rows[index][column_index])

Why not reap the benefits of your own analysis and code it with list comprehension?

 temp = [modified_matrix_rows[index][column_index]
 for index in range(len(modified_matrix_rows))]

Or better:

 temp = [row[column_index] for row in modified_matrix_rows]

Matrix transposition

You might want to keep this one in your back pocket:

def get_matrix_columns(matrix_rows):
 """Return a list of lists containing n * n matrix columns."""
 return list(map(*matrix_rows))

Of course, you'll want to study what it does, and why it works. The time will be well spent.

Rows, Columns, and Diagonals

If instead of a list of list, you simply had one long list:

m = list(map(int, grid.split()))

Then m[:20] is the first row, m[::20] is the first column, m[::20+1] is one of the main diagonals, and m[19:-1:20-1] is the other main diagonal.

Exercise left to student on how to generalize this to get all the relevant rows, columns and diagonals.