Question

How to find max product of 4 adjacent numbers in the same direction in a 20×20 grid with C++

Answer 1

#include <iostream>
#include <iomanip>
#include <ctime>

#define ROWS 20
#define COLS 20

void printGrid(int grid[][COLS], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            std::cout << std::setw(3) << grid[i][j] << " ";
        }
        std::cout << "\n";
    }
}

int generateRandomInteger(int first, int last) {
    return rand() % ((last + 1) - first) + first;
}

void generateRandomInteger(int grid[][COLS], int size) {
    srand(time(NULL));

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            grid[i][j] = generateRandomInteger(1, 100);
        }
    }
}

int FindMaxProduct(int grid[][COLS], int size) {
    int max = 0, product;
    int n1 = 0, n2 = 0, n3 = 0, n4 = 0;


    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 3; j++) {
            product = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3];
            if (product > max) {
                n1 = grid[i][j]; n2 = grid[i][j + 1]; n3 = grid[i][j + 2]; n4 = grid[i][j + 3];
                max = product;
            }
        }
    }
    
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 3; j++) {
            product = grid[j][i] * grid[j + 1][i] * grid[j + 2][i] * grid[j + 3][i];
            if (product > max) {
                n1 = grid[i][j]; n2 = grid[j + 1][i]; n3 = grid[j + 2][i]; n4 = grid[j + 2][i];
                max = product;
            }
        }
    }

    for (int i = 0; i < size - 3; i++) {
        for (int j = 0; j < size - 3; j++) {
            product = grid[j][i] * grid[j + 1][i + 1] * grid[j + 2][i + 2] * grid[j + 3][i + 3];
            if (product > max) {
                n1 = grid[j][i]; n2 = grid[j + 1][i + 1]; n3 = grid[j + 2][i + 2]; n4 = grid[j + 3][i + 3];
                max = product;
            }
        }
    }

    for (int i = 0; i < size - 3; i++) {
        for (int j = 3; j < size; j++) {
            product = grid[j][i] * grid[j - 1][i + 1] * grid[j - 2][i + 2] * grid[j - 3][i + 3];
            if (product > max) {
                n1 = grid[j][i]; n2 = grid[j - 1][i + 1]; n3 = grid[j - 2][i + 2]; n4 = grid[j - 3][i + 3];
                max = product;
            }
        }
    }

    std::cout << "\n" << n1 << " * " << n2 << " * " << n3 << " * " << n4 << " = ";

    return max;
}

int main() {
    int grid[ROWS][COLS] = { { 0 } };

    generateRandomInteger(grid, ROWS);

    printGrid(grid, ROWS);

    int maxProduct = FindMaxProduct(grid, ROWS);

    std::cout << maxProduct;
}




/*
run:

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

93 * 94 * 100 * 83 = 72558600

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>

int findGreatestProduct(const std::vector<std::vector<int>>& grid) {
    int maxProduct = 0;
    int rows = grid.size();
    int cols = grid[0].size();
    int maxnumber1, maxnumber2, maxnumber3, maxnumber4;

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            // Horizontal (right)
            if (j + 3 < cols) {
                int product = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3];
                if (product > maxProduct) {
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i][j + 1];
                    maxnumber3 = grid[i][j + 2];
                    maxnumber4 = grid[i][j + 3];
                }
                maxProduct = std::max(maxProduct, product);
            }

            // Vertical (down)
            if (i + 3 < rows) {
                int product = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j];
                if (product > maxProduct) {
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i + 1][j];
                    maxnumber3 = grid[i + 2][j];
                    maxnumber4 = grid[i + 3][j];
                }
                maxProduct = std::max(maxProduct, product);
            }

            // Diagonal (down-right)
            if (i + 3 < rows && j + 3 < cols) {
                int product = grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3];
                if (product > maxProduct) {
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i + 1][j + 1];
                    maxnumber3 = grid[i + 2][j + 2];
                    maxnumber4 = grid[i + 3][j + 3];
                }
                maxProduct = std::max(maxProduct, product);
            }

            // Diagonal (down-left)
            if (i + 3 < rows && j - 3 >= 0) {
                int product = grid[i][j] * grid[i + 1][j - 1] * grid[i + 2][j - 2] * grid[i + 3][j - 3];
                if (product > maxProduct) {
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i + 1][j - 1];
                    maxnumber3 = grid[i + 2][j - 2];
                    maxnumber4 = grid[i + 3][j - 3];
                }
                maxProduct = std::max(maxProduct, product);
            }
        }
    }
    
    std::cout << "maxnumber1: " << maxnumber1 << std::endl;
    std::cout << "maxnumber2: " << maxnumber2 << std::endl;
    std::cout << "maxnumber3: " << maxnumber3 << std::endl;
    std::cout << "maxnumber4: " << maxnumber4 << std::endl;

    return maxProduct;
}

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

    int result = findGreatestProduct(grid);
    
    std::cout << "Greatest product of 4 adjacent numbers: " << result << std::endl;
}



/*
run:

maxnumber1: 93
maxnumber2: 94
maxnumber3: 100
maxnumber4: 83
Greatest product of 4 adjacent numbers: 72558600

*/

 

70+ SQL courses for beginners and professionals