Friday, 29 April 2011

Traverse an array diagonally

Question

How would you traverse an array diagonally and display its contents ?

Say you have something like this,

1  2  3
4  5  6
7  8  9
In the above array, if you traverse from top left corner, then the list of number will be,
, [2,4], [3,5,7], [6,8], 
How would you get the above set?
Solution
Reference: http://stackoverflow.com/questions/1779199/traverse-matrix-in-diagonal-strips
0     1     2
0   1     2     3
1    4    5     6
2    7    8     9
The list of indices for the required traversals are,
{[0,0]}  {[0,1][1,0]}  {[0,2][1,1][2,0]}  {[1,2][2,1]} {[2,2]}
If you can get the pattern, then you can do this easily. Total 5 slices will come which is array size N * 2-1. i.e, for 3x3 = 6-1 = 5.
you should have a incrementing counter at row/column when moving to the middle slice. After that you need a decrementing counter at row/column.
Code
void main()
{
int x = {1, 2, 3,
4, 5, 6,
7, 8, 9};
int N=3;
for (int slice = 0; slice < N*2-1; ++slice) {
int z = slice < N ? 0 : slice - N + 1;
for (int j = z; j <= slice - z; ++j) {
int c1=j;
int c2=(N-1)-(slice-j);
printf("%d ", x[c1][c2]);
}
printf("\n");
}

printf("\n");
for (int slice = 0; slice < N*2-1; ++slice) {
int z = slice < N ? 0 : slice - N + 1;
for (int j = z; j <= slice - z; ++j) {
int c1=j;
int c2=slice-j;
printf("%d ", x[c1][c2]);
}
printf("\n");
}
}
• here slice maintains the incrementing/decrementing index required. slice-N+1 will take care of that value
• slice-j allows as move in both row and column.
• When you need to move from top right, just subtract N-1 from slice-j so that you also travel from top right.
Output
Top right to bottom left

3
2 6
1 5 9
4 8
7

Top left to bottom right

1
2 4
3 5 7
6 8
9