Finding 4 Numbers in a 2D array

[XboxOne2019]

Hello everyone, we have an assignment to manipulate 2D arrays and I have written everything for the code except the last part, which I am posting about. We have a 15x15 array and I will populate the values for you. I have already read from a file into the array, printed them, found highest/lowest in certain columns, etc.

Instructions for last part: Write a function (or functions) that will find 4 adjacent numbers (horizontal, vertical, or diagonal) in the array that sums to the largest value. The four numbers have to be adjacent values in one of 8 directions. Before your write code for this 4 adjacent number task, think through what is needed for this process and you will see that of the 8 directions, you only have to deal with half of them. Another note: you may see that adding three rows to top and to bottom and adding three columns to left and right of the array may save you a lot of coding (‘if’ statements for boundary checks). //not sure how adding more columns helps?

We are not allowed prints in the functions, only pass by value. Printing has to do be done in main. My issue is figuring out the logic to find 4 numbers in the array that equal the largest which is = 82. My idea was to step through each column and find 4 numbers and test them T/F. Not sure how to do that though. Any suggestions would be nice. Please be patient with me, I am still pretty new and we have not covered vectors, pointers, classes, we can only use user-created functions, etc.

24 50 17 -17 52 7 61 41 45 47 -12 28 64 10 44 
74 78 25 10 19 74 -13 -15 36 75 65 4 -1 1 78 
30 9 54 21 52 -5 50 82 18 77 -14 -6 5 16 56 
47 24 -6 36 51 30 27 45 40 20 42 6 24 12 61 
-1 18 73 25 71 -11 23 25 47 31 29 -12 73 12 53 
33 -11 -16 76 31 12 6 67 37 39 23 49 59 14 -9 
27 22 9 6 20 21 1 65 12 24 16 -2 22 41 -13 
13 60 -11 56 69 4 28 7 55 53 12 60 56 80 -5 
69 73 44 19 38 50 38 57 14 35 33 33 24 7 49 
13 -10 74 -10 20 40 70 36 66 28 -8 -8 41 4 71 
5 29 -11 13 -4 51 -17 74 45 38 -7 42 7 20 31 
66 78 24 -15 33 74 19 57 3 79 4 31 82 51 67 
64 17 36 82 1 21 -17 71 10 50 11 76 31 66 -10 
4 -7 0 -4 -3 -8 -1 18 34 -17 32 2 39 81 -14 
7 -9 27 -8 72 -15 78 68 76 26 6 70 -3 -14 31 

 int highestArray(int arr[][15])  //function to find largest value 
 {
     int c, r, highest=arr[0][0];
     for(r=0;r<15;r++)
     {
         for(c=0;c<15;c++)
         {
             if(arr[r][c]>highest)
             {
                 highest=arr[r][c];
             }
         }
     }
             return highest;
 }
 
//function call in main 
highestArray=highestArray(array2D);
cout<<"highest in array: "<<highestArray<<endl;

[jonnin]

make a 15+3 by 15+3:
int arr[18][18]; //like this
and pad the outers with zeros (fill it with zeros on initialize, is one way)
then change what you have to populate the inner 15x15 with the values.
now you can add up safely without going out of bounds.

feel free to print in the function as you code it so you can debug and see what you are doing, and remove the prints later to comply with your requirement.

I see 2 ways to read that.
find the 4 that sum to the *largest sum of 4 numbers*
or as you said it, you can also read that as *sum == the biggest in the grid*
those are not the same thing at all. You may want to ask about this..!

[XboxOne2019]

For sure its 4 numbers he is asking for:
Find the four adjacent numbers that sum to the largest sum in the array. Four adjacent numbers can be in a row, col or one of the diagonals ( 8 possible directions.) Print the four numbers and their sum.

[jonnin]

ok so the way I read that, since it says fine the #, is that 82 is not it.
50 82 18 77 for example sums to 227. It may not be the biggest, either...

you are not looking for 82, you are looking for the 4 numbers that give the biggest answer.

