Click here to Skip to main content
15,867,568 members
Please Sign up or sign in to vote.
5.00/5 (2 votes)
See more:
I HAVE DECIDED TO CREATE A NEW QUESTION, SINCE THIS ONE WAS GETTING VERY MESSY AND CONFUSING.

Heya, I have a 2D matrix, where each element holds a height value, an example matrix may look something like this:
1 2 3
6 5 4
7 8 9

I'm trying to find the longest path that satisfies the following criteria:
- element[i] > element[i + 1] (the next element in our chosen path is lower than the current element) (down)
- element[i] == element[i + 1] (the next element in our chosen path is the same as the current element) (straight)
- note that we can only move in 4 directions: up, down, left, right.

Furthermore the path should contain the maximal possible amount of segments, where the value decreases and the minimal possible amount of segments, where the value stays the same.

The solution for the example matrix above is as follows:
9-8-7-6-5-4-3-2-1 (8 segments down, 0 segments straight)


Finding a decreasing path is, on its own, quite simple, and there are multiple solved examples, however, I'm having trouble with devising an algorithm that would work with segments where the value can also stay the same.

Take the following matrix as an example:
0 1 2
2 2 2
3 4 5

The correct path for this matrix looks like this:
5-4-3-2-2-1-0 (5 segments down, 1 segment straight) 

Below is the same matrix, but the unvisited cells have been removed for clarity
0 1
2 2
3 4 5


What I have tried:

I have tried finding the longest path from every element of the matrix, and the choosing the one that satisfies the criteria above (max segments down, min segments straight)

Finding the longest path from element
I've tried using BFS, and then choosing the next cells based on the conditions above, but, even with a memory table, I'm unable to correctly solve more complex matrices and my implementation produces incorrect results when there are more straight segments involved.

Answer 1 (Marco Garganigo)
I've tried implementing the suggested algorithm, but I got stuck after writing the 'render' phase. I'm not sure if I understand the algorithm correctly - here's my understanding: we go over all the cells in the matrix, and if the fall under certain criteria we increment the relevant value in a separate matrix (down, same). We then use these values to find our path.

