Project Euler

Problem 11: Largest Product in a Grid

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

The product of these numbers is \(1,788,696 = 26 \times 63 \times 78 \times 14\).

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

Let’s solve using Julia.

We can use a matrix for this problem which we’ll define as Grid below

Code

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]

20×20 Matrix{Int64}:
  8   2  22  97  38  15   0  40   0  …   5   7  78  52  12  50  77  91   8
 49  49  99  40  17  81  18  57  60     40  98  43  69  48   4  56  62   0
 81  49  31  73  55  79  14  29  93     67  53  88  30   3  49  13  36  65
 52  70  95  23   4  60  11  42  69     56   1  32  56  71  37   2  36  91
 22  31  16  71  51  67  63  89  41     54  22  40  40  28  66  33  13  80
 24  47  32  60  99   3  45   2  44  …  53  78  36  84  20  35  17  12  50
 32  98  81  28  64  23  67  10  26     67  59  54  70  66  18  38  64  70
 67  26  20  68   2  62  12  20  95     39  63   8  40  91  66  49  94  21
 24  55  58   5  66  73  99  26  97     78  96  83  14  88  34  89  63  72
 21  36  23   9  75   0  76  44  20     14   0  61  33  97  34  31  33  95
 78  17  53  28  22  75  31  67  15  …  80   4  62  16  14   9  53  56  92
 16  39   5  42  96  35  31  47  55     24   0  17  54  24  36  29  85  57
 86  56   0  48  35  71  89   7   5     37  44  60  21  58  51  54  17  58
 19  80  81  68   5  94  47  69  28     13  86  52  17  77   4  89  55  40
  4  52   8  83  97  35  99  16   7     32  16  26  26  79  33  27  98  66
 88  36  68  87  57  62  20  72   3  …  67  46  55  12  32  63  93  53  69
  4  42  16  73  38  25  39  11  24     18   8  46  29  32  40  62  76  36
 20  69  36  41  72  30  23  88  34     69  82  67  59  85  74   4  36  16
 20  73  35  29  78  31  90   1  74     71  48  86  81  16  23  57   5  54
  1  70  54  71  83  51  54  69  16     48  61  43  52   1  89  19  67  48

Let’s also start by identifying how we’ll move on this grid to find the maximum product.

Let’s notice that if we move along every position on the grid we can cover each possibility with four directions: up, diagonally up from left to right, right, and diagonally down from left to right.

There’s no need to have a left direction, a down direction, or the diagonal directions from right to left because the above directions cover all scenarios. Let’s demonstrate this with an example. At position Grid[7,9] = 26 (row 7, column 9) the product in the diagonally down from the left to right direction the product is \(26 \times 63 \times 78 \times 14\). This is the same product when we’re at position Grid[10,12] = 14 in the diagonally up from the right to left direction which is \(14 \times 78 \times 63 \times 28\).

The same will be true with the other directions. Therefore we can just consider the previous four directions because we can elimintate any unnecessary compututions for efficiency purposes.

In our code we can define the following - product1 refers to the product in the up direction - product2 refers to the product in the diagonally up direction - product3 refers to the product in the right direction - product4 refers to the product in the diagonally down direction

Therefore we have the following code

Code

# Initialize products
max_product = 1
product1 = 1
product2 = 1
product3 = 1
product4 = 1

prod_vector = []

# Used to determine position and direction of product
pos_m = 0
pos_n = 0
direction = 0

for rows = 1:20
    for cols = 1:20

        # Reset products and prod_vector when starting new position on grid
        product1 = 1
        product2 = 1
        product3 = 1
        product4 = 1
        prod_vector = []

        for up = 1:4

            # Boundary case
            if (rows - up + 1) == 0
                break
            end

            product1 = product1*Grid[rows - up + 1, cols] 
        end
        
        for diagonal_up = 1:4

            # Boundary case
            if ((rows - diagonal_up + 1) == 0) | ((cols + diagonal_up - 1) == 21)
                break
            end

            product2 = product2*Grid[rows - diagonal_up + 1, cols + diagonal_up - 1]
        end

        for right = 1:4

            # Boundary case
            if (cols + right - 1) == 21
                break
            end

            product3 = product3*Grid[rows, cols + right - 1]
        end

        for diagonal_down = 1:4

            # Boundary case
            if ((rows + diagonal_down - 1) == 21) | ((cols + diagonal_down - 1) == 21)
                break
            end

            product4 = product4*Grid[rows + diagonal_down - 1, cols + diagonal_down - 1]
        end
        
        # Add all products to prod_vector
        prod_vector = push!(prod_vector, product1, product2, product3, product4)
        
        # Update max product at every postion if condition is true, find max product
        if max_product < maximum(prod_vector)
            direction = argmax(prod_vector)
            max_product = maximum(prod_vector)
            pos_m = rows
            pos_n = cols
        end

    end
end

println("max_product = ", max_product)
println("row = ", pos_m)
println("col = ", pos_n)
println("direction = ", direction)

max_product = 70600674
row = 16
col = 4
direction = 2

Therefore we have that the greatest product is \(70,600,674 = 87 \times 97 \times 94 \times 89\) which is at position Grid[16,4] (row 16, column 4)in the diagonally up direction.