Skip to main content

Project Euler #011

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 any direction (up, down, left, right, or diagonally) in the 20 × 20 grid?

//In the 2020 grid below, four numbers along a diagonal line have been marked in red.
//What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?
module E011



let data =
    ["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 matrix = data |> List.map (fun vector -> vector.Split(' ') |> Seq.map (fun number -> System.Int32.Parse(number)) |> Seq.toList)



// Reorder the matrix so that it reads from top to bottom instead
let vertical_matrix (matrix:list<list<int>>) = [0..(matrix.Length - 1)] |> List.map (fun x -> [0..(matrix.Length - 1)] |> List.map (fun y -> matrix.[y].[x]))



// Rotate the matrix so that the bottom left corder appears on top, all rows diagonal
let diagonalmatrixbottomlefttotopright (matrix:list<list<int>>) = 
    let max = matrix.Length - 1
    ([0..max] |> List.map (fun x -> [(max - x)..max] |> List.mapi (fun i y -> [i;y]))) @ ([1..max] |> List.map (fun x -> [0..(max - x)] |> List.map (fun y -> [(x + y);y]))) // Get the coords
        |> List.map (fun row -> row |> List.map (fun coord -> matrix.[coord.[1]].[coord.[0]])) // Map coords to matrix



// Rotate the matrix so that the top left corder appears at the top, all rows diagonal
let diagonalmatrixtoplefttobottomright (matrix:list<list<int>>) =
    let max = matrix.Length - 1
    ([0..max] |> List.map (fun x -> [0..x] |> List.mapi (fun i y -> [i;(x - y)]))) @ ([1..max] |> List.map (fun x -> [0..(max - x)] |> List.mapi (fun i y -> [(y + x);(max - i)]))) // Get the coords
        |> List.map (fun row -> row |> List.map (fun coord -> matrix.[coord.[1]].[coord.[0]])) // Map coords to matrix



let rec Take (vector:list<int>) n =
    vector |> List.toSeq |> Seq.take n |> Seq.toList



let rec findlargestproduct (vector:list<int>) numberofparts result =
    if vector.Length >= numberofparts then
        let product = Take vector numberofparts |> List.fold (fun acc x -> acc * x) 1
        if (product > result) then
            findlargestproduct vector.Tail numberofparts product
        else
            findlargestproduct vector.Tail numberofparts result
    else
        result



let rec findlargestproductinmatrix matrix numberofparts result =
    match matrix with
    | head :: tail -> 
        let subproduct = findlargestproduct head numberofparts 0
        if  subproduct > result then
            findlargestproductinmatrix tail numberofparts subproduct
        else
            findlargestproductinmatrix tail numberof_parts result
    | [] -> result



let solution = lazy ([
                        findlargestproductinmatrix matrix 4 0; 
                        findlargestproductinmatrix (verticalmatrix matrix) 4 0; 
                        findlargestproductinmatrix (diagonalmatrixbottomlefttotopright matrix) 4 0; 
                        findlargestproductinmatrix (diagonalmatrixtoplefttobottom_right matrix) 4 0
                     ] |> List.max)

comments powered by Disqus