Question

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

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#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++) {
            printf("%4d", grid[i][j]);
        } 
        printf("\n");
    }
}
  
int generateRandomInteger(int min, int max) {
    return min + rand() / (RAND_MAX / (max - min + 1) + 1);
    // return rand() % (max - min + 1) + min;
}
      
void generateRandomMatrix(int matrix[][COLS], int size) {
    srand(time(NULL));
     
    for (int i = 0; i < size; i++) {     
        for (int j = 0; j < size; j++) {
            matrix[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;
            }
        }
    }

    printf("\n %d * %d * %d * %d = ", n1 , n2, n3, n4);

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

 91 * 97 * 100 * 97 = 85621900
 
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <stdio.h>

#define ROWS 20
#define COLS 20

int findGreatestProduct(int grid[ROWS][COLS]) {
    int maxProduct = 0;
    int maxnumber1 = 0, maxnumber2 = 0, maxnumber3 = 0, maxnumber4 = 0;

    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            // Horizontal
            if (j + 3 < COLS) {
                int product = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3];
                if (product > maxProduct) {
                    maxProduct = product;
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i][j+1];
                    maxnumber3 = grid[i][j+2];
                    maxnumber4 = grid[i][j+3];
                }
            }

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

            // Diagonal 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) {
                    maxProduct = product;
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i+1][j+1];
                    maxnumber3 = grid[i+2][j+2];
                    maxnumber4 = grid[i+3][j+3];
                }
            }

            // Diagonal 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) {
                    maxProduct = product;
                    maxnumber1 = grid[i][j];
                    maxnumber2 = grid[i+1][j-1];
                    maxnumber3 = grid[i+2][j-2];
                    maxnumber4 = grid[i+3][j-3];
                }
            }
        }
    }

    printf("maxnumber1: %d\n", maxnumber1);
    printf("maxnumber2: %d\n", maxnumber2);
    printf("maxnumber3: %d\n", maxnumber3);
    printf("maxnumber4: %d\n", maxnumber4);

    return maxProduct;
}

int main() {
    int grid[ROWS][COLS] = {
        {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);
    
    printf("Greatest product of 4 adjacent numbers: %d\n", result);
    
    return 0;
}



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

 

70+ SQL courses for beginners and professionals