What is the greatest product of four adjacent numbers in the same direction(up, down, left, right or diagonally)

Question

1.00/5 (1 vote)

See more:

C++

<pre>
#include <iostream>
#include <vector>

long largestProduct(std::vector<std::vector<int> >arr)
{


    std::vector<long>products;
    for(int row=0; row<20; row++)
        {


            for(int col=0; col<20; col++)
                {

                    int left=col-4;
                    int right=col+4;

                    int down=row+4;
                    int up=row-4;

                    while(up<0)
                        {
                            up++;
                        }
                    while(down>20)
                        {
                            down--;
                        }

                    if(down-up>=4)
                        {
                            for(up; up<=down-4; up++)
                                {
                                    long product=1;
                                    int rowCount=up;
                                    int rowDist=rowCount+4;
                                    for(rowCount; rowCount<rowDist; rowCount++)
                                        {
                                            product=product*arr[rowCount][col];
                                        }
                                    products.push_back(product);
                                }
                        }





                    while(left<0)
                        {
                            left++;
                        }
                    while(right>20)
                        {
                            right--;
                        }

                     if(right-left>=4)
                        {

                            for(left; left<=right-4; left++)
                                {
                                    long product=1;
                                    int colCount=left;
                                    int colDist=colCount+4;
                                    for(colCount; colCount<colDist; colCount++)
                                        {
                                            product=product*arr[row][colCount];
                                        }
                                    products.push_back(product);
                                }
                        }



                            down=row+4;
                            up=row-4;
                            left=col-4;
                            right=col+4;

                            while(down>20)
                                {
                                    down--;
                                }
                            while(up<0)
                                {
                                    up++;
                                }
                            while(left<0)
                                {
                                    left++;
                                }
                            while(right>20)
                                {
                                    right--;
                                }


                     if(down-up>=4 && right-left>=4)
                        {

                            for(up; up<=down-4; up++)
                                {
                                    for(left; left<=right-4; left++)
                                        {
                                            int rowCount=left;
                                            int rowDist=rowCount+4;
                                            int colCount=left;
                                            int colDist=colCount+4;

                                            while(rowCount<rowDist)
                                                {
                                                    long product=1;
                                                    while(colCount<colDist)
                                                        {

                                                            product=product*arr[rowCount][colCount];
                                                            rowCount=rowCount+1;
                                                            colCount=colCount+1;

                                                        }
                                                        products.push_back(product);

                                                }


                                        }
                                }
                        }

                }
        }

        long MAX=0;
        for(int i=0; i<products.size(); i++)
            {

                if(products[i]>MAX)
                    {
                        MAX=products[i];
                    }

            }
            return MAX;
}

int main()
{
    std::vector< std::vector<int> >arr{

                                        {8,   2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
                                        {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
                                        {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
                                        {52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 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,  3, 45,  2, 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,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
                                        {24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
                                        {21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
                                        {78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
                                        {16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
                                        {86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
                                        {19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
                                        { 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
                                        {88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
                                        { 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
                                        {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
                                        {20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
                                        { 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48}

    };
    std::cout<<largestProduct(arr);

}

What I have tried:

I have tried by debugging but it gets complicated, I know that there are some values that count more than once but I will solve it, now my main problem is I want to understand what goes wrong

Posted 4-Jul-18 23:28pm

Member 13277493

Updated 5-Jul-18 1:18am

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Accepted Answer · 2018-07-04T23:51:00

Start by looking at what you are doing and simplifying it. Repeatedly, you do things like this:

while(down>20)
    {
        down--;
    }

Which doesn't need a loop:

C++

if (down > 20) down = 20;

Or even

C++

down = down > 20 ? 20 : down;

would be a lot better.
Then, you have nested loops within nested loops, within nested loops- that's messy, and also difficult to follow, as well as being inefficient.
Instead, write a function that takes an x and y address as parameters, and which returns the sum of the adjacent cells. That's pretty trivial (the only complications are ignoring edge effects but that is clear code to write) and doesn;t need a loop at all.
Test that, and then call it inside a loop comparing the result to the last maximum and the whole code becomes much, much easier to read, understand, and debug.

Patrice T · Accepted Answer · 2018-07-05T01:18:00

Quote:
What is the greatest product of four adjacent numbers in the same direction(up, down, left, right or diagonally)

Looks like you jumped to programming a little too fast.
It is always good to do an analyze of the problem: result of multiplication is the same, no matter the order of numbers.
So A*B*C*D = D*C*B*A
This imply that for any product down, you have a product up that is identical, the same for left and right. So you can drop up and left. if you check 4 diagonals, it is the same.
So by checking horizontal, vertical and 2 diagonals, you check all.

I think that code doing all horizontals, then code doing all verticals and then diagonals world be simpler to write and to check.

C++

long largestProduct(std::vector<std::vector<int> >arr)
{
// Check horizontal

// check vertical

// check diagonal

}

For the max, you don't need to use a vector, just actual value of max
and when a new product is greater than max, make it the new max.

What is the greatest product of four adjacent numbers in the same direction(up, down, left, right or diagonally)

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0