Im not seeing anything super clever here past brute force.
I mean, you can do a running total...
24 50 17 -17 52 7 61 …
take 24+50+17-17 and that's a value.
then do that value -24 + 52 and its the next value (reduced work, see it?)
and so on.. do that for all the rows, then again for all the columns, and then similar for all the diagonals.

[lastchance]

Another possible (brute-force) way:
- cycle through all the [i][j] of the array and check whichever of the following quadruplets are feasible (i.e. don't extend beyond the bounds of the array):

   *---
  /|\
 / | \
/  |  \

There are 4 directions, not 8, and you don't really need padding.


For that array I think the answer is
Best quadruplet: 69 50 70 74
Biggest sum: 263

[XboxOne2019]

So far I have written a function for finding the sum of values in a column, row, and diagonal. For some reason the vertical function is giving me a wrong value every 4th number and on the horizontal almost every number is right except the last value in row 4, row 7, row 9, and row 11. I don't understand what could be going wrong on it.

Theyre almost identical except for reversing row or column first.

 int sumVertical(int arr[][15], int min, int max, int colNum)  //the sum of 4 vertical numbers 
 {
     int c, r, sum=0;
     for(r=min;r<=max;r++)
     {
         for(c=colNum;c<=colNum;c++)
         {
             sum=sum+arr[r][c];
         }
     }
             return sum;
 }
 
 int sumHorizontal(int arr[][15], int min, int max, int rowNum) //sum of horizontal numbers
 {
     int c, r, sum=0;
     for(c=min;c<=max;c++)
     {
         for(r=rowNum;r<=rowNum;r++)
         {
             sum=sum+arr[r][c];
         }
     }
             return sum;
 }


   //The sum of 4 vertical numbers top to bottom
  for(colNum=0;colNum<15;colNum++)
  {
  for(i=0;i<15;i+=4)
     {
        sumValVertical=sumVertical(array2D, i, i+3, colNum);
         cout<<"Sum Vertical: "<<colNum<<" "<<sumValVertical<<endl;
     }
  cout<<endl;
  }
  
  
  //The sums of 4 horizontal numbers each row 
  for(rowNum=0;rowNum<15;rowNum++)
  {
     for(i=0;i<15;i+=4)
         {
            sumValHorizontal=sumHorizontal(array2D, i, i+3, rowNum);
            cout<<"Sum Horizontal "<<rowNum<<" "<<sumValHorizontal<<endl;
         }
     cout<<endl;
  }
  

Sum Vertical: 1 161
Sum Vertical: 1 89
Sum Vertical: 1 170
Sum Vertical: 1 -13415  //every 4th number is wrong 

Sum Vertical: 2 90
Sum Vertical: 2 55
Sum Vertical: 2 131
Sum Vertical: 2 63

Sum Vertical: 3 50
Sum Vertical: 3 163
Sum Vertical: 3 7
Sum Vertical: 3 -2145620874

on horizontal the last number on row 4 is 171, it should be 138
on row 7 the last number is 200, it should be 191 
on row 9 the last number is 121, it should be 112
on row 11 the last number is 264, it should be 200

[lastchance]

Both will be wrong in the last number - you are going beyond the end of an array. The last index in each direction is 14 (since you have 15 values starting from index 0), so the last possible starting position is 11. You, however, will be starting sums from index 12.

You also have to consider ALL quadruplets, not just those starting at 0, 4, 8 etc. Your logic is wrong.

[XboxOne2019]

it does print out all quadruplets, I just only posted a few in the output section to demonstrate the issue i'm having. I'll look into what you are saying. Does this also explain why only a few horizontal numbers are doing this as well?

[lastchance]

Please show your whole, compileable code.

  for(i=0;i<15;i+=4)
     {
        sumValVertical=sumVertical(array2D, i, i+3, colNum);

Nope - that i += 4 suggests to me that your starting values are going up in 4s.


BTW, here is what I think is the solution.

Best quadruplet: 69 50 70 74
Biggest sum: 263
  24  50  17 -17  52   7  61  41  45  47 -12  28  64  10  44
  74  78  25  10  19  74 -13 -15  36  75  65   4  -1   1  78
  30   9  54  21  52  -5  50  82  18  77 -14  -6   5  16  56
  47  24  -6  36  51  30  27  45  40  20  42   6  24  12  61
  -1  18  73  25  71 -11  23  25  47  31  29 -12  73  12  53
  33 -11 -16  76  31  12   6  67  37  39  23  49  59  14  -9
  27  22   9   6  20  21   1  65  12  24  16  -2  22  41 -13
  13  60 -11  56  69   4  28   7  55  53  12  60  56  80  -5
  69  73  44  19  38  50  38  57  14  35  33  33  24   7  49
  13 -10  74 -10  20  40  70  36  66  28  -8  -8  41   4  71
   5  29 -11  13  -4  51 -17  74  45  38  -7  42   7  20  31
  66  78  24 -15  33  74  19  57   3  79   4  31  82  51  67
  64  17  36  82   1  21 -17  71  10  50  11  76  31  66 -10
   4  -7   0  -4  -3  -8  -1  18  34 -17  32   2  39  81 -14
   7  -9  27  -8  72 -15  78  68  76  26   6  70  -3 -14  31

[XboxOne2019]

could someone show me a loop to demonstrate what they are saying?

[lastchance]

XboxOne2019 wrote:

could someone show me a loop to demonstrate what they are saying?

Here you go - but you'll have to translate it into c++. Methodology as in
http://www.cplusplus.com/forum/beginner/261698/#msg1132507
Input file as the last 15 lines in
http://www.cplusplus.com/forum/beginner/261698/#msg1133169

It scans all i, j values in turn and checks quadruplets ... rightward row of 4, downward column of 4, both downward diagonals of 4. It doesn't bother with any checks that go outside the array.

program bestquad
   implicit none
   integer, parameter :: N = 15
   integer A(N,N)
   integer bestline(4), largest, i, j, r

   open( 10, file="input.txt" )
   read( 10, * ) A
   
   bestline = A(1:4,1)
   largest = sum( bestline )
   do i = 1, N
      do j = 1, N
         if ( i + 3 <= N ) call test( A(i:i+3,j) )
         if ( j + 3 <= N ) call test( A(i,j:j+3) )
         if ( i + 3 <= N .and. j + 3 <= N ) call test( [ ( A(i+r,j+r), r = 0, 3 ) ] )
         if ( i - 3 >= 1 .and. j + 3 <= N ) call test( [ ( A(i-r,j+r), r = 0, 3 ) ] )
      end do
   end do

   write( *, "( 'Best quadruplet: ', 4( i0, 1x ) )" ) bestline
   write( *, "( 'Biggest sum: ', i0 )" ) largest

contains
   subroutine test( line )
      integer, intent(in) :: line(4)
      if ( sum( line ) > largest ) then
         largest = sum( line )
         bestline = line
      end if
   end subroutine test

end program bestquad

[XboxOne2019]

on the diagonal isn't it just the most even from top left to bottom right from col 0 row 0 to col14 row 14? and then you start at col(0) r(14) bottom left to top right c(14) r(0)? Essentially a giant X?

[lastchance]

You asked for 4 adjacent numbers - in rows, columns or diagonals. (Unless you have decided to change the problem; it is yours, after all.)

Most of the diagonals have more than 4 elements, so I don't see the need to restrict oneself to a "giant X" based on main diagonals only.

[XboxOne2019]

ok, I was just making sure. That's how I would do it. I figured out the columns and rows for now. Gotta figure out how to return the 4 adjacent numbers that equals the largest sum. I know to compare all the horizontals to the verticals, and the diagonals, but not sure how to isolate the 4 numbers at the end.

[XboxOne2019]

It's not my problem, it's what the teacher assigned to us and it's a very hard problem at the end of a somewhat easy one and it's our first intro to 2D arrays. Those were his instructions.