Traverse Matrix in Reverse Diagonal strips

Question

I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

1 2 3
4 5 6
7 8 9

Would have to be traversed in the following order:

[3],[2,6],[1,5,9],[4,8],[7]

Answer 1

I hope that the following example will inspire you: $$ (2,0) \\ (1,0),(2,1) \\ (0,0),(1,1),(2,2) \\ (0,1),(1,2) \\ (0,2) $$ This is the same as the order you were describing. Notice that line $i$ (counting from zero) consists of $(x,y)$ such that $y-x = i-2$, arranged in order of increasing $y$ (or decreasing $x$). Furthermore, $y$ runs from $\max(i-2,0)$ to $\min(i,2)$.

In the general $n\times n$ case, just replace all occurrences of $2$ with $n-1$, and let $i$ run from $0$ to $2n-1$.

Answer 2

Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\,1,\,0,\,-1,\,-2$. This gives something like

for c := 2 to -2 step -1
    for x := 0 to 2
        y := x-c
        if 0<=y<=2
            print A[x,y]

Answer 3

Here's the Python version:

def reverse_diagonal_traversal(matrix):
    side = len(matrix) + 1
    iterations = side - 1
    for i in range(1, side):
        for j in range(i):
            yield matrix[j][iterations + j - i]
    for i in range(side - 2, 0, -1):
        for j in range(i):
            yield matrix[iterations + j - i][j]


def test(side):
    matrix = [range(i * side, side + i * side) for i in range(side)]
    print matrix
    for i in reverse_diagonal_traversal(matrix):
        print i

Writing this in C would require too much code dealing with memory (de)allocation / printing, which isn't really part of this problem. I'd imagine that porting the above to C won't be a problem.

The idea behind the code is that you need to produce iterations of 1..N length until you reach the main diagonal, and then N-1..1. In the first half, you'd have to select the row at N at the first step of the iteration, and then N-i for each value of i in the iteration. You'd select the column starting at nth iteration - length of iteration, and then for each iteration step you'd increment that by one.

Finally, I'm not sure this is the most "elegant" solution (maybe you can do it in just half the code), but I couldn't find a good way to do that.