Extracting a list of all diagonals from a matrix in a specific direction

Question

I'm trying to extract from a matrix all the diagonals in a certain direction, for example down-right.

For the following matrix:

A   B   C   D
E   F   G   H
I   L   M   N

the expected result should be

[ [A F M], [B G N], [C H], [D], [E L], [I] ]

A general approach is welcome.

The language I'm using is Java.

Thanks!

EDIT

String[] grid = {"SUGAR", 
                 "GLASS", 
                 "MOUSE"};

for( int k = 0; k < grid.length; k++ )
{   
    StringBuffer buffer = new StringBuffer( );

    for( int i = 0; i < grid.length
                && i+k < grid[0].length( ); i++ )
    {
        buffer.append( grid[i].charAt(i+k) );
    }

    trie.addWord( buffer.toString() );
}

output words added to the trie are

[ "SLU" "UAS" "GSE" ]

expected strings stored in the trie (order doesn't matter )

[ "SLU" "UAS" "GSE" "GO" "M" "AS" "R"]

Answer 1

This was an interesting problem to solve.

It's easy to get tangled up in nested loops.

I noticed if I put the words together into one string, a pattern emerged.

Taking the OP's example, the three words "SUGAR", "GLASS", "MOUSE" are concatenated together into SUGARGLASSMOUSE.

Here are the zero based character positions of the characters that I need to get from the concatenated string. I've lined them up so you can more easily see the pattern.

          10     M
     5    11     GO
0    6    12     SLU
1    7    13     UAS
2    8    14     GSE
3    9           AS
4                R

See the pattern yet? I have 3 indexes that consist of 5 iterations. I have 3 words that consist of 5 letters.

The number of diagonal words is letters + words - 1. We subtract 1 because the first letter in character position 0 is only used once.

Here are the results from a test I ran.

[ "SUGAR" "GLASS" "MOUSE" "STATE" "PUPIL" "TESTS" ]
[ "T" "PE" "SUS" "MTPT" "GOAIS" "SLUTL" "UASE" "GSE" "AS" "R" ]

[ "SUGAR" "GLASS" "MOUSE" ]
[ "M" "GO" "SLU" "UAS" "GSE" "AS" "R" ]

And here's the code:

import java.util.ArrayList;
import java.util.List;

public class Matrix {

    public static final int DOWN_RIGHT = 1;
    public static final int DOWN_LEFT = 2;
    public static final int UP_RIGHT = 4;
    public static final int UP_LEFT = 8;

    public String[] getMatrixDiagonal(String[] grid, int direction) {
        StringBuilder builder = new StringBuilder();
        for (String s : grid) {
            builder.append(s);
        }
        String matrixString = builder.toString();

        int wordLength = grid[0].length();
        int numberOfWords = grid.length;
        List<String> list = new ArrayList<String>();


        if (wordLength > 0) {
            int[] indexes = new int[numberOfWords];

            if (direction == DOWN_RIGHT) {
                indexes[0] = matrixString.length() - wordLength;
                for (int i = 1; i < numberOfWords; i++) {
                    indexes[i] = indexes[i - 1] - wordLength;
                }

                int wordCount = numberOfWords + wordLength - 1;

                for (int i = 0; i < wordCount; i++) {
                    builder.delete(0, builder.length());
                    for (int j = 0; (j <= i) && (j < numberOfWords); j++) {
                        if (indexes[j] < wordLength * (wordCount - i)) {
                            char c = matrixString.charAt(indexes[j]);
                            builder.append(c);
                            indexes[j]++;
                        }
                    }
                    String s = builder.reverse().toString();
                    list.add(s);
                }
            }

            if (direction == DOWN_LEFT) {
                // Exercise for original poster
            }

            if (direction == UP_RIGHT) {
                // Exercise for original poster
            }

            if (direction == UP_LEFT) {
                // Exercise for original poster
                // Same as DOWN_RIGHT with the reverse() removed
            }
        }

        return list.toArray(new String[list.size()]);
    }

    public static void main(String[] args) {
        String[] grid1 = { "SUGAR", "GLASS", "MOUSE", "STATE", "PUPIL", "TESTS" };
        String[] grid2 = { "SUGAR", "GLASS", "MOUSE" };

        Matrix matrix = new Matrix();
        String[] output = matrix.getMatrixDiagonal(grid1, DOWN_RIGHT);
        System.out.println(createStringLine(grid1));
        System.out.println(createStringLine(output));

        output = matrix.getMatrixDiagonal(grid2, DOWN_RIGHT);
        System.out.println(createStringLine(grid2));
        System.out.println(createStringLine(output));
    }

    private static String createStringLine(String[] values) {
        StringBuilder builder = new StringBuilder();
        builder.append("[ ");

        for (String s : values) {
            builder.append("\"");
            builder.append(s);
            builder.append("\" ");
        }

        builder.append("]");

        return builder.toString();
    }

}

Answer 2

If your data is in table form, you could just scan the matrix up the first column, then left across the first row.

final String[M][N] mtx = { ... };

public List<List<String>> diagonalize() {
    final List<List<String>> diags = new ArrayList<>();
    for (int row = M - 1; row > 1; --row) {
        diags.add(getDiagonal(row, 0));
    }
    for (int col = 0; col < N; ++col) {
        diags.add(getDiagonal(0, col));
    }
    return diags;
}

private List<String> getDiagonal(int x, int y) {
    final List<String> diag = new ArrayList<>();
    while (x < M && y < N) {
        diag.add(mtx[x++][y++]);
    }
    return diag;
}