"Finding the Greatest Products in a Matrix, Using a Two-Dimensional Arrays"

Question

Hello Stackoverflow! Today I have a question about getting started with an assignment I have. The objective of the assignment is to create a function, find_greatest_product(), that takes an array argument and returns the max product of four adjacent numbers that can be up, down, left, right, diagonally, or in a box formation in the N × M grid/matrix.

What I already have posted is my exact code that creates an array and populates it with a random number from 0 to 50 for the sake of testing. What I don't know is how to create an algorithm that can scan the entire array for the objective. I have a method that can find the greatest product in a 2x2 box, but the straight and diagonal lines are proving difficult. Any help, input, or suggestions are very welcome. Here is my pre-exsisting code:

int find_greatest_product(int **newArray, int &r, int &c){
    //find the greatest product of 4 adjacent numbers, in any direction.
}

int test_array(){
    //error handling 
}

int print_array(int **newArray, int &r, int &c){
    for (int i = 0; i < c; ++i)
    {
        for (int j = 0; j < r; ++j)
        {
            cout << newArray[i][j] << ' ';
        }
        cout << endl;
    }
}

int create_array(int r, int c){
    srand((unsigned)time(0));

    int** newArray = new int*[r];
    for (int i = 0; i < r; ++i)
    {
        newArray[i] = new int[c];
        for (int j = 0; j < c; ++j)
            newArray[i][j] = rand() % 50 + 1;
    }

    print_array(newArray, r, c);
}



int main(int argc, char* argv[]) {

    int rows, col;

    cout << "enter rows : " << endl;
    cin >> rows;
    cout << "enter cols : " << endl;
    cin >> col;

    create_array(rows, col);

}

Also, for those interested, here is the original problem statement:

Problem Statement

Funny question. Explain me how in your code you'll pass the array you've created in `create_array()` back to main ? — Christophe, Mar 04 '15 at 20:56
@George Gall There are many users with nick Stackoverflow. What user are you greeting?:) — Vlad from Moscow, Mar 04 '15 at 20:56
@Christophe would it be possible to dereference it in the main? — George Gall, Mar 04 '15 at 20:59
What part of them is proving difficult? How have you tried to solve the problem? — NathanOliver, Mar 04 '15 at 21:06
Ok ! Let's do some progress together: start change the code, so to return the array pointer to main(). To verify that it works, call the print_array() from main. Finally organise somehow that all these pointers will get freed when you leave main(). Once this basic stuff is done, I come bck to you — Christophe, Mar 04 '15 at 21:13
srand should only be called once per program. That means calling `create_array` more than once in your program could cause problems. — Neil Kirk, Mar 06 '15 at 01:48

Zeeshan Ali Khan · Accepted Answer · 2015-03-05T06:54:56.810

This algorithm will give you the max product.But dry run this code and make an understanding of how this algorithm work. I haven't added the functionality to find row, col or direction(vertical,down etc). Think and update this algorithm to add these functionalities.

int find_greatest_product(int **newArray, int &r, int &c)
{
    int max_product=0, p1=0, p2=0, p3=0;
    for(int i=0; i< r-3; i++)
    {
        for(int j=0; j<c-3; j++)
        {
            //down
            max_product = newArray[i][j]*newArray[i+1][j]*newArray[i+2][j]*newArray[i+3][j];
            //right_horizental
            p1 = newArray[i][j]*newArray[i][j+1]*newArray[i][j+2]*newArray[i][j+3];
            if(p1 > max_product)
                max_product = p1;
            //diagonally_right_down
            p2 = newArray[i][j]*newArray[i+1][j+1]*newArray[i+2][j+2]*newArray[i+3][j+3];
            if(p2 > max_product)
                max_product = p2;
            //box
            p3 = newArray[i][j]*newArray[i][j+1]*newArray[i+1][j]*newArray[i+1][j+1];
            if(p3 > max_product)
            max_product = p3;
        }
    }

    return max_product;
}

there was a bit of mistake in this. I have corrected it. Hope so it will work fine now. you can compare both code and see what my mistake was

