1
\$\begingroup\$

How can I improve this?

The idea is to store every left to right diagonals in a list

Not looking for a more efficient algorithm instead something readable, LINQ perhaps?

input:

3, 1
2, 5, 7
1, 5, 8, 3, 1, 4
6, 8, 7, 1
4
6
6, 2, 5

output:

1, 7, 3,
3, 5, 8, 1,
7, 3,
5, 8, 1,
2, 5, 7,
8, 1,
5, 7,
1, 8,
6, 2,

--

    var arr = new[]
{
    new[]{3,1},
    new[]{2,5,7},
    new[]{1,5,8,3,1,4},
    new[]{6,8,7,1},
    new[]{4},
    new[]{6},
    new[]{6,2,5}
};

GetAllDiagonals(arr);
Console.ReadKey();

static void GetAllDiagonals(int[][] array)
{
    var e = new List<List<int>>();

    for (var i = 0; i < array.Length; i++)
    {
        for (var j = array[i].Length - 1; j >= 0; j--)
        {
            var n = i;
            var x = j;
            var next = i + 1 <= array.Length - 1 && j < array[n + 1].Length - 1;
            var index = 0;
            if (next)
            {
                e.Add(new List<int>());
                index = e.Count - 1;
            }

            while (next)
            {
                e[index].Add(array[n][x]);
                next = n + 1 <= array.Length - 1 && x < array[n + 1].Length - 1;
                n++; x++;
            }
        }
    }

    for (var i = 0; i < e.Count; i++)
    {
        for (var j = 0; j < e[i].Count; j++)
        {
            Console.Write(e[i][j] + ", ");
        }
        Console.WriteLine();
    }
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Are you sure about the expected output is correct? Like why does it include 5 8 1 it's not diagonal? According to my understand the result should include these: 1 8, 2 5 7, 3 5 8 1 and 1 7 3. Or please define what do you mean by diagonal \$\endgroup\$ Nov 16, 2022 at 15:16
  • 1
    \$\begingroup\$ This conditional j <= e[i].Count - 1 really should be j < e[i].Count. \$\endgroup\$
    – Rick Davin
    Nov 16, 2022 at 15:17
  • \$\begingroup\$ Yes @PeterCsala my initial purpose was to store only the one mentioned however it proved more difficult \$\endgroup\$
    – Laycoonz
    Nov 16, 2022 at 18:00
  • \$\begingroup\$ @Laycoonz On the contrary that simplifies design. You have to start the diagonal searching only from the first column or from the first row. Tomorrow I will leave a post with the details. \$\endgroup\$ Nov 16, 2022 at 19:38

1 Answer 1

3
\$\begingroup\$

Disclaimer: Apologise for my poor visualisation. I've used Excel to draw the bellow diagrams.


Finding the diagonal step-by-step

Let's play a little bit with your example

the original matrix

As you have said it in your question you want to find all left to right diagonals.

I've used the following informal definition for the left to right diagonal:

  • A descending line which starts either from the left or from the top side of the matrix until there is a number in the way of it
  • The minimum length of the line is two

I haven't read any requirements regarding the ordering so, lets suppose you want to find them from left to right

first second third fourth fifth

Algorithm

I hope you have noticed the following part (highlighted with bold) in my informal definition:

A descending line which starts either from the left or from the top side of the matrix until there is a number in the way of it

That means you have to have two top level iterations

  • On the 1st column from bottom to the top
  • On the 1st row from left to right

bottom to top left to right

To find a diagonal you need the following steps:

  1. Increment both column and row indices
  2. Check whether there is a number under the new indices
    1. If yes repeat step 1 and 2
    2. If not then check line's length
      1. If it is greater than one then you have found a diagonal
      2. If it is 1 then you continue the iteration on the top-level

Implementation

Now let's see how do we implement the above algorithm.
Let's start with the diagonals search which starts from left

static List<List<int>> FindDiagonalsWhichStartsFromLeft(int[][] input)
{
    var diagonals = new List<List<int>>();
    //Bottom top iteration on first column
    for (int row = input.Length - 1; row > 0; row--)
    {
        int rowIndex = row, columnIndex = 0;
        var diagonal = new List<int>()
        {
            input[rowIndex][columnIndex]
        };

        //#2.1 If yes repeat step 1 and 2
        while (true)
        {
            //#1 Increment both column and row indices
            rowIndex++; columnIndex++;

            //#2 Check whether there is a number under the new indices
            if (rowIndex >= input.Length ||
                columnIndex >= input[rowIndex].Length)
            {
                break;
            }

            diagonal.Add(input[rowIndex][columnIndex]);
        }

        //#2.2.1 If it is greater than one then you have found a diagonal
        if (diagonal.Count > 1)
        {
            diagonals.Add(diagonal);
        }

        //#2.2.2 If it is 1 then you continue the iteration on the top-level
    }

    return diagonals;
}

Please note that we have done a reverse loop here from the last row till the 2nd row. We skipped the 1st row because otherwise the main diagonal will be found twice

main diagonal

Of course you can avoid this duplicate in another way like starting from the 2nd column whenever you are searching for diagonals which is starting from the top. (Where to put the prevention logic is up to you.)

Now let's see the other iteration

static List<List<int>> FindDiagonalsWhichStartsFromTop(int[][] input)
{
    var diagonals = new List<List<int>>();
    //Left to Right iteration on first row
    for (int column = 0; column < input[0].Length; column++)
    {
        int rowIndex = 0, columnIndex = column;
        var diagonal = new List<int>()
    {
        input[rowIndex][columnIndex]
    };

        //#2.1 If yes repeat step 1 and 2
        while (true)
        {
            //#1 Increment both column and row indices
            rowIndex++; columnIndex++;

            //#2 Check whether there is a number under the new indices
            if (rowIndex >= input.Length ||
                columnIndex >= input[rowIndex].Length)
            {
                break;
            }

            diagonal.Add(input[rowIndex][columnIndex]);
        }

        //#2.2.1 If it is greater than one then you have found a diagonal
        if (diagonal.Count > 1)
        {
            diagonals.Add(diagonal);
        }

        //#2.2.2 If it is 1 then you continue the iteration on the top-level
    }

    return diagonals;
}

As you can see the only difference here is the outer loop. So, the "core logic" is untouched which means we can extract that into its own method

static void GetDiagonal(int[][] input, List<int> diagonal, int rowIndex, int columnIndex)
{
    //#2.1 If yes repeat step 1 and 2
    while (true)
    {
        //#1 Increment both column and row indices
        rowIndex++; columnIndex++;

        //#2 Check whether there is a number under the new indices
        if (rowIndex >= input.Length ||
            columnIndex >= input[rowIndex].Length)
        {
            break;
        }

        diagonal.Add(input[rowIndex][columnIndex]);
    }
}

For the sake of completeness let me share with you the full source code (without comments for the sake of brevity)

static void Main()
{
    var arr = new[]
    {
        new[]{3,1},
        new[]{2,5,7},
        new[]{1,5,8,3,1,4},
        new[]{6,8,7,1},
        new[]{4},
        new[]{6},
        new[]{6,2,5}
    };
    FindAndPrintDiagonals(arr);
}

static void FindAndPrintDiagonals(int[][] input)
{
    var diagonalsFromLeft = FindDiagonalsWhichStartsFromLeft(input);
    var diagonalsFromTop = FindDiagonalsWhichStartsFromTop(input);
    foreach (var diagonal in diagonalsFromLeft.Union(diagonalsFromTop))
    {
        Console.WriteLine(string.Join(" ", diagonal));
    }
}

static List<List<int>> FindDiagonalsWhichStartsFromLeft(int[][] input)
{
    var diagonals = new List<List<int>>();
    for (int row = input.Length - 1; row > 0; row--)
    {
        int rowIndex = row, columnIndex = 0;
        var diagonal = new List<int>()
        {
            input[rowIndex][columnIndex]
        };

        GetDiagonal(input, diagonal, rowIndex, columnIndex);
        if (diagonal.Count > 1)
            diagonals.Add(diagonal);
    }
    return diagonals;
}

static List<List<int>> FindDiagonalsWhichStartsFromTop(int[][] input)
{
    var diagonals = new List<List<int>>();
    for (int column = 0; column < input[0].Length; column++)
    {
        int rowIndex = 0, columnIndex = column;
        var diagonal = new List<int>()
        {
            input[rowIndex][columnIndex]
        };

        GetDiagonal(input, diagonal, rowIndex, columnIndex);
        if (diagonal.Count > 1)
            diagonals.Add(diagonal);
    }
    return diagonals;
}

static void GetDiagonal(int[][] input, List<int> diagonal, int rowIndex, int columnIndex)
{
    while (true)
    {
        rowIndex++; columnIndex++;
        if (rowIndex >= input.Length || columnIndex >= input[rowIndex].Length)
            break;
        
        diagonal.Add(input[rowIndex][columnIndex]);
    }
}

Here is a working dotnetfiddle link.
You should see the following output on the console:

6 2
1 8
2 5 7
3 5 8 1
1 7 3
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I take my hat off to you, very good and extensible explanation thank you \$\endgroup\$
    – Laycoonz
    Nov 17, 2022 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.