Project Euler – Problem 11


What is the greatest product of four numbers on the same straight line in the 20 by 20 grid?

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

My Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Euler
{
    class Problem11 : IProblemBase
    {

        //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?

        public Problem11()
        {
        }   

        public string GetAnswer()
        {
            List<int[]> rows = new List<int[]>();
            rows.Add(new int[]{08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08});
            rows.Add(new int[]{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00});
            rows.Add(new int[]{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65});
            rows.Add(new int[]{52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91});
            rows.Add(new int[]{22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80});
            rows.Add(new int[]{24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50});
            rows.Add(new int[]{32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70});
            rows.Add(new int[]{67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21});
            rows.Add(new int[]{24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72});
            rows.Add(new int[]{21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95});
            rows.Add(new int[]{78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92});
            rows.Add(new int[]{16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57});
            rows.Add(new int[]{86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58});
            rows.Add(new int[]{19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40});
            rows.Add(new int[]{04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66});
            rows.Add(new int[]{88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69});
            rows.Add(new int[]{04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36});
            rows.Add(new int[]{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16});
            rows.Add(new int[]{20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54});
            rows.Add(new int[]{01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48});

            int currentSum = 0;
            int maxSum = 0;

            for (int i = 0; i < rows.Count; i++)
            {
                for (int j = 0; j < rows[i].Length; j++)
                {
                    int x = i;
                    int y = j;
                    int currentInt = rows[i][j];
                    int maxRight = rows[i].Length - 3;
                    int maxDown = rows.Count - 4;

                    if (x < maxRight && y < 3)
                    {
                        //right
                        currentSum = Right(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                        //downright
                        currentSum = DownRight(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                        //down
                        currentSum = Down(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                    }
                    else if (x < maxRight && y > 2 && y < maxRight)
                    {
                        //right
                        currentSum = Right(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                        //downright
                        currentSum = DownRight(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                        //down
                        currentSum = Down(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                        //downleft
                        currentSum = DownLeft(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                    }
                    else if (x < maxRight && y > 6)
                    {
                        //down
                        currentSum = Down(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                        //downleft
                        currentSum = DownLeft(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                    }
                    else if (x > maxDown && y < maxRight)
                    {
                        //right
                        currentSum = Right(rows, i, j, currentInt);
                        SetMaxSum(ref currentSum, ref maxSum);

                    }

                }

            }

            return maxSum.ToString(); ;

        }

        private static void SetMaxSum(ref int currentSum, ref int maxSum)
        {
            if (currentSum > maxSum)
            {
                maxSum = currentSum;
            }
        }

        private static int Right(List<int[]> rows, int i, int j, int currentInt)
        {
            int one = 0;
            int two = 0;
            int three = 0;
            int four = 0;

            one = currentInt;
            two = rows[i][j + 1];
            three = rows[i][j + 2];
            four = rows[i][j + 3];

            return one * two * three * four;
        }

        private static int DownRight(List<int[]> rows, int i, int j, int currentInt)
        {
            int one = 0;
            int two = 0;
            int three = 0;
            int four = 0;

            one = currentInt;
            two = rows[i + 1][j + 1];
            three = rows[i + 2][j + 2];
            four = rows[i + 3][j + 3];

            return one * two * three * four;
        }

        private static int Down(List<int[]> rows, int i, int j, int currentInt)
        {
            int one = 0;
            int two = 0;
            int three = 0;
            int four = 0;

            one = currentInt;
            two = rows[i + 1][j];
            three = rows[i + 2][j];
            four = rows[i + 3][j];

            return one * two * three * four;
        }

        private static int DownLeft(List<int[]> rows, int i, int j, int currentInt)
        {
            int one = 0;
            int two = 0;
            int three = 0;
            int four = 0;

            one = currentInt;
            two = rows[i + 1][j - 1];
            three = rows[i + 2][j - 2];
            four = rows[i + 3][j - 3];

            return one * two * three * four;
        }

    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: