Click here to Skip to main content
15,867,308 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
The original question can be found here, I've decided to create a new thread, since the old one was getting very confusing for newcomers

I have a 2D matrix, that may look something like this:
0 1 2
5 4 3
7 8 9

I'm trying to find a path that contains the highest number of segments, where the value decreases, so that when we find our path the following parameter is true:
finalPath[0] > finalPath[1]

This, on it's own has, as far as I know, been solved, but I also have to account for segments, where the value stays the same, this can be described in the following expression
finalPath[0] == finalPath[1]

SOME OTHER RULES AND DEFINITIONS:
- The highest value in the matrix does not have to be the optimal starting point.
- We can only move in the 4 cardinal directions (up, down, left, right)
- We may not visit an already visited cell
- A 'segment' refers to two elements next to each other (ie. matrix[0][0] and matrix[1][0] form a segment, the value different between these elements is what we are examining)
- The correct starting point can be located anywhere in the matrix

FINAL GOAL OF THE ALGORITHM: Minimize the number of straight segments and maximize the number of segments where the value decreases.
Note that the 'direction' of the path is irrelevant

TEST SCENARIOS:
0 1 2
5 4 3
7 8 9

Final path:
[9, 8, 7, 5, 4, 3, 2, 1, 0]
(All path segments are decreasing, this is the simplest scenario)
0 1 2
2 2 2
3 4 5

Final path:
[5, 4, 3, 2, 2, 1, 0]
(We do not traverse all of the elements, since we are looking to maximize the number of decreasing segments)

What I have tried:

See the old question for what I've tried so far.
Posted
Updated 29-Jan-23 0:44am
v2
Comments
[no name] 26-Jan-23 13:48pm    
Add 2 extra rows and colums (5x5). Then you can use one function to iterate the interior 3x3 matrix (in terms of x-1, y; x, y-1; x+1, y; x, y+1) without having to get too fancy (cell is invalid, same, higher, lower).

1 solution

Below are the changes in my previous solution to get the result that you wanted.

Form this:
C#
if ((testValue == currentValue || testValue == currentValue - 1) &&
	Math.Max(nextValue, testValue) == testValue)
{
	nextValue = testValue;
	nextCell = new[] { cell[0], cell[1] };
}

To this:
C#
if (testValue == currentValue || testValue == currentValue - 1)
{
    nextValue = testValue;
    nextCell = new[] { cell[0], cell[1] };
    if (Math.Min(nextValue, testValue) == testValue)
        break;
}

And changed to order of direction checks from:
C#
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 };

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

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

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

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

Full code below:
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);

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)
            {
                nextValue = testValue;
                nextCell = new[] { cell[0], cell[1] };
                if (Math.Min(nextValue, testValue) == testValue)
                    break;
            }
        }
        
        // 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) // up
        return cr == rows - 1 ? default : new[] { ++cr, cc };

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

    if (direction == 3) // right
        return cc == cols - 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();

    Console.WriteLine($"Path found: {string.Join(", ", path.Where(x => x > -1))}");
    
    Console.WriteLine();
}

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, 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, 5, 5, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 0

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

Path found: 9, 8, 7, 6

As for longest horizontal/vertical segment, I leave that to you.
 
Share this answer
 
v2

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