Wouldn't this algorithm only work in really small cases (ie. 2x2)? My thinking is that the algorithm doesn't "see" ahead by that far (only 1 step) and produces a lot of 'leafs' (branching paths, that potentially lead nowhere, but maybe I'm wrong - would you perhaps mind sharing a pseudo code implementation?
constexpr int dirs[4][2] = {
    { 1, 0 }, // right
    {-1, 0 }, // left
    { 0, 1 }, // down
    { 0,-1 }  // up
};


std::vector<std::vector<int>> matrix = {
    { 1, 2, 3 },
    { 6, 5, 4 },
    { 7, 8, 9 }
};

int main() {
    // [[down, same]]
    std::vector<std::vector<std::pair<int, int>>> store(matrix.size(), std::vector<std::pair<int, int>>(matrix[0].size(), std::make_pair(0, 0)));

    for (int x = 0; x < store.size(); ++x)
    {
	    for (int y = 0; y < store[0].size(); ++y)
	    {
		    for(const auto& dir : dirs)
		    {
                const int nextX = x + dir[0];
                const int nextY = y + dir[1];

                if(nextX < 0 || nextY < 0 || nextX > store[0].size() - 1 || nextY > store.size() - 1)
                {
                    continue;
                }

                if(matrix[x][y] > matrix[nextX][nextY])
                {
                    store[x][y].first++;
                }
                else if(matrix[x][y] == matrix[nextX][nextY])
                {
                    store[x][y].second++;
                }
		    }
	    }
    }
}
Posted
Updated 24-Jan-23 2:42am
v3
Comments
[no name] 19-Jan-23 2:22am    
One approach you can take to find the longest path that satisfies your criteria is to use dynamic programming. You can create a 2D array that stores the maximum number of segments of decreasing values and minimum number of segments of the same value that can be obtained from each element in the matrix.

You can use a bottom-up approach to fill in the values of this array by iterating through the matrix and for each element, checking its neighbors (up, down, left, right) to determine if it is possible to reach them while satisfying your criteria. You can then use the values stored in the array to find the longest path.

Here's an outline of the algorithm:

Create a 2D array to store the maximum number of segments of decreasing values and minimum number of segments of the same value that can be obtained from each element in the matrix.
Initialize the array with the values from the input matrix.
Iterate through the matrix and for each element, check its neighbors (up, down, left, right) to determine if it is possible to reach them while satisfying your criteria.
If it is possible to reach a neighbor, update the values in the array for that neighbor by adding 1 to the number of segments of decreasing values or leaving it the same for the number of segments of the same value.
Once you have filled in the entire array, you can use it to find the longest path by starting at the element with the highest value of maximum number of segments of decreasing values and minimum number of segments of the same value.
Follow the path by checking the values stored in the array and moving to the neighbor with the highest value.
It's worth noting that this algorithm will have a time complexity of O(n^2) since you are iterating through the matrix twice.

You can also try a Depth-First Search (DFS) with a memory table, where the DFS starts from each element of the matrix and stores the information of the maximum number of segments of decreasing values and minimum number of segments of the same value that can be obtained from each element in the matrix, this will allow you to avoid repeating the same calculation and speeds up your algorithm.

In addition, you can try to optimize your DFS algorithm by using a priority queue to sort the possible next cells based on their decreasing value, then the cells that have the same value, this way you will not have to explore all the cells, but only the ones that are most likely to be part of the solution, this can help you improve the performance of your algorithm.
Yor Gurt 20-Jan-23 9:09am    
Hi, thanks for replying! I've tried implementing your algorithm, but I got stuck + I think that this wouldn't work for all cases. See my updated question for more details.
Graeme_Grant 20-Jan-23 13:32pm    
That is a ChatGPT response, not a real answer.

1 solution

You have not specified a language, so I am guessing that you want a pseudo-code solution.

It would be something like the following

1. store current value (var_next)

2. check adjacent cells for equal to the (var_next) or less while skipping over the (var_last) cell
- true, store value to (var_next)

3. once completed all checks:
- store the current value to (var_last)
- move to (var_next)

4. repeat steps 1. to 3. until there are no more cells to move to.


If you are looking for a different type of answer, then please update your question.

UPDATE

There was a little more to this than I thought. Needed to also track the path taken.

Here is the solution that I came up with. It's written in C#:

1. Tests used:
C#
int[,] cells1 =
{
    { 1, 2, 3 },
    { 6, 5, 4 },
    { 7, 8, 9 }
};

int[]? result1 = ProcessCells(cells1);
DisplayResults(cells1, result1);

int[,] cells2 =
{
    { 0, 1, 2 },
    { 2, 2, 2 },
    { 3, 4, 5 }
};

int[]? result2 = ProcessCells(cells2);
DisplayResults(cells2, result2);

int[,] cells3 =
{
    { 6, 6, 6 },
    { 5, 8, 7 },
    { 4, 8, 9 }
};

int[]? result3 = ProcessCells(cells3);
DisplayResults(cells3, result3);

// test a single cell matrix
int[,] singleCells =
{
    { 1 }
};

int[]? singleResult = ProcessCells(singleCells);
DisplayResults(singleCells, singleResult);

// test a large matrices
int[,] largeMatrix1 =
{
    { 8, 9, 10, 11, 12, 13, },
    { 7, 16, 15, 14, 14, 14, },
    { 6, 17, 30, 31, 32, 33, },
    { 5, 18, 29, 26, 25, 34, },
    { 4, 19, 28, 27, 24, 35, },
    { 3, 20, 21, 22, 23, 36, },
};

int[]? largeResult1 = ProcessCells(largeMatrix1);
DisplayResults(largeMatrix1, largeResult1);

int[,] largeMatrix2 =
{
    { 1, 1, 1, 1, 1, 2, },
    { 1, 3, 2, 2, 2, 2, },
    { 1, 3, 8, 8, 8, 8, },
    { 1, 4, 7, 6, 6, 9, },
    { 1, 4, 7, 6, 6, 9, },
    { 0, 4, 5, 5, 5, 9, },
};

int[]? largeResult2 = ProcessCells(largeMatrix2);
DisplayResults(largeMatrix2, largeResult2);

// test a solution that can not be completed
int[,] badCells =
{
    { 0, 0, 3 },
    { 6, 0, 4 },
    { 7, 8, 9 }
};

int[]? badResult = ProcessCells(badCells);
DisplayResults(badCells, badResult);

And here is the code:
C#
static int[]? ProcessCells(int[,] cells)
{
    // get the bounds of the array
    int rows = cells.GetLength(0);
    int cols = cells.GetLength(1);

    // is the array valid?
    if (rows < 1) return default;
    if (cols < 1) return default;

    // remember where we have been...
    int[,] path = new int[rows, cols];

    // track the results
    int[] results = new int[rows * cols];

    // initialize results to failed
    for (int i = 0; i < results.Length; i++)
        results[i] = -1;

    // initialize the starting value and cell
    int startValue = cells[rows - 1, cols - 1];
    int currentValue = startValue;
    int[] currentCell = {rows - 1, cols - 1};
    path[rows - 1, cols - 1] = -1;

    // set pointer to start of results
    int index = 0;

    // log the start cell
    results[index] = cells[currentCell[0], currentCell[1]];

    // now walk the 2D array
    while (currentCell[0] >= 0 && currentCell[1] >= 0)
    {
        // track valid cell
        int[]? nextCell = default;
        int nextValue = -1;

        // look around
        for (int direction = 0; direction < 4; direction++)
        {
            // get the adjacent cell that we want to look at
            int[]? cell = GetValidAdjacentCell(direction, currentCell, rows, cols);

            // check if not a valid direction
            if(cell is null ||  path[cell[0], cell[1]] != 0)
                continue;

            int testValue = cells[cell[0], cell[1]];

            // do we have a valid value?
            if ((testValue == currentValue || testValue == currentValue - 1) &&
                Math.Max(nextValue, testValue) == testValue)
            {
                nextValue = testValue;
                nextCell = new[] { cell[0], cell[1] };
            }
        }
        
        // no more to do
        if (nextCell is null)
            break;

        // track value
        results[++index] = cells[nextCell[0], nextCell[1]];
        
        // track where we are
        currentCell = new[] { nextCell[0], nextCell[1] };
        currentValue = nextValue;

        // track where we have been
        path[nextCell[0], nextCell[1]] = -1;
    }

    // we are all done
    return results;
}

static int[]? GetValidAdjacentCell(int direction, int[] currentCell, int rows, int cols)
{
    int cr = currentCell[0];
    int cc = currentCell[1];

    // check based on importance of order

    if (direction == 0) // left
        return cc == 0 ? default : new[] { cr, --cc };

    if (direction == 1) // right
        return cc == cols - 1 ? default : new[] { cr, ++cc };

    if (direction == 2) // down
        return cr == 0 ? default : new[] { --cr, cc };

    if (direction == 3) // up
        return cr == rows - 1 ? default : new[] { ++cr, cc };

    // invalid direct value
    return default;
}

static void DisplayResults(int[,] cells, int[]? path)
{
    int rows = cells.GetLength(0);
    int cols = cells.GetLength(1);

    int padLeft = cells[rows - 1, cols - 1].ToString().Length + 1;

    Console.WriteLine("Matrix Traversed:");
    for (int row = 0; row < rows; row++)
    {
        for (int col = 0; col < cols; col++)
            Console.Write(cells[row, col].ToString().PadLeft(padLeft));
        
        Console.WriteLine();
    }
    Console.WriteLine();

    int count = path.Count(value => value != -1);

    if (path.Length != count)
        Console.WriteLine($"Path cannot be completed. Only traversed {count} cells of {path.Length}");

    Console.WriteLine($"Path found: {string.Join(", ", path)}");
    
    Console.WriteLine();
}

3. And the output:
Matrix Traversed:
 1 2 3
 6 5 4
 7 8 9

Path found: 9, 8, 7, 6, 5, 4, 3, 2, 1

Matrix Traversed:
 0 1 2
 2 2 2
 3 4 5

Path found: 5, 4, 3, 2, 2, 2, 2, 1, 0

Matrix Traversed:
 6 6 6
 5 8 7
 4 8 9

Path found: 9, 8, 8, 7, 6, 6, 6, 5, 4

Matrix Traversed:
 1

Path found: 1

Matrix Traversed:
  8  9 10 11 12 13
  7 16 15 14 14 14
  6 17 30 31 32 33
  5 18 29 26 25 34
  4 19 28 27 24 35
  3 20 21 22 23 36

Path found: 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 14, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3

Matrix Traversed:
 1 1 1 1 1 2
 1 3 2 2 2 2
 1 3 8 8 8 8
 1 4 7 6 6 9
 1 4 7 6 6 9
 0 4 5 5 5 9

Path found: 9, 9, 9, 8, 8, 8, 8, 7, 7, 6, 6, 6, 6, 5, 5, 5, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0

Matrix Traversed:
 0 0 3
 6 0 4
 7 8 9

Path cannot be completed. Only traversed 4 cells of 9
Path found: 9, 8, 7, 6, -1, -1, -1, -1, -1

The last test will fail as it has no complete path.

All code is fully commented.

Enjoy!
 
Share this answer
 
v3
Comments
Yor Gurt 20-Jan-23 9:20am    
Hello, thanks for replying. Would you mind being a bit more specific or perhaps even sharing some real code (your preferred language :D)? What does 'store' mean exactly in this context? Are you telling me to create a dynamic array, store cells in it, go through steps 1 through 3 and continue until I don't have any elements in it? I think I'm thinking a bit too much about it and I'm getting stuff confused. Thanks
Graeme_Grant 20-Jan-23 17:47pm    
All good ... see my updated answer with fully commented code. It was an interesting challenge.

PS: I'll leave the straight part to you! 😉

PPS: I will give you a hint ... use this to track direction and not set to -1. You can then find the longest straight path.
path[nextCell[0], nextCell[1]] = -1;
Yor Gurt 22-Jan-23 11:05am    
Thanks for the amazing example! I've reimplemented it in my language of choice and all works well, but I'm not really sure how to modify the algorithm so that it prefers going down instead of straight (the goal of the algorithm is to find a path that contains the highest amount of 'down' segments and lowest amount of 'straight' segments). I've tried fiddling around with the path direction just like you suggested, but all my attempts ended in vain - do you have any suggestions? Thanks.
Graeme_Grant 22-Jan-23 15:12pm    
I have done the difficult part for you, now you have the easy part. I did code it a little different to yours to make it easier to understand...

According to your information, you are allowed to move in all 4 directions, not just straight and down. My understanding is that you need to work out which segments are the longest down part and the longest straight part. You have the path, now it is just a matter of either keeping track of or analyzing post-path findings. So have two variables that count, based on the horizontal movement (left or right) and the down movement. Max value for each is tracked.
Yor Gurt 23-Jan-23 4:56am    
I’m afraid there seems to have been a slight misunderstanding - when I talk about going 'down' and 'straight' I'm talking about the value of the matrix decreasing or staying the same from cell-to-cell. (meaning that I'm not looking for anything related to the direction of the path, but for a path, that contains as many segments where the value decreases while minimizing the number of segments where the value stays the same (see my explanation in my original question for a better definition)). Sorry about that :D

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900