C++ 2D Array access question

funkey_monkey

I've got a 2D array - 6 x 6

I want to sum 3 adjacent cells in the array for a repeating pattern throughout the array (hourglass).
Is there a quick way to sum 3 adjacent cells in C++? - i.e. sum elements arr[j], arr[j+1] and arr[j+2].

I had noticed the accumulate function, but that does not appear to work with just adjacent elements.

I've got an alternative plan in mind, but was wondering if there is something in the vast C++ library which would allow me to input the start and end and sum between on a row basis.


Thanks.

funkey_monkey

The problem:
See attachment.

Can the issue in my first email be answered. Also critiques of my solutions welcomed.


The initial skeleton that was provided was:

#include <bits/stdc++.h>

using namespace std;



int main()
{
    vector<vector<int>> arr(6);
    for (int i = 0; i < 6; i++) {
        arr[i].resize(6);

        for (int j = 0; j < 6; j++) {
            cin >> arr[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    return 0;
}

Attempt 1:

#include <bits/stdc++.h>
#include <numeric>
#include <algorithm>    // std::max

using namespace std;



int main()
{
    vector<vector<int>> arr(6);
    for (int i = 0; i < 6; i++) {
        arr[i].resize(6);

        for (int j = 0; j < 6; j++) {
            cin >> arr[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    
    int numHourglasses = arr.size()-2; // Num of hourglasses per row/col
    int maxHourglassSum = 0;           // Max calculated hourglass value


    // Working across the table
    for(int j = 0; j < numHourglasses; j++)
    {
        // Working down the table
        for(int i = 0; i < numHourglasses; i++)
        {  
            // Known starting point (i, j) so can start summing directly
            int sum = arr[i][j]     + arr[i][j+1]   + arr[i][j+2]
                                    + arr[i+1][j+1] +
                      arr[i+2][j]   + arr[i+2][j+1] + arr[i+2][j+2];

            // Compare with previous value and maintain the highest
            maxHourglassSum = std::max(maxHourglassSum, sum);
        }

    }
    cout << maxHourglassSum;

    return 0;
}

Second attempt:

#include <bits/stdc++.h>
#include <numeric>
#include <algorithm>    // std::max

using namespace std;



int main()
{
    vector<vector<int>> arr(6);
    for (int i = 0; i < 6; i++) {
        arr[i].resize(6);

        for (int j = 0; j < 6; j++) {
            cin >> arr[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    
    int numHourglasses = arr.size()-2; // Num of hourglasses per row/col
    int maxHourglassSum = 0;           // Max calculated hourglass value

    // Origin is known (i,j), so define offsets for all other required
    // points as a table and iterate around
    struct
    {
        int i;
        int j;
    }
    points[] = {{0,0},{0,1},{0,2},{1,1},{2,0},{2,1},{2,2}};

    // Working across the table
    for(int j = 0; j < numHourglasses; j++) {

        // Working down the table
        for(int i = 0; i < numHourglasses; i++) { 
        
            int sum = 0;  // Used to hold sum of hourglass currently
                          // being analysed

            // Starting point is known (i, j) so use points to sum all
            // other elements required for the hourglass
            for (int k = 0; k < 7; k++) {
                sum += arr[i + points[k].i][j + points[k].j];
            }

            // Compare with previous value and maintain the highest
            maxHourglassSum = std::max(maxHourglassSum, sum);
        }
    }
    cout << maxHourglassSum;

    return 0;
}

Anjobe

I don't think there is any need to go looking for a solution using standard algorithms, this is quite easily solved using nested loops.

int hourglassSum(vector<vector<int>> arr) {
    int largest = INT_MIN;

    for (int i = 1; i < 5; i++)
    {
        for (int j = 1; j < 5; j++)
        {
            int sum = 0;

            for (int k = i - 1; k <= i + 1; k++)
            {
                for (int l = j - 1; l <= j + 1; l++)
                {
                    if (k!=i || l == j)
                    {
                        sum += arr[k][l];
                    }
                }
            }

            largest = std::max(largest, sum);
        }
    }

    return largest;
}

funkey_monkey

Thanks - your solution had one small subtlety which made it more robust than mine and that was the initialising of the max value to int_min.
I didn't realise this const existed.

It certainly appears a lot more succinct than my attempt

Does that solution not have an increased timing complexity for the additional 2 loop structures?
I was always told to avoid unnecessary looping and unroll them if possible for performance benefits.

Colonel Panic

Let compilers unroll your loops for you!

Are nested loops bad? Sometimes. Depends on a lot of things. How big your data is, what way it's organised in memory, what work you're doing in the inner loop etc.

funkey_monkey

Okay next question.
What is the easiest way to do the equivalent of a lookup in C++? Within 0 - 100 in non equal steps I want to return a char dependent on the in value.
I can think of the obvious ways such as a CASE but was wondering if there was something more succinct? So, I've got an int value x. I want to return a Char whose value depends on where x lies in 0 - 100. Is there a simpler way than a CASE?

Colonel Panic

If a mapping for each thing between 0 and 100, an array,

If not, maybe a std::map.

It's each enough declare and initialise an array in one go.

int stuff[] = { 'a', 'b', 'c', };
char thing = stuff[1];

funkey_monkey

I'd want to do something the equivalent of:
arr[0..39] {'A'};
arr[40..54] {'B'};
arr[55..69] {'C'};
arr[70..100] {'D'};

Does C++ have a shortcut way of equivalence with this?

Colonel Panic

I believe GCC has an extension that lets you say

case 0 ... 39:

But in general, use blocks of if/else statements here and don't overthink it!

funkey_monkey

return ( avg < 40 ? 'T' : 
                     avg < 55 ? 'D' : 
                     avg < 70 ? 'P' : 
                     avg < 80 ? 'A' :
                     avg < 90 ? 'E' : 'O' );

Still trying to get head around the syntax. But I'll keep practising and see where I end up!

Colonel Panic

Ugh, don't do that!!

funkey_monkey

Colonel Panic wrote: »

Ugh, don't do that!!

Why is it less efficient than:

int sum = 0;
            int len = this->testScores.size();
            sum = accumulate(this->testScores.begin(),
                             this->testScores.end(), sum);
            int avg = sum/len;

            if (avg < 40){
                return 'T';
            }
            else if (avg < 55){
                return 'D';
            }
            else if (avg < 70){
                return 'P';
            }
            else if (avg < 80){
                return 'A';
            }
            else if (avg < 90){
                return 'E';
            }
            else{
                return 'O';
            }

Anima

Not about efficiency, they'll produce the same assembly. Probably commenting on the style.

I don't have a terrible opinion of it tbh, you'd see it in web dev more so but it's not as easy to change as the more long form version.

if (avg < 40) return 'T';
if (avg < 55) return 'D';
if (avg < 70) return 'P';
if (avg < 80) return 'A';
if (avg < 90) return 'E';

return 'O';

funkey_monkey

Anima wrote: »

Not about efficiency, they'll produce the same assembly. Probably commenting on the style.

I don't have a terrible opinion of it tbh, you'd see it in web dev more so but it's not as easy to change as the more long form version.

if (avg < 40) return 'T';
if (avg < 55) return 'D';
if (avg < 70) return 'P';
if (avg < 80) return 'A';
if (avg < 90) return 'E';

return 'O';

Yes, okay - that is neat and easily readable too. I presume you actually meant:

if (avg < 40) return 'T';
else if (avg < 55) return 'D';
else if (avg < 70) return 'P';
else if (avg < 80) return 'A';
else if (avg < 90) return 'E';

return 'O';

Otherwise all ifs would require evaluation.

Anima

They can't evaluate if it's already returned.

funkey_monkey

Yes, you're right. Really need to brush up:rolleyes:

Colonel Panic

The ternary operator is best used for small, inline chunks of code for readability.

It's also useful for conditionally assigning a value to a const variable, something you couldn't do with blocks of if statements.

I just hate to see "cute" code where people try to distill logic into a one-liner, albeit one with line breaks in an attempt to give it readability.

14ned

If it's coursework you're doing, submit the answers already suggested.

If you care about the dark arts of C++:

• Avoid vectors of vectors to represent 2D arrays, they produce surprise, and they are highly inefficient for that use case.
• https://en.cppreference.com/w/cpp/numeric/valarray is the C++ 98 era way of "getting the compiler to do arrays properly". On GCC only it can produce quite good codegen.
• https://en.cppreference.com/w/cpp/container/array Fixed sized arrays of fixed sized arrays is the best you can do in standard C++ 20.
• C++ 23 will come with mdspan<T> which will finally provide standard support for multi-dimensional things. Combined with the concurrent algorithms library it can produce good quality codegen. We may also see a standard linear algebra library in 23, which is obviously vastly better again.
• There are loads of third party libraries which do matrix math very well i.e. apply SIMD or GPU offload optimisations, where appropriate. Some are in Boost, others not. Probably best start with the three or four in Boost first.

funkey_monkey

Thanks for the replies.
I mostly know the design of what I want to do (or that will at least provide a working solution albeit ugly/inefficient). Getting my head around the C++ structure in which to do it is the issue!

Trying to put some more effort into it now and realising it is a lot lot more complex that I first envisaged. The libraries are vast and figuring out if I need to do something or if the libraries have something already there takes a bit of time. Stumbled upon the accumulate function:

        /*	
        *   Function Name: calculate
        *   Return: A character denoting the grade.
        */
        char calculate(){
            int sum = 0;
            int len = this->testScores.size();
            sum = accumulate(this->testScores.begin(),
                             this->testScores.end(), sum);
            int avg = sum/len;