Search through the diagonals of a matrix

[Rik30]

Hello!

I'm trying to find the longest sequence of equal elements in a matrix M x N. I use two nested for-loops to search into the rows and compare the cells - same thing for the columns. When two adjacent elements are equal, I increment a counter. If the counter is greater than the previous one, I save the new counter value and the current element.

Now I should search in the diagonal directions. How can I do? If i and j are the indexes of a cell, the main diagonal (from left to right) has i == j. But for the secondary diagonals (from left to right and from right to left)? I also have a problem to reach the border of the matrix to avoid the IndexOutOfRangeException... Any help is appreciated.

[ddanbe]

Hi Rik30, welcome at DaniWeb. :)
Could you show us the method you're having trouble with?

[Rik30]

Sure! :) I have written the following code:

for (int i=0; i<arr.Length(0)-1; i++) // check rows
{
    for (int j=0; j<arr.Length(1)-1; j++)
    {
        if(arr[i,j]==arr[i,j+1])
            k++;

        if(k > temp)
        {
            temp = k;
            value = arr[i,j];
        }
    }

    k = 0;
}

for (int i=(arr.GetLength(0)-2); i>=0; i--) // check diagonals (left to right) ?
{
    while (!border) // border ??
    {
        if (arr[i,j] == arr[i+1,j+1])
        {
            k++;
        }

        if (k > temp)
        {
            temp = k;
            value = arr[i,j];
        }

        j++; // ?
    }

      counter = 0;
 }

But I cannot imagine a method for the diagonal directions... I also did some sketches on a sheet of paper to find a solution...

[ddanbe]

You say you have IndexOutOfRangeExceptions could you explain what your Length method is doing?
And to traverse diagonal, do you mean
1 2 3
4 5 6
7 8 9
[3] [2,6] [1,5,9] [4,8] [7] ?

[Rik30]

Yes, I mean it. The matrix can be of any size N x M.

I'd start from the penultimate row, first column (the corners cannot be a sequence). Then, I'd compare the cell with another that has indexes i+1 and j+1 (as temporary values?), and so on... until the border is reached. But how can I be sure that I have reached the border? When the row is 0 (after decrements), I should increment the column... (?)

[ddanbe]

OK, Took me awhile but this code will print out the diagonal values of a MxN array.

for (int i = 0; i < M; i++)
            {
                int j = 0;
                int k = i;

                Console.WriteLine("Diagonal nr {0}", diagCnt);
                diagCnt++;
                while (j < N && k >= 0)
                {
                    Console.WriteLine(">> {0}", R[j, k]);
                    k--;
                    j++;
                }               
            }
            for (int i = 1; i < M; i++)
            {
                int j = M - 1;
                int k = i;

                Console.WriteLine("Diagonal nr {0}", diagCnt);
                diagCnt++;
                while (j >= 0 && k < N)
                {
                    Console.WriteLine(">> {0}", R[k, j]);
                    k++;
                    j--;
                }               
            }   
            Console.ReadKey();

[Rik30]

Thank you! :)

It was quite tricky for me

[Rik30]

Hmm... there is an issue. I solved it by noting that the sum of the indexes is the same (from right to left).

Example:
1 2 3
4 5 6
7 8 9

[2,4] has i + j = 1
[3,5,7] has i + j = 2
[6,8] has i + j = 3

But for the other diagonals (left-to-right)?

[ddanbe]

Still working on a solution in all directions. Been in hospital lately, I'll keep in touch.

[Rik30]

No problem, thank you once again for your time :)

PS: I'm not English... I have written "issue" instead of "problem" thinking it is a synonym. I'm sorry for the misunderstanding

[Rik30]

Resolved.

To find the right-to-left diagonals I have split the problem in two sub-problems: the lower left and the upper right of the matrix.