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?

Solution

This large blocks of numbers may look daunting, but in reality the number of cases we have to check is pretty small. It’s small enough that we can check all of them and then take the maximum.

First, we’ll load the data line by line and then create a 2d array of integers that represents the problem data set:

def prepareData(): Array[Array[Int]] =
  loadFileAsLines().map(_.split(" ").map(_.toInt)).toArray

The loadFileAsLines() is a helper method that does exactly what its name says: it loads the file as a list of strings, where each string is a line.

Let’s define our search function like that:

private def findLargestProduct(matrix: Array[Array[Int]]): Long = ???

Because of how the data was loaded, matrix(0) would return the first row, and matrix(0)(0) will give us the first element within the first row.

So, we can iterate over all the elements like that:

for (col <- matrix.indices; row <- matrix(col).indices)

The .indices method is pretty convenient as it returns a range that corresponds to the array length, so we don’t need to worry about going out of bounds.

If we’re at the element of (0, 0), then naturally we can only check the product in three directions: down, right and diagonally (right, down). If we’re going from left to right, do we ever need to check the left direction?

Not really. Because if we’re checking the right direction at (0, 0), it will be the same as checking the left direction at (0, 3). In both cases we’re multiplying these elements: (0, 0), (0, 1), (0, 2), (0, 3).

Likewise, when checking the diagonals, we can check only those going down. Overall, this gives us four directions to check: “right”, “down”, “right-down”, “left-down”.

Checking each direction is a matter of defining right constraints, so we don’t go out of bounds. Let’s analyze how would that look for the “right” direction.

First, we need to define a condition: col < matrix(row).length - 3. The matrix(row).length returns the length of the first row. We could as well define a constant of 20, but let’s keep it dynamic as a good practice. With this check, we’re making sure that the last column we’re checking will be 16, so we can check elements 16, 17, 18, 19. Our array has 20 elements, but they’re indexed from 0, so the last element has index 19.

Let’s summarize it then. Our check for the “right” direction will look as follows:

var max: Long = 0
if (col < matrix(row).length - 3) {
   max = Math.max(max, matrix(row)(col) * matrix(row)(col + 1) * matrix(row)(col + 2) * matrix(row)(col + 3))
}

Now we just need to define the checks for other 3 directions and that’s it, we’ll have our solution.

Here’s the complete solution. It’s a mutable one, but just a little bit. We maintain a mutable, local max that keeps the maximum product we’ve found so far.

object Euler011M extends EulerApp {

  override def execute(): Long = findLargestProduct(prepareData())

  def prepareData(): Array[Array[Int]] =
    loadFileAsLines().map(_.split(" ").map(_.toInt)).toArray

  private def findLargestProduct(matrix: Array[Array[Int]]): Long = {
    var max: Long = 0

    for (col <- matrix.indices; row <- matrix(col).indices) {
      if (row < matrix.length - 3) {
        max = Math.max(max, matrix(row)(col) * matrix(row + 1)(col) * matrix(row + 2)(col) * matrix(row + 3)(col))
      }

      if (col < matrix(row).length - 3) {
        max = Math.max(max, matrix(row)(col) * matrix(row)(col + 1) * matrix(row)(col + 2) * matrix(row)(col + 3))
      }

      if ((col < matrix(row).length - 3) && (row > 3)) {
        max = Math.max(
          max,
          matrix(row)(col) * matrix(row - 1)(col + 1) * matrix(row - 2)(col + 2) * matrix(row - 3)(col + 3)
        )
      }

      if ((col < matrix(row).length - 3) && (row < matrix.length - 3)) {
        max = Math.max(
          max,
          matrix(row)(col) * matrix(row + 1)(col + 1) * matrix(row + 2)(col + 2) * matrix(row + 3)(col + 3)
        )
      }
    }

    max
  }
}

Keyboard shortcuts

A Guide to Project Euler in Scala

Largest Product in a Grid

Solution