Project Euler Problem 11 in F#

Project Euler Problem 11 is an interesting one; when addressed with a functional approach it lends itself to be solved using function composition. Let's have a look at the question and then a possible solution:

In the 20x20 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 x 63 x 78 x 14 = 1788696.

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

let numbers =
    array2D [|
      [|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 dimensions = (Array2D.length1 numbers, Array2D.length2 numbers)

let horizontal_traverser (i, j) (iMax, jMax) f_4 =
    if (i > iMax) || (j + 4 > jMax) then 0
    else f_4 numbers.[i,j]  numbers.[i, j+1] numbers.[i,j+2] numbers.[i,j+3]

let vertical_traverser (i,j) (iMax, jMax) f_4 =
    if (i + 4 > iMax) || (j > jMax) then 0
    else f_4 numbers.[i,j] numbers.[i+1, j] numbers.[i+2, j] numbers.[i+3,j]

let diagonal_traverser_left_right (i, j) (iMax, jMax) f_4 =
    if (i + 4 > iMax) || (j + 4 > jMax) then 0
    else f_4 numbers.[i,j] numbers.[i+1, j+1] numbers.[i+2, j+2] numbers.[i+3,j+3]

let diagonal_traverser_right_left (i, j) (iMax, jMax) f_4 =
    if (i - 3 < 0) || (j + 4 > jMax) then 0
    else f_4 numbers.[i,j] numbers.[i-1, j+1] numbers.[i-2, j+2] numbers.[i-3,j+3]

let max_in_direction traverser f_4 =
    seq { for i in 0..fst dimensions - 1 do
              for j in 0..snd dimensions - 1 do
                  yield traverser (i,j) dimensions f_4 }
    |> Seq.max

let maximum f_4 =
    [| max_in_direction horizontal_traverser f_4;
       max_in_direction vertical_traverser f_4;
       max_in_direction diagonal_traverser_left_right f_4;
       max_in_direction diagonal_traverser_right_left f_4 |]
    |> Array.max

let problem_11 () =
    maximum (fun a b c d -> a * b * c * d)

• We first declare a two-dimensions array containing the 20x20 numbers that we need to explore. To do this we use F# Array2D Module. The same module is used also to compute a tuple containing the size of the two dimension arrays, which we'll use later on.
• We then proceed to define four traverser functions, one for each of these directions: horizontal, vertical, diagonal top-left to bottom-right and diagonal bottom-left to top-right. Each traverser takes as input a given item of the array and applies the supplied 4-parameters function to the starting item plus the next 3 items in a direction. Note how at this point we are not talking about a specific operation (product or sum) yet and we are concentrating on 4 items of the array at a time.
• Next we define the max_in_direction function that takes a traverser and a 4-parameters function and finds the maximum value in that particular direction (whatever it might be applying the given function).
• We are getting closer to the solution by defining the maximum one-dimension array, where each item is the maximum value in each of the four directions and then taking the highest one.
• We finally solve the problem by invoking the maximum function passing to it the product of four items as a lambda.

Note how easy it is to change the particular function that we use to aggregate the 4 items: suppose for example that we are interested in the 4 items giving the maximum sum, we could simply invoke:

maximum (fun a b c d -> a + b + c + d)