(There used to be a paragraph here, but on a second look, you didn’t make the mistake it was talking about.)
Since you didn’t post to Code Reviews, here’s a solution instead of a detailed code review. (If you want to make the original approach work, I’d suggest single-stepping through it in a debugger and checking where your variables first get the wrong value.) It’s got a lot of boilerplate to make it compile and run, but the part you’ll be most interested in is diag_sums() and its comments.
One idea here is to use OOP to automatically check the bounds of your array accesses. The latter is very important for catching off-by-one errors and the like. You can turn it off in production if you want, but you really don’t want to silence warnings when your program has a buffer overrun. Other optimizations here include locality of access for the data, and strength reduction on the operations: rather than check on each iteration whether we’ve hit the right edge and the bottom edge, we can simply calculate the length of each diagonal in advance.
Since the definition of diagonal number k of matrix a with M rows is equivalent to: all elements a[i][j] such that such that M - k = i - j, the algorithm ensures correctness by maintaining the invariant, which holds whenever we add 1 to both i and j, starting when either i or j is 0, and stopping whenever i = M or j = N, that is, traversing each step of the diagonal from the left or top edge to the right or bottom edge, whichever comes first.
#include <assert.h>
#include <iostream>
#include <stddef.h>
#include <stdlib.h>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
template <typename T>
class matrix {
public:
matrix( const ptrdiff_t rows,
const ptrdiff_t cols,
std::vector<T>&& elems )
: rows_(rows), cols_(cols), elems_(elems)
{
assert( rows_ > 0 );
assert( cols_ > 0 );
assert( elems_.size() == static_cast<size_t>(rows_*cols_) );
}
matrix( const ptrdiff_t rows,
const ptrdiff_t cols,
const std::vector<T>& elems )
: matrix( rows, cols, std::move(std::vector<T>(elems)) )
{}
matrix( const matrix<T>& ) = default;
matrix( matrix<T>&& ) = default;
matrix& operator= ( const matrix<T>& ) = default;
matrix& operator= ( matrix<T>&& ) = default;
T& operator() ( const ptrdiff_t m, const ptrdiff_t n )
{
assert( m >= 0 && m < rows_ );
assert( n >= 0 && n < cols_ );
return elems_[static_cast<size_t>(m*cols_ + n)];
}
const T& operator() ( const ptrdiff_t m, const ptrdiff_t n ) const
{
/* Because this call does not modify any data, and the only reason the
* member function above cannot be const is that it returns a non-const
* reference to an element of elems, casting away the const qualifier
* internally and then returning a const reference is a safe way to
* re-use the code.
*/
matrix<T>& nonconst = *const_cast<matrix<T>*>(this);
return nonconst(m,n);
}
ptrdiff_t rows() const { return rows_; }
ptrdiff_t cols() const { return cols_; }
private:
ptrdiff_t rows_;
ptrdiff_t cols_;
std::vector<T> elems_;
};
template<typename T>
std::ostream& operator<< ( std::ostream& out, const matrix<T>& x )
/* Boilerplate to print a matrix. */
{
const ptrdiff_t m = x.rows(), n = x.cols();
for ( ptrdiff_t i = 0; i < m; ++i ) {
out << x(i,0);
for ( ptrdiff_t j = 1; j < n; ++j )
out << ' ' << x(i,j);
out << '\n';
} // end for
return out;
}
using elem_t = int;
std::vector<elem_t> diag_sums( const matrix<elem_t>& a )
/* Return a vector of all the diagonal sums of a.
*
* The first diagonal sum is a(rows-1,0)
* The second is a(rows-2,0) + a(rows-1,1)
* The third is a(rows-3,0) + a(rows-2,1) + a(rows-1,2)
* And so on. I.e., the kth diagonal is the sum of all elements a(i,j) such
* that i - j == rows - k.
*
* If a is a M×N matrix, there are M diagonals starting in column zero, and
* N-1 diagonals (excluding the one containing a(0,0) so we don't count it
* twice) starting in row 0. We process them bottom to top, then left to
* right.
*
* The number of elements in a diagonal starting at a(i,0) is min{M-i, N}. The
* number of elements in a diagonal starting at a(0,j) is min{M, N-j}. This is
* because a diagonal stops at either the bottom edge or the left edge of a.
*/
{
const ptrdiff_t m = a.rows(), n = a.cols();
std::vector<elem_t> result;
result.reserve( static_cast<size_t>(m + n - 1) );
for ( ptrdiff_t i = m-1; i > 0; --i ) {
elem_t sum = 0;
const ptrdiff_t nk = (m-i) < n ? (m-i) : n;
for ( ptrdiff_t k = 0; k < nk; ++k )
sum += a(i+k, k);
result.emplace_back(sum);
} // end for i
for ( ptrdiff_t j = 0; j < n; ++j ) {
elem_t sum = 0;
const ptrdiff_t nk = m < (n-j) ? m : (n-j);
for ( ptrdiff_t k = 0; k < nk; ++k )
sum += a(k, j+k);
result.emplace_back(sum);
} // end for j
return result;
}
matrix<elem_t> read_input_matrix( const int row, const int column )
/* Reads in row*column consecutive elements from cin and packs them into a
* matrix<elem_t>.
*/
{
assert(row > 0);
assert(column > 0);
const ptrdiff_t nelements = row*column;
assert(nelements > 0); // Check for overflow.
std::vector<elem_t> result;
result.reserve(static_cast<size_t>(nelements));
for ( ptrdiff_t i = nelements; i > 0; --i ) {
int x;
cin >> x;
assert(cin.good());
result.push_back(x);
}
return matrix<elem_t>( row,
column,
std::move(result) );
}
template<typename T>
bool print_sequence( const T& container )
/* Prints the contents of a container in the format
* "{47, 94, 124, 160, 148, 36, 5}".
*/
{
cout << "{";
if ( container.begin() != container.end() )
cout << *container.begin();
for ( auto it = container.begin() + 1; it < container.end(); ++it )
cout << ", " << *it;
cout << "}\n";
return cout.good();
}
/* A simple test driver that reads in the number of rows, the number of
* columns, and then row*columns int values, from standard input. It
* then passes the result to diag_matrix(), E.g.:
*
* 5 3
* 52 35 5
* 2 71 1
* 3 60 25
* 79 55 98
* 47 15 66
*/
int main()
{
int rows, columns;
cin >> rows;
cin >> columns;
assert(cin.good());
const matrix<elem_t> input_matrix = read_input_matrix( rows, columns );
// cout << input_matrix; // Instrumentation.
const std::vector<elem_t> sums = diag_sums(input_matrix);
print_sequence(sums);
return EXIT_SUCCESS;
}
You could also just do print_sequence(diag_sums(read_input_matrix( rows, columns ))).