int find_greatest_product(int **newArray, int &r, int &c)
{
    int max_product=0, p0 = 0, p1=0, p2=0, p3=0;
    for(int i=0; i< r; i++)
    {
        for(int j=0; j<c; j++)
        {
            if(i < r-3)
            {
                //down
                p0 = newArray[i][j]*newArray[i+1][j]*newArray[i+2][j]*newArray[i+3][j];
                if(p0 > max_product)
                    max_product = p0;
            }
            if(i < r-3 && j < c-3 )
            {
                //diagonally_right_down
                p2 = newArray[i][j]*newArray[i+1][j+1]*newArray[i+2][j+2]*newArray[i+3][j+3];
                if(p2 > max_product)
                    max_product = p2;
            }
            if(j < c-3)
            {
                //right_horizental
                p1 = newArray[i][j]*newArray[i][j+1]*newArray[i][j+2]*newArray[i][j+3];
                if(p1 > max_product)
                    max_product = p1;
            }
            if(i < r-1 && j < c-1)
            {
                //box
                p3 = newArray[i][j]*newArray[i][j+1]*newArray[i+1][j]*newArray[i+1][j+1];
                if(p3 > max_product)
                    max_product = p3;
            }
        }
    }

    return max_product;
}

This is a very similar algorithm to the one I came up with on my own. Good answer! I will make a test program using this and see if it works. — George Gall, Mar 05 '15 at 05:03
it works great. Another question I have is what could I add to the print function that adds a '0' in front of single digit numbers? — George Gall, Mar 05 '15 at 21:16
this question is related to the term called padding zeros ... following post will help you in doing so: http://stackoverflow.com/questions/1714515/how-can-i-pad-an-int-with-leading-zeros-when-using-cout-operator — Zeeshan Ali Khan, Mar 06 '15 at 16:39

score 1 · Answer 2 · edited Mar 05 '15 at 07:09

int find_greatest_product (int **newArray, int &r, int &c)
{
//find the greatest product of 4 adjacent numbers, in any direction.


//greater Calc  deisgnes  the  attributes  of our  result ( the  coordonates , the sahp "direction"  and  the  current  multiplication  "produit")
greaterCalc maxP(0,0,0,"none");

for(int i = 0 ;  i  <  r ;  i++)
{
    for(int j = 0; j < c ;  j++)
    {
        long  produitHorizontal  = 1,produitVertical = 1, produitDiagonal=1;

        //We  check here  the  4  horizontal  neighbours
        if(c-j >= 4)
        {   
            for(int l = j,k=0 ;   k < 4 ;k++, l++)
                produitHorizontal *= newArray[i][l];

            //If the product  is  more than  our  MaxP,  we just update,  and  we  continue
            if(produitHorizontal > maxP.produit )
                {  
                    maxP.x=j;
                    maxP.y=i;
                    maxP.produit = produitHorizontal;
                    maxP.direction = "horizontal";
                }
        }       


        //We  check here  the  4  vertical  neighbours
        if(r-i >= 4)
        {   for(int l = i, k=0 ;   k < 4 ;k++,l++)
                produitVertical *= newArray[l][j];

        //If the product  is  more than  our  MaxP,  we just update,  and  we  continue
        if(produitVertical > maxP.produit )
           {
            maxP.x=j;
            maxP.y=i;
            maxP.produit = produitVertical;
            maxP.direction = "vertical";

           }
        }

        //We  check here  the  4  diagonal  neighbours
        if(r-i >= 4 && c-j >= 4 )
        {       
            for(int l = i,m = j, k=0 ;   k < 4 ;k++,l++,m++)
                    produitDiagonal *= newArray[l][m];

            //If the product  is  more than  our  MaxP,  we just update,  and  we  continue
            if(produitDiagonal > maxP.produit )
                    {
                    maxP.x=j;
                    maxP.y=i;
                    maxP.produit = produitDiagonal;
                    maxP.direction = "diagonal";
                    }
        }
    }
}

cout<<endl<<endl <<"Max Prod : "<<maxP.produit   <<"  Position : row"<<maxP.y +1  <<", col" <<maxP.x +1  <<" Shape : "<<maxP.direction <<endl;
return 0;
}

"Finding the Greatest Products in a Matrix, Using a Two-Dimensional Arrays"

2 Answers2