Maximum sum path in a matrix from top to bottom

Question

An easy way to do this is with a Queue.

Add the first row
for every item in the queue, add any other valid moves
when finished, check if it’s a valid combination
check against the last highest

It uses an and Iterator method, Linq, and queues to return current best finds. What I suggest you do, is research the parts involved, step through it and inspect variables, use Console.WriteLine to look at what is happening. If you are really stuck you can always ask further questions about this code and what it’s doing.

The idea of the queue is, we add each element in the first row as initial items in the queue (that is our precondition by the rules you have given), then we go and look at the first element in the queue, then from that position (x,y) we go through all the next positions in the next row that we can legitimately visit. The queue also hold a list of columns visited and a value at that position. It could be done differently. I.e we really only need to to know the sum of all elements visited and a list of columns etc so we can validate the path afterwards.

_{Note : This is not the most optimal solution and it could be done a lot more efficiently and in less code in many other ways (and more elegantly). However, it touches on a lot of common concepts that are worth understanding}

Given

private static Random _rand = new Random();

// this could be done with linq, however it's easy to see how it works
private static bool IsPathValid(int length, List<int> path)
{
    for (var i = 0; i < length; i++)
        if (!path.Contains(i))
            return false;
    return true;
}

Iterator

public static IEnumerable<IEnumerable<(int col, int value)>> FindPath(int[, ] matrix)
{
    var queue = new Queue<(int x, int y, List<(int col, int value)> path)>();
    // add the first row to the queue
    for (var i = 0; i < matrix.GetLength(1); i++)
        queue.Enqueue((i, 0, new List<(int col, int value)>()));
    // lets keep the higest found
    var highest = int.MinValue;
    // loop all queue items until none left
    while (queue.Any())
    {
        // get the next item out of the queue
        var(x, y, path) = queue.Dequeue();
        // add the path we are visiting
        path.Add((x, matrix[y, x]));
        // if we have looked at all the rows, then time to return
        if (y + 1 == matrix.GetLength(0))
        {
            // get a list of columns visited 
            var cols = path.Select(x => x.col).ToList();
            // check to see if all columns are visited
            if (IsPathValid(matrix.GetLength(1), cols))
            {
                var sum = path.Sum(x => x.value);
                // sum the path, if it's not the highest we don't care
                if (sum > highest)
                {
                    // we are the highest path so far so let's return it
                    yield return path;
                    highest = sum;
                }
            }

            continue;
        }

        // where ever we are, lets look at all the valid x's in the next row
        var start = Math.Max(0, x - 1);
        var finish = Math.Min(matrix.GetLength(1) - 1, x + 1);
        // add them to the queue
        // we inefficiently create a new path, as list is a reference type and we don't want to reuse it
        for (var newX = start; newX <= finish; newX++)
            queue.Enqueue((newX, y + 1, new List<(int col, int value)>(path)));
    }
}

Usage

// create a random matrix, make sure there the dimensions are going to produce a result
var y = _rand.Next(2, 5);
var matrix = new int[_rand.Next(y, y + 3), y];

// fill and print the matrix
Console.WriteLine("Matrix");
Console.WriteLine();
for (var i = 0; i < matrix.GetLength(0); i++)
{
   for (var j = 0; j < matrix.GetLength(1); j++)
   {
      matrix[i, j] = _rand.Next(0, 20);
      Console.Write(matrix[i, j].ToString().PadLeft(3));
   }

   Console.WriteLine();
}


Console.WriteLine();
Console.WriteLine("Best Path (column,Value)");
Console.WriteLine();

// get the best, which be the last
var best = FindPath(matrix).Last();
foreach (var item in best)
{
   Console.WriteLine(item);
}

// show the result
Console.WriteLine();
Console.WriteLine("= " + best.Sum(x => x.value));

Output

Matrix

 14  9 17  0
 19  5 11 10
 17 12  9 13
  3 11  2  5
  0  0 12 15

Best Path (column,Value)

(0, 14)
(0, 19)
(1, 12)
(2, 2)
(3, 15)

= 62

Full Demo Here

Additional Resources

Leave a Comment Cancel Reply