Largest product in a grid - Project Euler 11

Question

A stab at Project Euler Problem 11: Largest product in a grid

"""
In the 20×20 grid below, four numbers along a diagonal line 
have been marked in red.

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

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?
"""
import numpy as np

grid = np.loadtxt("grid.txt")
all_products = []

def get_horizontal():
    for i in range(20):
        start, finish = 0, 4
        while finish <= 20:
            four_elements = grid[i, start:finish]
            all_products.append(np.prod(four_elements))
            start += 1
            finish += 1
    max_horizontal = max(all_products)
    return max_horizontal

def get_vertical():
    for i in range(20):
        start, finish = 0, 4
        while finish <= 20:
            four_elements = grid[start:finish, i]
            all_products.append(np.prod(four_elements))
            start += 1
            finish += 1
    max_horizontal = max(all_products)
    return max_horizontal

def get_right():
    for i in range(-16, 16):
        dgnl = np.diagonal(grid, i)
        start, finish = 0, 4
        while finish <= len(dgnl):
            four_elements = dgnl[start:finish]
            all_products.append(np.prod(four_elements))
            start += 1
            finish += 1
    max_right = max(all_products)
    return max_right

def get_left():
    for i in range(-16, 16):
        dgnl = np.diagonal(np.flipud(grid), i)
        start, finish = 0, 4
        while finish <= len(dgnl):
            four_elements = dgnl[start:finish]
            all_products.append(np.prod(four_elements))
            start += 1
            finish += 1
    max_left = max(all_products)
    return max_left

print(max(get_horizontal(), get_left(), get_right(), get_vertical()))

Hey, I'm really not too much of a coder, I just do these challenges for fun and I was hoping that maybe some of you have an idea on how to do this challenge a little more concise? I feel like I did way to much work to solve it.

Answer 1

all_products

At the top, you initialize all_products = []. Then you call get_horizontal(), which appends products of four_elements to all_products. Then you get and return the maximum.

Then you call get_left() which does the same thing ... but continues appending to the all_products list. When the maximum is computed, it is the maximum of both the horizontal and the left diagonals!

In other words, you don't need to find the maximum of the horizontal, left, right and vertical results. That is already being accidentally done.

get_horizontal()
get_left()
get_right()
print(get_vertical())    # Still returns the maximum over all 4 directions!

You should initialize all_products = [] inside the get_left, get_right, get_horizontal and get_vertical functions, and remove it from global scope.

Float or integer?

Your results ends in .0. All the numbers are integer numbers. You could load the grid as an integer matrix:

grid = np.loadtxt("grid.txt", dtype='i')

And now the answer is generated without a decimal point.

Looping

You've written code like this 4 times:

    start, finish = 0, 4
    while finish <= 20:
        four_elements = ... start:finish ...
        ...
        start += 1
        finish += 1

This is a simple loop from finish=4 to finish=20 (or finish=len(dgnl)). Start and end always differ by 4, so you could use finish - 4 instead of start. Or loop over start and use start + 4 for finish.

Eg)

    for start in range(16 + 1):
        four_elements = ... start : start+4 ...
        ...

With 4 copies of the that code, 3 less lines per copy, you've saved 12 lines.

Flip, and flip, and flip

def get_left():
    for i in range(-16, 16):
        dgnl = np.diagonal(np.flipud(grid), i)

Each time though this loop, you flipud(grid). That's 32 identical flips. Maybe you'd want to save this as a temporary result:

def get_left():
    flipped_grid = np.flipud(grid)
    for i in range(-16, 16):
        dgnl = np.diagonal(flipped_grid, i)

Question: Why 32? Perhaps you meant for i in range(-16, 16 + 1):? You were missing a diagonal!!! Twice!!!

Call functions more than once

Now, get_left() and get_right() are identical, save for that initial flip. You could pass the grid into get_right(), and get_left() could pass a flipped copy to get_right():

def get_right(grid):
    for i in range(-16, 16):
        dgnl = np.diagonal(grid, i)
        for start in range(len(dgnl) - 3):
            four_elements = dgnl[start:start + 4]
            all_products.append(np.prod(four_elements))
    max_right = max(all_products)
    return max_right

def get_left(grid):
    return get_right(np.flipud(grid))

Call functions more than once (reprise)

get_horizontal() and get_vertical() are duplicates also ... save for grabbing either the ith row or column. If you transposed the matrix, columns would become rows, and you could again use the same function.

Flip, Transpose ... Rotate!

If you flip the matrix, one left-up diagonals become left-down ones, but rows and columns are still rows and columns. If you transpose the matrix, rows become columns, columns become rows, but the left-up diagonals are still left-up diagonals.

If you rotate the matrix 90 degrees, rows become columns and left-up diagonals become left-down diagonals.

rotated = np.rot90(grid)
print(max(get_horizontal(grid), get_horizontal(rotated), get_right(grid), get_right(rotated)))

Using NumPy

All you've really used NumPy for is loading the grid from a file, flipping it, and extracting diagonals. It is much more powerful than that.

import numpy as np

grid = np.loadtxt("grid.txt", dtype='i')

