Print 2d array on diagonals

Question

I'm trying to print the diagonals for a 2d array starting with the bottom left corner and moving towards the top right corner. I've managed to print the first half of the matrix but I got stuck when I have to print the second part of it and I'm hoping somebody can give me a clue how to continue. Here is what I have:

matrix = [["A", "B", "C", "D"], 
          ["E", "F", "G", "H"], 
          ["I", "J", "K", "L"],
          ["M", "N", "O", "P"],
          ["Q", "R", "S", "T"]]

and the partial function that print the diagonals up to a point:

def diagonal_matrix_print(input_matrix):
    width = len(input_matrix[0])
    height = len(input_matrix)
    start_row = height - 1
    first_row = 0 
    for start_row in reversed(range(0, height)):
        i = start_row
        for column in range(0, width):
            if i == height:
                start_row = start_row - 1
                break
            print input_matrix[i][column]
            i = i + 1
        print

The issue I'm facing is printing the diagonals that start with the second half of the matrix - B G L, C H, D

I tried using another 2 for loops for it like:

for row in range (0, height -1):
    i = row
    for start_column in range(1, width):
        print input_matrix[i][start_column]
        i = i + 1

but when the row value changes to 1, is not printing the diagonal anymore...

Answer 1

Suppose we have the list of lists L:

>>> L = [[ 0,  1,  2],
         [ 3,  4,  5],
         [ 6,  7,  8],
         [ 9, 10, 11]])

We want a function diagonals such that

>>> diagonals(L)
[[9], [6, 10], [3, 7, 11], [0, 4, 8], [1, 5], [2]]

We can think about items in L with respect to 2 different coordinate systems. There is the usual (x, y) coordinate system where (x, y) corresponds to the location with value L[x][y].

And then there is also the (p, q) coordinate system where p represents the pth diagonal, with p=0 being the diag at the lower-left corner. And q represents the qth item along the pth diag, with q=0 starting at the left edge. Thus (p, q) = (0,0) corresponds to the location with value L[3][0] = 9 in the example above.

Let h,w equal the height and width of L respectively. Then p ranges from 0 to h + w - 1.

We want a formula for translating from (p, q) coordinates to (x, y) coordinates.

• x decreases linearly as p increases.
• x increases linearly as q increases.
• When (p, q) = (0, 0), x equals h.

Therefore: x = h - p + q.

• y does not change with p (if q is fixed).
• y increases linearly as q increases.
• When (p, q) = (0, 0), y equals q.

Therefore, y = q.

Now the extent of valid values for x and y requires that:

(0 <= x = h - p + q < h) and (0 <= y = q < w)

which is equivalent to

(p - h + 1 <= q < p + 1) and (0 <= q < w)

which is equivalent to

max(p - h + 1, 0) <= q < min(p + 1, w)

Therefore we can loop through the items of L using

for p in range(h + w - 1):
    for q in range(max(p-h+1, 0), min(p+1, w))
        L[h - p + q - 1][q]

---

def diagonals(L):
    h, w = len(L), len(L[0])
    return [[L[h - p + q - 1][q]
             for q in range(max(p-h+1, 0), min(p+1, w))]
            for p in range(h + w - 1) ]


matrix = [ ["A", "B", "C", "D"], ["E","F","G","H"], ["I","J","K","L"], ["M","N","O","P"], ["Q", "R", "S","T"]]

for diag in diagonals(matrix):
    print(diag)

yields

['Q']
['M', 'R']
['I', 'N', 'S']
['E', 'J', 'O', 'T']
['A', 'F', 'K', 'P']
['B', 'G', 'L']
['C', 'H']
['D']