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 48The 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
byXxxfunctions to generate all possible sequences of 4 numbers. - Concatenates that into a single sequence consisting of 4-number arrays.
- Uses
Seq.mapto compute the product of each array - Uses
Seq.maxto return the answer.