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.

if you want to traverse the matrix as a 2D array, why did you convert it to a 1D in the first place? — Pablo, Apr 10 '18 at 17:43
I created the array in 1D using malloc but I want to treat it as if it was a diagonal array. I did it because this way I allocate less memory — guruste, Apr 10 '18 at 17:48
What do you mean by "traversing in diagonal strips"? Can you show the traversal pattern? "diagonal" usually means main diagonal... — Mad Physicist, Apr 10 '18 at 18:03
"I created the array in 1D using malloc" --> post that code. — chux - Reinstate Monica, Apr 10 '18 at 18:07

Jose Fernando Lopez Fernandez · Accepted Answer · 2018-04-10T19:12:55.570

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.

edited Apr 10 '18 at 19:12

answered Apr 10 '18 at 18:00

Jose Fernando Lopez Fernandez

1,139
9
18

1

Never heard about this being a security measure: could you provide a reliable source? You add 4 to the offset, not 3. – Mad Physicist Apr 10 '18 at 18:02
Sure, I'll edit it in, give me a sec. Not sure why you'd add 4 to the offset though, then you would access `arr[0]`, `arr[4]`, and `arr[8]`. Did you mean something else? If you add three, you get elements 0, 3, and 6, which correspond to the first row, first column, second row second column, and third row third column – Jose Fernando Lopez Fernandez Apr 10 '18 at 18:15
OP is asking for the diagonal – Mad Physicist Apr 10 '18 at 19:08
Right, I gave him the diagonal given by elements [0][0], [1][1], [2][2] – Jose Fernando Lopez Fernandez Apr 10 '18 at 19:09
Ah, duh, I just got what you're saying – Jose Fernando Lopez Fernandez Apr 10 '18 at 19:09
This is why I voted to close the question instead of answering myself. It's really not clear what OP wants. – Mad Physicist Apr 10 '18 at 19:10
I can't believe it took me an hour to realize I was giving the first column. I need to go to bed. Sorry about that, thanks for the heads up – Jose Fernando Lopez Fernandez Apr 10 '18 at 19:13

purec · Answer 2 · 2018-04-10T18:30:27.357

0

Something like this?

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

int
main() {
 int i, n = 5;
 int *arr = malloc(n*n*sizeof(int));
 for (i = 0; i < n*n; i++)
    arr[i] = i + 1;
 for (i = 0; i < n*n; i += n+1) 
    printf("%d ", arr[i]);
}

edited Apr 10 '18 at 18:30

answered Apr 10 '18 at 18:23

purec

308
2
6

Where is the diagonal involved in this? – Mad Physicist Apr 10 '18 at 19:08
In printf("%d ", arr[i]); – purec Apr 10 '18 at 19:12
I can't read today apparently. My mistake. I read the increment as `i += n`. – Mad Physicist Apr 10 '18 at 19:13

Traverse a 2D array converted to 1D, diagonal

2 Answers2