2
\$\begingroup\$

I have solved a seemingly easy problem:

Given a square matrix, calculate the absolute difference between the sums of its diagonals.

For example, the square matrix is shown below: $$\begin{bmatrix} 1\, 1\, 1 \\ 2 \, 3\, 3 \\ 0\,1\,0\end{bmatrix}$$

The left-to-right diagonal = \$0+3+1=4\$. The right to left diagonal \$1+3+0=4\$. Their absolute difference is \$0\$.

However, I am a beginner in C and had some troubles. It took me way too long :D. Also, I tried to abstract the problem on a higher level - which does not mean it is high. However, I am not sure how far I should abstract the problem in such challenges.

  1. How well/bad is this code written?

  2. Is the code abstract enough?

  3. How can you solve such challenges more quickly?

int addDiagonal(int from_X,int to_X,int from_Y, int to_Y, int** arr){
    int sum = 0;
    int dirX = to_X - from_X;

    if(dirX < 0) dirX = -1;
    else if(dirX > 0) dirX = 1;

    int dirY= to_Y - from_Y;
    if(dirY < 0) dirY = -1;
    else if(dirY > 0) dirY = 1;

    while(from_X != to_X){
        sum+=arr[from_X][from_Y];
        from_X += dirX;
        from_Y += dirY;
    }
    sum+=arr[from_X][from_Y];
    return sum;
}

int diagonalDifference(int arr_rows, int arr_columns, int** arr) {
    int left_to_right = addDiagonal(0,arr_columns-1,0,arr_rows-1,arr);
    int right_to_left = addDiagonal(0, arr_columns-1,arr_rows-1,0,arr);
    if(left_to_right - right_to_left > 0) return left_to_right - right_to_left;
    return right_to_left - left_to_right;
}
\$\endgroup\$
2
\$\begingroup\$

How well/bad is this code written?

A good first timer implementation.

Is the code abstract enough?

Mostly. It does make unnecessary assumptions about range. It assumes int math does not overflow.

To make more abstract, code could use typedef int TVS_int; to ease future type changes.

How can you solve such challenges more quickly?

Take advantage that the matrix is square.

With computing along the diagonal of a square matrix, only the matrix and its one size parameter are needed.

Use const to hint the the compiler about certain potential optimizations and convey code's intent better.

size_t is the best size of array indexing, not too wide nor too narrow.

I like the idea of using a wider intermediate type to mitigate overflow problems.

typedef int TVS_int;
typedef long long TVS_int2;  // a type with wider range.

TVS_int diagonalDifference_alt(const TVS_int** arr, size_t n) {
  TVS_int2 sum_up = 0;
  TVS_int2 sum_dn = 0;

  for (size_t i = 0; i<n; i++) {
    // Notice both `arr` use the same `arr[i]` --> potentially easier to optimize
    sum_up += arr[i][n-i-1];
    sum_dn += arr[i][i];
  }
  TVS_int2 diff = sum_up - sum_dn;
  return (TVS_int) ((diff < 0) ? -diff : diff);  // OF possible here in range reduction 
}

if(left_to_right - right_to_left > 0) unnecessarily incurs the potential for int overflow. Simply compare instead. if (left_to_right > right_to_left)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.