Striping a matrix concentrically, anticlockwise

Question

Given a matrix you shall stripe the matrix, such that every number that has equal distance to the matrix border will be filled into an array.

For examples see code comments.

typedef int matrixOptimizationValue;
/*
Striping a matrix by packing numbers who have the same distance from matrix border.
Note that the packing is anti-clockwise.
 E.g:

 Example 1:
 ___      ___
 . 1 1 1 1  .         Field:
 . 2 2 2 2  .          [1,2,3,3,3,3,2,1,1,1]
 . 3 3 3 3  .  -->     [2,2]
 ___      ___

 Example 2:
 ___      ___         Field:
 . 1 1 1 4 1  .        [1,2,3,1,2,4,5,6,3,2,1,4,1,1,1]
 . 2 2 2 3 2  .        [2,3,3,3,2,3,2,3,2,2]
 . 3 3 3 2 3  .  -->
 . 1 2 4 5 6  .
 ___      ___


 returns:
 return_value      - Field of Arrays; unpacked Matrix
 arr_lengths       - Since fields arrays have a variable size, "*array_lengths" contains the following information.
                     {Amount of arrays in the field, sizes_of_array01, sizes_of_array03 ... }
                     Therefore "*array_lengths" size must be *array_lengths[0]+1.

 in:
 const int* matrix - Matrix to be unpacked
 int rows          - rows of the matrix
 int columns       - columns of the matrix

 Possible Errors:
    1. Matrix has no measurments.

 */
matrixOptimizationValue** strip(const matrixOptimizationValue* matrix, const int rows, const int columns, int** arr_lengths){
    //Checking if Matrix has measurments.
    int* lengths = *arr_lengths;
    if(rows == 0 || columns == 0){
        printf("\nMatrix has no measurments. Error. \n");
        exit(0);
    }

    //Calculating maximal distance of an element to borders.
    const int max_dis = (columns > rows) ? round((double)(rows)/2) : round((double)(columns)/2);
    //Creating future return_value
    matrixOptimizationValue** unstriped_matrix = malloc(max_dis*sizeof(int*));
    (lengths) = malloc((max_dis+1) * sizeof(matrixOptimizationValue));
    (lengths)[0] = max_dis;
    //Packing...
    int x_minborder = 0; //Borders
    int y_minborder = 0;
    int x_maxborder = columns;
    int y_maxborder = rows;

    for(int i = 0; i < max_dis; i++){
        int elements_size=0; //Unfortunately, making "const" causes really bad syntax...
        if(x_maxborder-x_minborder <= 1 || y_maxborder-y_minborder <=1){
            if(x_maxborder-x_minborder <= 1 && y_maxborder-y_minborder <=1){
                elements_size = 1;
            } else {
                elements_size = (x_maxborder-x_minborder == 1) ?  y_maxborder-y_minborder : x_maxborder-x_minborder;
            }
        } else {
            elements_size = 2*(x_maxborder-x_minborder + y_maxborder-y_minborder)-4;
        }
        matrixOptimizationValue* array = malloc(elements_size * sizeof(int));
        (lengths)[i+1]=elements_size;
        //Initializing coordinates
        int x = i; //It is certain, that this coordinates will always belong to fields array_i;
        int y = i;

        int dir_x = 0; //Direction
        int dir_y = 1;

        for(int j = 0; j < elements_size; j++){
            array[j] = matrix[y*columns + x];
            if(x+dir_x >= x_maxborder || x+dir_x < x_minborder || y+dir_y >= y_maxborder || y+dir_y < y_minborder){
                /*Rotate Direction-vector using Algebra
                         x
                         y
                 0  1    y
                -1  0   -x
                 */
                const int clone = dir_x;
                dir_x = dir_y;
                dir_y = -clone;
            }
            x += dir_x;
            y += dir_y;
        }
        x_minborder++;
        y_minborder++;
        x_maxborder--;
        y_maxborder--;
        unstriped_matrix[i]=array;
    }
    return unstriped_matrix;
}

1. How would you improve the syntax?
2. Assume high-performance needs, how would you improve the code?

Answer 1

Here are some things that may help you improve your code.

Fix the bug

The code allocates memory for the passed arr_lengths but never returns a pointer to the newly allocated memory to the caller. The code currently has this:

int* lengths = *arr_lengths;
// more code
(lengths) = malloc((max_dis+1) * sizeof(matrixOptimizationValue));

Instead it should be this:

// more code
*arr_lengths = malloc((max_dis+1) * sizeof(matrixOptimizationValue));
int* lengths = *arr_lengths;

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. The code comments are good, but a sample program would be better.

Use the required #includes

The code uses printf which means that it should #include <stdio.h>. It was not difficult to infer, but it helps reviewers if the code is complete. I had to add these three lines:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

Avoid the use of floating point math

On many computers, floating point mathematics is slower than integer math. For this reason, it's often better to avoid if you can. In this case, it's easily done. We can replace this:

