The maximum amount of hourglass is possible in an array of 6 * 6
In 2D array, a question arises that says
Given a 6 * 6 matrix, we should print the largest (maximum) hourglass sum found in the matrix. The hourglass is described as:
a b c
d
e f g
Input example
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
Output example
19
Explanation
The sample matrix contains the following hourglass:
1 1 1 1 1 0 1 0 0 0 0 0
1 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0
0 0 2 0 2 4 2 4 4 4 4 0
1 1 1 1 1 0 1 0 0 0 0 0
0 2 4 4
0 0 0 0 0 2 0 2 0 2 0 0
0 0 2 0 2 4 2 4 4 4 4 0
0 0 2 0
0 0 1 0 1 2 1 2 4 2 4 0
The hourglass with the maximum amount (19) is
2 4 4
2
1 2 4
I wrote a program where I made a function to calculate the sum of an hourglass. Now I have created a loop that calls this function for every four hourglass the row is available. And for every four lines the hourglass can create.
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int sum(int a[6][6],int i,int j)
{
int n=i+3;
int m=j+3;
int sum=0;
for(i;i<n;i++)
{
for(j;j<m;j++)
{
if(i==n-2)
{
sum += a[i][j+1];
break;
}
else
sum += a[i][j];
}
}
// printf("%d\t",sum);
return sum;
}
int main(){
int arr[6][6];
int i,j,n,k;
int max=0;
for(int arr_i = 0; arr_i < 6; arr_i++){
for(int arr_j = 0; arr_j < 6; arr_j++){
scanf("%d",&arr[arr_i][arr_j]);
}
}
for(int i=0;i<4;i++)
{
k=0;
while(k<4)
{
n=sum(arr,i,k);
// printf("%d\t",n);
k++;
if(n>max)
max=n;
}
}
printf("%d",max);
return 0;
}
Can anyone tell me where I am going wrong or is this method not the right way to solve this problem?
My program outputs 10
as output.
source to share
There is probably a mistake in your function sum
. The way you did it was a little over the top, it would be much easier (and readable!) For you to do it like this:
#define GRID_SIZE (6)
int sum(int a[GRID_SIZE][GRID_SIZE], int i, int j)
{ // Define an hourglass by the index i,j of its central element
int sum = a[j-1][i-1] + a[j-1][i] + a[j-1][i+1] +
a[j][i] +
a[j+1][i-1] + a[j+1][i] + a[j+1][i+1];
return sum;
}
Then just make sure you iterate with normal values (at [1, len-2]):
for (int i = 1; i < (GRID_SIZE-1); i++)
{
for (int j = 1; j < (GRID_SIZE-1); j++)
{
n = sum(arr, i, j);
if (n > max)
max = n;
}
}
Edit: make sure it works here: http://www.cpp.sh/46jhy
Thanks, it was fun :-).
PS: Make sure you check some coding standards document, it will make your life much easier in the long run, just search for "C code code standard" and get used to trying to work with the one you like. Unless you're doing something new and on its own, you probably have to follow a standard and maybe not even have a say in which one, so check out the general rules and get used to the next, whichever is you like.
source to share
There are a few frills here - four different ways to write the "hourglass sum" function. For the reasons stated in user3629249's comment , I renamed the functions to hourglass_N
(for N to 1..4). Of these options, it is hourglass_1()
pretty neat for that particular shape, but hourglass_2()
more easily adaptable to other shapes.
The test code handles matrices with negative maximum sums correctly.
#include <assert.h>
#include <stdio.h>
enum { ARR_SIZE = 6 };
static int hourglass_1(int a[ARR_SIZE][ARR_SIZE], int i, int j)
{
assert(i >= 0 && i < ARR_SIZE - 2 && j >= 0 && j < ARR_SIZE - 2);
int sum = a[i+0][j+0] + a[i+0][j+1] + a[i+0][j+2]
+ a[i+1][j+1] +
a[i+2][j+0] + a[i+2][j+1] + a[i+2][j+2];
return sum;
}
static int hourglass_2(int a[ARR_SIZE][ARR_SIZE], int i, int j)
{
assert(i >= 0 && i < ARR_SIZE - 2 && j >= 0 && j < ARR_SIZE - 2);
static const int rows[] = { 0, 0, 0, 1, 2, 2, 2 };
static const int cols[] = { 0, 1, 2, 1, 0, 1, 2 };
enum { HG_SIZE = sizeof(rows) / sizeof(rows[0]) };
int sum = 0;
for (int k = 0; k < HG_SIZE; k++)
sum += a[rows[k]+i][cols[k]+j];
return sum;
}
static int hourglass_3(int a[ARR_SIZE][ARR_SIZE], int i, int j)
{
assert(i >= 0 && i < ARR_SIZE - 2 && j >= 0 && j < ARR_SIZE - 2);
int sum = 0;
for (int i1 = 0; i1 < 3; i1++)
{
for (int j1 = 0; j1 < 3; j1++)
{
if (i1 == 1)
{
sum += a[i + i1][j + j1 + 1];
break;
}
else
sum += a[i + i1][j + j1];
}
}
return sum;
}
static int hourglass_4(int a[ARR_SIZE][ARR_SIZE], int i, int j)
{
assert(i >= 0 && i < ARR_SIZE - 2 && j >= 0 && j < ARR_SIZE - 2);
int n = i + 3;
int m = j + 3;
int sum = 0;
for (int i1 = i; i1 < n; i1++)
{
for (int j1 = j; j1 < m; j1++)
{
if (i1 == n - 2)
{
sum += a[i1][j1 + 1];
break;
}
else
sum += a[i1][j1];
}
}
return sum;
}
typedef int (*HourGlass)(int arr[ARR_SIZE][ARR_SIZE], int i, int j);
static void test_function(int arr[ARR_SIZE][ARR_SIZE], const char *tag, HourGlass function)
{
int max_sum = 0;
int max_row = 0;
int max_col = 0;
for (int i = 0; i < (ARR_SIZE-2); i++)
{
for (int j = 0; j < (ARR_SIZE-2); j++)
{
int n = (*function)(arr, i, j);
if (n > max_sum || (i == 0 && j == 0))
{
max_sum = n;
max_row = i;
max_col = j;
}
}
}
printf("%s: %3d at (r=%d,c=%d)\n", tag, max_sum, max_row, max_col);
}
int main(void)
{
int arr[ARR_SIZE][ARR_SIZE];
for (int i = 0; i < ARR_SIZE; i++)
{
for (int j = 0; j < ARR_SIZE; j++)
{
if (scanf("%d", &arr[i][j]) != 1)
{
fprintf(stderr, "Failed to read integer (for row %d, col %d)\n", i, j);
return 1;
}
}
}
test_function(arr, "hourglass_1", hourglass_1);
test_function(arr, "hourglass_2", hourglass_2);
test_function(arr, "hourglass_3", hourglass_3);
test_function(arr, "hourglass_4", hourglass_4);
return 0;
}
For different different datasets, the code gives the correct answer.
Install 1:
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
hourglass_1: 19 at (r=3,c=2)
hourglass_2: 19 at (r=3,c=2)
hourglass_3: 19 at (r=3,c=2)
hourglass_4: 19 at (r=3,c=2)
Install 2:
-1 -1 -1 +0 +0 +0
+0 -1 +0 +0 +0 +0
+1 -1 +1 +0 +0 +0
+0 +0 -2 +4 -4 +0
+0 +0 +0 +2 +0 +0
+0 +0 +1 +2 -4 +0
hourglass_1: 7 at (r=2,c=2)
hourglass_2: 7 at (r=2,c=2)
hourglass_3: 7 at (r=2,c=2)
hourglass_4: 7 at (r=2,c=2)
Install 3:
-7 -2 -9 -7 -4 -4
-6 0 -7 -5 -8 -1
-9 -1 -2 -1 -3 -3
-9 -1 -3 -6 -2 -9
-8 -1 -3 -7 -7 -9
0 -3 -5 -2 -2 -5
hourglass_1: -18 at (r=2,c=1)
hourglass_2: -18 at (r=2,c=1)
hourglass_3: -18 at (r=2,c=1)
hourglass_4: -18 at (r=2,c=1)
Install 4:
-7 -7 0 -7 -8 -7
-9 -1 -5 -6 -7 -8
-2 0 -7 -7 -6 -3
-5 -3 -1 -6 -3 -1
-3 -5 0 -5 0 -7
-1 -2 -8 -8 -9 -9
hourglass_1: -20 at (r=2,c=0)
hourglass_2: -20 at (r=2,c=0)
hourglass_3: -20 at (r=2,c=0)
hourglass_4: -20 at (r=2,c=0)
source to share