max diag

t13e11.maxDiag.cpp

// t13e11.maxDiag.cpp
// juanfc 2023-11-23
// Find the greatest sum for the elements of all the pos- sible diagonals of a
// TMat. Take into account that diagonals can go ↘ or ↗. Some diagonals are
// shorter than others.
// 


#include <iostream>
#include <iomanip>
#include <array>
using namespace std;

const bool DEBUG = false;

const int NROWS = 3;
const int NCOLS = 5;
typedef array<int,NCOLS> TRow;
typedef array<TRow,NROWS> TMat;


int main()
{
    void test(TMat);
    test((TMat) {{{{1, 2, 3, 4, 5}},
                  {{4, 5, 6, 7, 8}},
                  {{7, 8, 9, 10, 11}}}});

    test((TMat) {{{{10, 2, 3, 4, 5}},
                  {{4, 5, 6, 7, 8}},
                  {{7, 8, 9, 10, 11}}}});

    test((TMat) {{{{1, 2, 3, 4, 5}},
                  {{40, 5, 6, 7, 8}},
                  {{7, 8, 9, 10, 11}}}});

    test((TMat) {{{{1, 2, 3, 4, 5}},
                  {{4, 5, 6, 7, 80}},
                  {{7, 8, 9, 10, 11}}}});

    test((TMat) {{{{1, 2, 3, 4, 50}},
                  {{4, 5, 6, 7, 8}},
                  {{7, 8, 9, 10, 11}}}});
    return 0;
}



void test(TMat a)
{
    int maxDiag(TMat);
    void print(TMat);
    print(a); cout << endl;
    cout << "\tMax diag: " << maxDiag(a) << endl << endl;
}

int maxDiag(TMat a)
{
    void partMsg(string);
    void cellMsg(int, int);
    int max = a[0][0];
    partMsg("from first col, rows down");
    for (int row = 0; row < NROWS; ++row) {
        int col = 0;
        int rc = row;
        int s = 0;
        while (rc < NROWS and col < NCOLS) {
            cellMsg(rc, col);
            s += a[rc++][col++];
        }
        if (s > max) max = s;
        partMsg("");
    }
    partMsg("from first row cols right");
    for (int col = 1; col < NCOLS; ++col) {
        int row = 0;
        int rc = col;
        int s = 0;
        while (row < NROWS and rc < NCOLS) {
            cellMsg(row, rc);
            s += a[row++][rc++];
        }
        if (s > max) max = s;
        partMsg("");
    }

    partMsg("from first col, rows up");
    for (int row = NROWS-1; row >= 0; --row) {
        int col = 0;
        int rc = row;
        int s = 0;
        while (rc >= 0 and col < NCOLS) {
            cellMsg(rc, col);
            s += a[rc--][col++];
        }
        if (s > max) max = s;
        partMsg("");
    }
    partMsg("from last row cols right");
    for (int col = 1; col < NCOLS; ++col) {
        int row = NROWS-1;
        int rc = col;
        int s = 0;
        while (row >= 0 and rc < NCOLS) {
            cellMsg(row, rc);
            s += a[row--][rc++];
        }
        if (s > max) max = s;
        partMsg("");
    }
    return max;
}

bool gt(TMat m, int v, int i, int j)
{
    return (i>=0 and i<NROWS and j>=0 and j<NCOLS)?
        v > m[i][j]: true;
}


void print(TMat m)
{
    for (int row = 0; row < NROWS; ++row) {
        for (int col = 0; col < NCOLS; ++col) {
            cout << setw(3) << m[row][col] << " ";
        }
        cout << endl;
    }
}

void partMsg(string msg)
{
    if (DEBUG) {
        if (msg.length()>0)
            cout << endl << msg << endl;
        else
            cout << endl;
    }
}
void cellMsg(int r, int c)
{
    if (DEBUG)
        cout << r << "," << c << "; ";
}