print(max(np.max(grid[ :  , :-3] * grid[ :  , 1:-2] * grid[ :  , 2:-1] * grid[ :  , 3:]),
          np.max(grid[ :-3, :  ] * grid[1:-2,  :  ] * grid[2:-1,  :  ] * grid[3:  ,  :]),
          np.max(grid[ :-3, :-3] * grid[1:-2, 1:-2] * grid[2:-1, 2:-1] * grid[3:  , 3:]),
          np.max(grid[3:  , :-3] * grid[2:-1, 1:-2] * grid[1:-2, 2:-1] * grid[ :-3, 3:])))

Note: this works for 20 x 20 matrices, and 200 x 200 matrices equally well.

Okay, perhaps we should explain exactly what is going on there. Let's start with a 7x7 matrix, with random single-digit values:

>>> import numpy as np
>>> grid = np.random.randint(0, 10, (7, 7))
>>> grid
array([[8, 2, 3, 9, 9, 9, 3],
       [6, 2, 8, 0, 9, 4, 3],
       [0, 6, 9, 5, 6, 8, 8],
       [8, 5, 2, 6, 3, 0, 8],
       [5, 8, 0, 6, 7, 0, 3],
       [4, 3, 1, 0, 2, 5, 5],
       [4, 9, 5, 7, 2, 6, 0]])

grid[3:, :-3] will extract all the values starting at the 3rd row, and all the columns except the last 3 columns.

>>> grid[3:, :-3]
array([[8, 5, 2, 6],
       [5, 8, 0, 6],
       [4, 3, 1, 0],
       [4, 9, 5, 7]])

The grid[1:-2, 2:-1] extracts the 4x4 matrix one row up and one column to the right of the first:

>>> grid[2:-1, 1:-2]
array([[6, 9, 5, 6],
       [5, 2, 6, 3],
       [8, 0, 6, 7],
       [3, 1, 0, 2]])

And two rows up, two columns to the right:

>>> grid[1:-2, 2:-1]
array([[8, 0, 9, 4],
       [9, 5, 6, 8],
       [2, 6, 3, 0],
       [0, 6, 7, 0]])

And finally three rows up, three columns to the right ... in other words the top 4 rows, and the rightmost four columns:

>>> grid[:-3, 3:]
array([[9, 9, 9, 3],
       [0, 9, 4, 3],
       [5, 6, 8, 8],
       [6, 3, 0, 8]])

We can take these matrices, and multiply respective elements together:

>> grid[3:, :-3] * grid[2:-1, 1:-2] * grid[1:-2, 2:-1] * grid[:-3, 3:]
array([[3456,    0,  810,  432],
       [   0,  720,    0,  432],
       [ 320,    0,  144,    0],
       [   0,  162,    0,    0]])

For instance, the top-left corners contain 8, 6, 8 and 9, and the product of those is 8*6*8*9 = 3456. Looking at the original matrix, we can see these values in a diagonal starting at row 3, column 0 and going up to row 0, column 3.

The next diagonal contains 5, 5, 9, 0, 9. 5*5*9*0 = 0 and 5*9*0*9 = 0, which is the next diagonal of our product matrix.

The largest product in that matrix?

>>> np.max(grid[3:, :-3] * grid[2:-1, 1:-2] * grid[1:-2, 2:-1] * grid[:-3, 3:])
3456

The other 3 expressions take different adjacent rectangular regions, multiply them together, and find the maximums for the other diagonal and the rows and columns.

Answer 2

(Disclaimer -- I too am a beginner here and I am happy to read your comments.)

The code gets repeated a lot in methods get_horizontal, get_vertical, ...

One idea to fight this is to write a function that gets the starting position, difference in the x-axis dx, and difference in the y-axis dy (possibly also the number of numbers to multiply -- in this case 4).

This leads to another problem that we do not want to address out of the grid. We can have another method that returns whether or not your indexes always stay inside the grid.

""" Solve Euler problem 11: https://projecteuler.net/problem=11 """
import numpy as np

def all_in_grid(start_x, start_y, dif_x, dif_y, numbers):
    """Check if all positions are in the grid."""
    for i in range(numbers):
        if not (
                0 <= start_x + i*dif_x < GRID.shape[0]
                and 0 <= start_y + i*dif_y < GRID.shape[1]
                ):
            return False
    return True


def product(start_x, start_y, dif_x, dif_y, numbers):
    """Return multiple of the numbers in the grid.

    return GRID[start_x][start_y] * GRID[start_x+dif_x][start_y+dif_y]
        * ... * GRID[start_x + (numbers-1)*dif_x][start_y + (numbers-1)*dif_y]
    """
    prod = 1
    for i in range(numbers):
        prod *= GRID[start_x + (i*dif_x)][start_y + (i*dif_y)]
    return prod


def max_in_direction(dif_x, dif_y, numbers=4):
    """Return maximum in the given direction."""
    return max(
        product(start_x=x, start_y=y, dif_x=dif_x, dif_y=dif_y, numbers=numbers)
        for x in range(GRID.shape[0])
        for y in range(GRID.shape[1])
        if all_in_grid(start_x=x, start_y=y, dif_x=dif_x, dif_y=dif_y, 
numbers=numbers)
        )


GRID = np.loadtxt("grid.txt")
GRID = GRID.astype(int)

SOLUTION = max(
        max_in_direction(1, 0),
        max_in_direction(0, 1),
        max_in_direction(1, 1),
        max_in_direction(1, -1),
        )
print(SOLUTION)

It would probably be a good idea to convert this solution to a one which would use numpy product instead of looping in python.