const int max_dis = (columns > rows) ? round((double)(rows)/2) : round((double)(columns)/2);

with this:

const int max_dis = (rows < cols ? rows+1 : cols+1) / 2;

I also changed the variable columns to cols but that's a personal preference. The longer name is arguably more descriptive.

Check return values for errors

The calls to malloc can fail. You must check the return values to make sure they haven't or your program may crash (or worse) when given malformed input or due to low system resources. Rigorous error handling is the difference between mostly working versus bug-free software. You should strive for the latter.

Choose descriptive names

Most of the variables and function are well-named and clear in their usage and intent, but I found matrixOptimizationValue both somewhat misleading (it's not a value, but rather a type) and also overly long. I renamed it DataType which is also not a brilliant name, but is, at least, shorter.

Minimize system calls

If you're looking for performance, it's often a good idea to avoid system calls, such as for malloc. In this case, I'd suggest changing the code to do only one single allocation. This has the benefits of speed, simplification of error checking and handling, and simplification of cleanup after the call (only one call to free is required).

Consider separating I/O from the algorithm

The strip function uses printf to print to the console and then exits via exit if the input is malformed. Consider changing that to return NULL on error and letting the caller figure out what to do.

Simplify the algorithm

I found the length of the code and many variables something of an impediment to my understanding of the algorithm. It can be simplified considerably by remembering that the passed variables may also be used directly. In the rewrite I created, pointers are used extensively to simplify the code. It also uses the fact that we can calculate in advance when to change direction.

Results

Following all of these suggestions, I created the following rewrite:

#include <stdlib.h>
#include <stdio.h>
#include <stddef.h>

typedef unsigned short DataType;
#define DataTypeStr "u"

DataType* strip(const DataType* matrix, int rows, int cols, int** arr_lengths){
    if (rows == 0 || cols == 0) {
        return NULL;
    }
    const int max_dis = (rows < cols ? rows+1 : cols+1) / 2;
    // return value is a single vector of the same size as 
    // the input, followed by an int value n, which is the 
    // count of arrays represented, followed by n ints which
    // represent the lengths of those sub-arrays.
    DataType *retval = malloc(rows * cols * sizeof(DataType*) 
            + (1 + max_dis) * sizeof(int));
    if (retval == NULL) {  // bail out on allocation error
        return NULL;
    }
    *arr_lengths = (int *)(&retval[rows*cols]);
    DataType *out = retval;
    int *len = *arr_lengths;
    *len++ = max_dis;
    // precalculate down, right, up, left 
    enum compass { DOWN, RIGHT, UP, LEFT, DIRCOUNT };
    const int dirs[DIRCOUNT] = { cols, +1, -cols, -1 };
    // because we move and then fetch a value, 
    // move one row above matrix
    matrix += dirs[UP];

    for (int matnum=0; matnum < max_dis; ++matnum) {
        if (rows > 1 && cols > 1) {
            *len++ = 2 * (rows + cols - 2);
        } else {
            *len++ = rows + cols - 1;   
        }
        // start by moving down
        int dir = DOWN;
        while (rows && cols && dir < DIRCOUNT) {
            // down and up
            for (int i = rows; i; --i) {
                matrix += dirs[dir];
                *out++ = *matrix;
            }
            --rows;
            --cols;
            ++dir;
            // right and left
            for (int i = cols; i; --i) {
                matrix += dirs[dir];
                *out++ = *matrix;
            }
            ++dir;
        }
    }
    return retval;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        puts("Usage: matstripe rows cols\n");
    }
    int rows = atoi(argv[1]);
    int columns = atoi(argv[2]);
    printf("Input is a %d x %d matrix\n", rows, columns);
    DataType *input = malloc(rows * columns * sizeof(DataType));
    if (input == NULL) {
        puts("Out of memory error, quitting program.");
        return 1;
    }
    int colcounter = columns;
    for (int i = 0; i < rows*columns; ++i) {
        input[i] = i+1;
        printf("%3" DataTypeStr " ", input[i]);
        if (--colcounter == 0) {
            printf("\n");
            colcounter = columns;
        }
    }
    int *arr_lengths;
    DataType* answer = strip(input, rows, columns, &arr_lengths);
    free(input);
    puts("Output:");
    if (answer) {
        DataType* mat = answer;
        for (int matnum = 0; matnum < *arr_lengths; ++matnum) {
            printf("[%" DataTypeStr, *mat++);
            for (int i = arr_lengths[matnum+1] - 1; i; --i) {
                printf(",%" DataTypeStr, *mat++);
            }
            puts("]");
        }
        free(answer);
    }
}

This takes two command line parameters for the nmber of rows and number of columns and constructs a test input matrix of that size filled with cardinal numbers. Here's an example of output.

Input is a 5 x 4 matrix
  1   2   3   4 
  5   6   7   8 
  9  10  11  12 
 13  14  15  16 
 17  18  19  20 
Output:
[1,5,9,13,17,18,19,20,16,12,8,4,3,2]
[6,10,14,15,11,7]