Project Euler problem #11 – Largest product in a grid

I have recently solved the following Project Euler problem:

In the 20×20 grid below, four numbers along a diagonal line have been marked in red [here bold].

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 102638 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 956394 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 177878 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 351400 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 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×20 grid?

with the following Python code:

import itertools
import numpy as np

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]
]

def diagonals(matrix):
    '''
    Returns all diagonals from a matrix
    '''
    # http://stackoverflow.com/questions/6313308/get-all-the-diagonals-in-a-matrix-list-of-lists-in-python
    np_array = np.array(matrix)
    diags = [np_array[::-1, :].diagonal(i).tolist() for
             i in range(-np_array.shape[0]+1, np_array.shape[1])]
    diags.extend(np_array.diagonal(i).tolist() for
                 i in range(np_array.shape[1]-1, -np_array.shape[0], -1))
    return diags

def columns(matrix):
    '''
    Returns all columns from a matrix
    '''
    np_array = np.array(matrix)
    cols = [np_array[:, i].tolist() for i in range(np_array.shape[1])]
    return cols

def subsequences(lst, size):
    '''
    Returns all subsequences of certain size from a list
    '''
    # http://stackoverflow.com/questions/6670828/find-all-consecutive-sub-sequences-of-length-n-in-a-sequence
    return [list(subsequence) for subsequence in zip(*(lst[i:] for i in range(size)))]

def largest_adjacent_product(matrix, subsequence_size):
    '''
    Returns largest product of a subsequence of a certain size of adjacent
    numbers of a matrix. The subsequences can be horizontal, vertical and
    diagonal.
    '''
    diags = diagonals(matrix)
    cols = columns(matrix)

    horizontal_subsequences = itertools.chain.from_iterable(
        [subsequences(row, subsequence_size) for row in matrix])

    diagonal_subsequences = itertools.chain.from_iterable(
        [subsequences(diag, subsequence_size) for diag in diags])

    vertical_subsequences = itertools.chain.from_iterable(
        [subsequences(col, subsequence_size) for col in cols])

    horizontal_products = [np.prod(subsequence) for
                           subsequence in horizontal_subsequences]

    diagonal_products = [np.prod(subsequence) for
                         subsequence in diagonal_subsequences]

    vertical_products = [np.prod(subsequence) for
                         subsequence in vertical_subsequences]

    max_horizontal_product = max(horizontal_products)
    max_diagonal_product = max(diagonal_products)
    max_vertical_product = max(vertical_products)

    result = max(max_horizontal_product, max_diagonal_product, max_vertical_product)

    return result

if __name__ == '__main__':
    print(largest_adjacent_product(GRID, 4))

So, what are your thoughts?

If you look at largest_adjacent_product you should see that {}_subsequences, {}_products and max_{}_product are all created the same way.
If you make it its own function, and add subsequences, then you should be able to come to:

product = np.prod
chain = itertools.chain.from_iterable
max(product(s) for s in chain(zip(*(row[i:] for i in range(size))) for row in grid))

You can actually remove the chain.
This gives you code that is easy to read:

product = np.prod
max(product(s)
    for row in grid
    for s in zip(*(row[i:] for i in range(size))))

Alternately I’d use use the second answer for subsequence and use:

product = np.prod
max(product(row[i:i + size])
    for row in grid
    for i in range(len(row) - size + 1))

I’d say this is better,
space complexity is $O(1)$, as opposed to $O(kn)$ (or $O(ksqrt{n})$ for the modified ones above).
Time complexity should be the same at $O(kn)$,
and the readability of both the above are much better.
$k =$ size and $n =$ grid.

This would make your code much simpler:

def largest_subset(grid, size):
    product = np.prod
    return max(product(row[i:i + size])
               for row in grid
               for i in range(len(row) - size + 1))

def largest_adjacent_product(matrix, size):
    return max(largest_subset(i, size)
               for i in [matrix, columns(matrix), diagonals(matrix)])

I don’t like how you change matrix to np_array in both diagonals and columns.
I would use grid rather than both terms, and just overwrite grid when converted to a np array.
Alternately I’d pass both a np array in the first place.