RSS FEED

Project Euler: Problem 11

It's cold and rainy outside, let's move on to solve some other Euler problem, this time it would be problem No. 11:

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?

This particular task doesn't leave much space for imagination, and as zeros are included, it doesn't make sense to use previous products to speed it up a little bit. So, we'll keep it simple, with just one array of all the numbers (knowing the column count, we don't have to have each row as one array) we will iterate over the horizontals, verticals and in both diagonal ways. We already know the value of one of the non-zero products so we can use it as an initial value for our maximum. For the iterators, only additions would do (well, to keep it short, I'll use 2*colCount instead of colCount + colCount) and then we just multiply the four values. Easy this time.

Just for the fun of I've used fileStream this time, at least it keeps me from repeating the exact same code as the last time.

(
    fn getGrid filePath =
    (
        local row, lineNr = 1
        local result = #()
        local file = openFile filePath
        while NOT EOF file do
        (
            row = (filterString (readLine file) " ")
            join result (for i = 1 to row.count collect row[i] as integer)
            lineNr += 1
        )
        close file
        result
    )

    fn iterateOverGrid grid rowCount:20 colCount:20 =
    (
        local maxProduct = 1788696

        -- horizontal
        for i = 0 to (rowCount - 1) do
        (
            local index = i*colCount
            local horMax = amax \
                (for j = 1 to (colCount - 3) collect
                    grid[index += 1]*grid[index+1]*grid[index+2]*grid[index+3])

            if horMax > maxProduct do
                maxProduct = horMax
        )

        -- vertical
        for i = 1 to colCount do
        (
            local index = i
            local verMax = amax \
                (for j = 0 to (rowCount - 4) collect
                    grid[index]*grid[index += colCount]*grid[index+colCount]*grid[index+2*colCount])

            if verMax > maxProduct do
                maxProduct = verMax
        )

        -- diagonal 1
        for i = 0 to (rowCount - 4) do
        (
            local index = i*colCount
            local diff = colCount + 1
            local diagMax1 = amax \
                (for j = 1 to (colCount - 3) collect
                    grid[index += 1]*grid[index+diff]*grid[index+2*diff]*grid[index+3*diff])        

            if diagMax1 > maxProduct do
                maxProduct = diagMax1
        )

        -- diagonal 2
        for i = 3 to (rowCount - 1) do
        (
            local index = i*colCount
            local diff = colCount - 1
            local diagMax2 = amax \
                (for j = 1 to (colCount - 3) collect
                    grid[index += 1]*grid[index-diff]*grid[index-2*diff]*grid[index-3*diff])

            if diagMax2 > maxProduct do
                maxProduct = diagMax2
        )

        maxProduct
    )

    testGrid = getGrid "Z:\Euler\prob11.txt"
    iterateOverGrid testGrid
)

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.

This Post needs Your Comment!

Return to top