Traverse a 2D array converted to 1D, diagonal

Question

I want to traverse a 2D square array that I have converted to 1D.

The problem is that I want to traverse it as if I was traversing the original 2D in diagonal strips.

The array is diagonal and I originally created it with malloc in 1D to avoid allocating too much memory.

The size of the array:

int Tsize = N*(N+1)/2; //table size -> diagonal array of (N+1)*N/2 elements

int* table = malloc(Tsize*sizeof(int)); 

I know that this way you traverse a flattened 2D array.

do{
    i = row*N + col;
    col++;
    if (col>N-1){
        col = 0;
        row++;
    }
    printf("%d ", x[i]);
} while( row < N);

And here is what I found for traversing an array in diagonal strips.

For this array:

int x[3][3] = {1, 2, 3,
               ø, 4, 5,
               ø, ø, 6};

ø: i will not use that element.

I create this array:

int k[6] = {1,2,3,4,5,6};

and I want to traverse it like that:

1,4,6,2,5,3

Can you suggest anything? I'm stuck.

Answer 1

What you are describing when you say you allocated a two-dimensional array as a one-dimensional array is known as array-flattening. Flattening arrays is actually a common security practice because the structure of an array gives you a lot of information on its own, so the code is obfuscated to mitigate this. Even the program's control flow itself will be obfuscated for additional security.

To diagonally traverse a hypothetical 3x3 matrix flattened into a one dimensional array of size 9, you can start at arr[0] and just add 4 to the offset. This method is essentially isomorphic to iterating through the matrix diagonal from the top left to the bottom right, while providing some additional secrecy because it's not as trivial to deduce the structure of the data.

You can visualize this transformation like so:

  a [0] [1] [2]
    [3] [4] [5]
    [6] [7] [8]

  b [0] [1] [2] [3] [4] [5] [6] [7] [8]

So when you iterate through the first array, you're nesting two for loops, telegraphing the fact that this is a two-dimensional array. On the other hand, when iterating through the second array by incrementing the index by 4 starting at 0, you'll be accessing the same elements you would have in the first array, but you're doing it without giving away the underlying structure of the data.

This contrived example is too trivial for practical use, but I encourage you to look into this. Let me know if you have any questions.