### The Problem

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?

### The Solution

First, we need that input grid in a format we can use.

open System

let runLength = 4
let gridSize = 20

let input = [|
"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"
|]

let splitBy (c : char) (s : string) =
s.Split([|c|], StringSplitOptions.RemoveEmptyEntries)

let ints =
input
|> Array.map (fun s ->
s
|> splitBy ' '
|> Array.map int32
)

let product arr =
arr |> Array.reduce (fun acc elem -> acc*elem)

We define a couple of values that tell us about the problem we’re solving. We’re looking for groups of runLength digits. gridSize tells us the grid is 20x20. input contains the grid itself, copy/pasted from the problem definition.

The ints function turns our input into an array of arrays, which allows us to reference rows and columns like so: ints.[row].[col]

Finally, similar to what we used in Problem 8, the product function uses Array.reduce to return the product of all the elements of an array.

Next, we need to figure out how to break this grid up into chunks of 4 numbers each. Let’s start with the easiest case: breaking each row up into groups of 4.

let byRows() =
ints
|> Seq.collect (fun r -> r |> Array.windowed runLength)

The function above uses Array.windowed to break up each row (which is an array itself) into groups of 4. For the first row of the grid, this function returns a sequence that looks like this:

[|8; 2; 22; 97|]
[|2; 22; 97; 38|]
[|22; 97; 38; 15|]
[|97; 38; 15; 0|]
[|38; 15; 0; 40|]
[|15; 0; 40; 0|]
[|0; 40; 0; 75|]
[|40; 0; 75; 4|]
[|0; 75; 4; 5|]
[|75; 4; 5; 7|]
[|4; 5; 7; 78|]
[|5; 7; 78; 52|]
[|7; 78; 52; 12|]
[|78; 52; 12; 50|]
[|52; 12; 50; 77|]
[|12; 50; 77; 91|]
[|50; 77; 91; 8|]

That’s the magic of the windowed function.

Next, we’ll tackle the problem of breaking up each column into groups of 4.

let byCols() =
let getCol c =
seq {
for r in 0..gridSize-1 do
yield ints.[r].[c]
}
|> Array.ofSeq
|> Array.windowed runLength

seq {
for c in 0..gridSize-1 do
yield! getCol c
}

The function above first turns the grid into arrays of columns, then uses Array.windowed to, once again, created groups of 4 numbers.

Now, onto diagonals, which are the most complicated case.

let byDiagonals() =
let getDownhill r c =
seq {
for i in 0..runLength - 1 do
yield ints.[r+i].[c+i]
} |> Array.ofSeq

let getUphill r c =
seq {
for i in 0..runLength - 1 do
yield ints.[r+i].[c-i]
} |> Array.ofSeq

seq {
for r in 0..gridSize - 1 do
for c in 0..gridSize - 1 do
if (r + runLength) < gridSize && (c + runLength) < gridSize then
yield getDownhill r c
if (r + runLength) < gridSize && (c - runLength) >= 0 then
yield getUphill r c
}

This function contains two functions inside it, getDownhill and getUphill. These return an array of 4 numbers either moving downhill (where both row and column increase) or uphill (where row increases and column decreases).

The main function body simply generates each possible position in the grid and, if possible, yields a downhill and an uphill sequence from that position.

With all that in place, we can finally get our answer:

[ byRows(); byCols(); byDiagonals() ]
|> Seq.concat
|> Seq.map product
|> Seq.max

The code above:

• Uses our three byXxx functions to generate all possible sequences of 4 numbers.
• Concatenates that into a single sequence consisting of 4-number arrays.
• Uses Seq.map to compute the product of each array
• Uses Seq.max to return the answer.
Other Posts in This Series