Project Euler Problem 11

Largest Product in a Grid

Project Euler presents the following Problem #11:

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

$$\text{08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08}\\ \text{49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00}\\ \text{81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65}\\ \text{52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91}\\ \text{22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80}\\ \text{24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50}\\ \text{32 98 81 28 64 23 67 10 \textcolor{red}{26} 38 40 67 59 54 70 66 18 38 64 70}\\ \text{67 26 20 68 02 62 12 20 95 \textcolor{red}{63} 94 39 63 08 40 91 66 49 94 21}\\ \text{24 55 58 05 66 73 99 26 97 17 \textcolor{red}{78} 78 96 83 14 88 34 89 63 72}\\ \text{21 36 23 09 75 00 76 44 20 45 35 \textcolor{red}{14} 00 61 33 97 34 31 33 95}\\ \text{78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92}\\ \text{16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57}\\ \text{86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58}\\ \text{19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40}\\ \text{04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66}\\ \text{88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69}\\ \text{04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36}\\ \text{20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16}\\ \text{20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54}\\ \text{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 x 63 x 78 x 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?

Helper Functions

For the solution to this problem, we can use a nested List<List<Int>> to store the provided numbers since there is no requirement to mutate the contents of the collection. But how can we build this representation of a grid?

Assuming that the grid is being read as input from a .txt file (with space-separated values), we can use the following function to process each line:

1import java.io.File
2
3/**
4 * Retrieves content of a test resource file, with each line transformed into a nested list.
5 *
6 * @param [lineTrim] characters to remove from the left & right of each file line.
7 * @param [lineSplit] characters to use as the delimiter when splitting a line.
8 * @param [transformation] function that takes either an entire line as an
9 * argument or, if split, individual elements in a line.
10 */
11fun <R> getTestResource(
12    filePath: String,
13    lineTrim: CharArray = charArrayOf(' ', '\n'),
14    lineSplit: String = " ",
15    transformation: (String) -> R
16): List<List<R>> {
17    return File(filePath).useLines { lines ->
18        lines.map { line ->
19            line.trim(*lineTrim).split(lineSplit).map(transformation)
20        }.toList()
21    }
22}
23
24fun main() {
25    val grid = getTestResource("path/to/file.txt", transformation = String::toInt)
26}

Line 11: This helper is set up as a generic function to ensure reusability across all Project Euler test files.

Line 17: useLines() returns the final value of the block callback and closes the reader once processing is complete.

Line 19: Here's a reminder of how Kotlin's spread operator works when a vararg-function, such as trim(), is called.

N.B. getTestResource() throws a FileNotFoundException if the pathname provided does not match an existing resource, so consider handling this if appropriate.

Now that we have a grid, let's also implement a small extension function to calculate the product of numbers in a List:

1fun List<Int>.product(): Int = reduce { acc, n -> acc * n }

N.B. This extension function will throw an UnsupportedOperationException if the collection is empty, which will not happen in our case. There is also no possibility of integer overflow given the problem's small numbers. Consider also handling these edge cases if choosing to use this function elsewhere.

Solution

The problem suggests multiple directions to search for the potential largest product: "up, down, left, right, or diagonally". Each direction can, of course, only be checked if the position of the current element allows for the expected amount of adjacent numbers. However, if we move methodically through each element in the grid, it can be observed that choosing to search all proposed directions leads to duplicate searches:

Instead, the directions can be reduced by the associative property of multiplication to: down, right, leading diagonal, and counter diagonal:

Note that the terms found by searching "down" are essentially the equivalent of searching right from the same position using a transposed grid.

Once the directions to search have been established, it's just a matter of getting the product of all applicable terms and storing the maximum value across each iteration:

1fun largestProductInGrid(grid: List<List<Int>>, terms: Int = 4): Int {
2    var largest = 0
3    for (row in grid.indices) {
4        for (col in 0..(grid[0].size - terms)) {
5            val right = grid[row].slice(col until (col + terms)).product()
6            val down = List(terms) { grid[col+it][row] }.product()
7            var leadingDiag = 0
8            var counterDiag = 0
9            if (row <= grid.size - terms) {
10                leadingDiag = List(terms) { grid[row+it][col+it] }.product()
11                counterDiag = List(terms) { grid[row+it][col+terms-1-it] }.product()
12            }
13            largest = maxOf(largest, right, down, leadingDiag, counterDiag)
14        }
15    }
16    return largest
17}

1fun main() {
2    val grid = List(4) { MutableList(4) { 0 } }
3    val portion: List<Int> = grid[0].slice(1..3)
4    grid.forEach { println(it) }
5    println("Slice -> $portion")
6    println("--------")
7    repeat(3) { grid[0][it + 1] = 1 }
8    grid.forEach { println(it) }
9    println("Slice -> $portion")
10}

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
Slice -> [0, 0, 0]
--------
[0, 1, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
Slice -> [0, 0, 0]

1fun main() {
2    val grid = List(4) { MutableList(4) { 0 } }
3    val portion: MutableList<Int> = grid[0].subList(1, 4)
4    grid.forEach { println(it) }
5    println("Sublist -> $portion")
6    println("--------")
7    repeat(3) { grid[0][it + 1] = 1 }
8    grid.forEach { println(it) }
9    println("Sublist -> $portion")
10    println("--------")
11    portion[0] = 2
12    grid.forEach { println(it) }
13    println("Sublist -> $portion")
14}

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
Sublist -> [0, 0, 0]
--------
[0, 1, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
Sublist -> [1, 1, 1]
--------
[0, 2, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
Sublist -> [2, 1, 1]

📚 Grids are a fairly common feature in Project Euler problems and, from here onwards, will require more than brute force iteration to solve in a reasonable time. Instead, algorithms, like breadth-first search and dynamic programming, will be heavily relied on and we'll even get a chance to be clever with combinatorics from as early as Problem #15.

Here's the full source code for this problem (and its corresponding test suite).

This solution set is also available in Python and in C++ on my GitHub.

Problem content on the Project Euler site is licensed under a Creative Commons (CC) License: CC BY-NC-SA 4.0. Solutions to only the first hundred problems are encouraged to be distributed publicly.

Thanks for reading!🏝️🔎🧭