7

Came across this problem -- You are given a grid with numbers that represent the elevation at a particular point. From each box in the grid you can go north, south, east, west - but only if the elevation of the area you are going into is less than the one you are in, i.e. you can only descend. You can start anywhere on the map and you are looking for a starting point with the longest possible path down as measured by the number of boxes you visit. And if there are several paths down of the same length, you want to take the one with the steepest vertical drop, i.e. the largest difference between your starting elevation and your ending elevation. Ex Grid:

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

On this particular map the longest path down is of length=5 and it is: 9-5-3-2-1.

There is another path that is also length five: 8-5-3-2-1. dropping from 9 to 1(8) is a steeper drop than 8 to 1(7). WAP to find the longest (and then steepest) path.

I've worked through Floyd Warshalls, DAG + Topological sorting, tried to think of DFS, though about DP, various things but I am not able to find a way to think through. Any pointers + simple pseudo code for approach would be helpful.

  • 2
    I haven't thought the problem through fully, but it looks to me like a modification of A* search should work on it. – Jules Jan 4 '16 at 10:34
10

A few observations about this problem.

  1. You are looking for the longest path with the given constraint, so it is not helpful to use A* or Floyd-Warshall which are designed to find the shortest path.

  2. In extreme cases, the path could contain all fields of the grid, e.g.:

    1 2 3
    8 9 4
    7 6 5
    

    (here, the path forms a spiral, but other figures are possible.)

    Therefore, an ideal algorithm cannot be better than O(n), which is also the same complexity as visiting each field once.

  3. Given a field F and its surrounding fields N, E, S, W as far as they exist, we can calculate the path length L(F) as

           ⎧ 1 + F(M) if M exists
    L(F) = ⎨
           ⎩ 0        otherwise
    

    where M ∈ {N, E, S, W} so that Value(M) < Value(F) and F(M) = max({F(X) | X ∈ {N, E, S, W}}). As pseudo-code:

    def L(F):
      lower = {X for X in {N, E, S, W} if X.value < F.value}
      if lower.is_empty:
        return 0
      return 1 + max({ L(X) for X in lower})
    

    Proof of correctness is left as an exercise to the reader.

  4. The function L(F) may be calculated using memoization. That is, we build a cache for L(F) so that each field is only calculated once. At the beginning, each calculation might involve the calculations for other fields as well, in the worst case all fields. Therefore, our memoized L(F) has complexity O(n) to O(1) depending on whether the cache already contains the necessary values. But on average over the whole cache complexity is O(1) (each value is computed only once, and is only requested a constant number of times).

    So if we iterate over all fields and calculate the path length for that field, this iteration will be O(n). Therefore, this algorithm with memoization is ideal!

  5. We cannot apply dynamic programming, since we do not know which fields would have to be calculated first. Well, we could sort all fields by their value and start calculating lowest first, but that would end up being more expensive and way more complicated than building the cache lazily.

  6. While calculating L(F), we can also somehow keep track of the path that contains some field, and the currently longest paths. All of this will not affect the complexity.

Together, the following approach emerges:

  • each field in your matrix has three properties: value, length, and next field in the path.
  • as an implementation detail, you'll have to figure out how to retrieve the neighbour fields for a given field.
  • the length is lazily calculated.
  • when the M neighbour is selected, the next field is set to M. This might be problematic if more than one field has the properties of M, e.g. in this matrix:

    1 2 3
    4 9 8
    5 8 9
    

    Starting from the 9s, it is not immediately clear which 8 should be part of the ideal path. Either you implement this to keep track of all possible paths (which does not affect the complexity), or you select the partial path with the steepest descent. This will require you to walk both paths which is not free but O(n). To avoid this, you can memoize the maximum slope as an additional property of each field.

    By the way, that example shows a case where there are two solutions 9-8-3-2-1.

Pseudo-code:

record Field {
  value  : Int
  length : Count? = null
  next   : Field? = null
  slope  : Int?   = null
}

get-neighbours(f : Field): Set[Field] {
  ...
}

get-length(f : Field): Int {
  if f.length != null {
    return f.length
  }

  let next : Collection[Field] = get-neighbours(f)
    .where(x -> x.value < f.value) // must be smaller
    .max-by(x -> get-length(x)) // must have longest partial path
    .max-by(x -> x.slope) // prefer steepest path

  if next.is_empty {
    f.length = 0
    return f.length
  }

  let next = next.first // pick any field that satisfies all properties
  f.next = next
  f.slope = next.slope ?? f.value - next.value
  f.length = 1 + next.length
  return f.length
}

get-path(f: Field): Field generator {
  yield f
  if f.next != null {
    yield from get-path(f.next)
  }
}

let matrix : Array[height, Array[width, Field]] = {
  { Field(1), ... },
  ...,
}

// evaluate length for each field in matrix
// and keep track of longest paths

let mut longest = List()
let mut length = 0

for f in matrix {
  let l = get-lengh(f)
  if l > length {
    length = get-length(f)
    longest = List(f)
  }
  else if l == length {
    longest.add(f)
  }
}

// print out longest paths
for start in longest {
  println(List(get-path(start)))
}
  • does this work when you have multiple equal length paths? It seems to me you cant solve the problem with a single L value per squarr – Ewan Jan 4 '16 at 15:00
  • @Ewan Since we are searching for the longest path, any field can only be a single distance away from the end of that path in which it participates. We discard all shorter paths. So if we have multiple equally longest paths, we still only have a single distance L(F). However, my pseudo-code does assume that there's only a single next square. This is sufficient to solve the problem since the next square is also chosen with respect to slope, but you are right that we'd probably need a collection of next fields if it must be possible to reconstruct all valid solutions. – amon Jan 4 '16 at 15:51
  • 2
    But the slop is defined by the first and last square, its a property of the path, not the node or a single step – Ewan Jan 5 '16 at 9:12
5

A dynamic programming approach should work.

For each cell:

  • Reduce the problem of finding the best (longest, steepest slope) descending path from there to the problem of finding the best path from each of its neighbors that is smaller and then adding the step to that neighbor to get the best path from the cell in question.

  • Memo(r)ize the best path from each cell along the way.

  • Don't actually save an explicit path, only save the next cell on the path (that way the path is there, just implicitly).

That should run in time linear to the size of the matrix if you do it correctly... unless I'm misunderstanding the problem of course.

Code might look something like:

public class BestDynamicDescendingPathFinder {
    public static int[][] example = new int[][]{{4, 8, 7, 3},{2, 5, 9, 3},{6, 3, 2, 5},{4, 4, 1, 6}};

    public static void main(String[] args)
    {
        BestDynamicDescendingPathFinder finder = new BestDynamicDescendingPathFinder(example);
        System.out.println("Best overall: " + Arrays.toString(finder.find()));
        System.out.println("Best starting from some other cell: " + Arrays.toString(finder.unfoldBestPathFromCell(3, 3)));
    }

    private int[][] matrix;
    private PathInformation[][] informationForBestPathFromCellMemory;

    public BestDynamicDescendingPathFinder(int[][] aMatrix)
    {
        informationForBestPathFromCellMemory = new PathInformation[aMatrix.length][];
        matrix = new int[aMatrix.length][];

        for(int i = 0; i < aMatrix.length; i++)
        {
            informationForBestPathFromCellMemory[i] = new PathInformation[aMatrix[i].length];
            matrix[i] = new int[aMatrix[i].length];

            for(int j = 0; j < aMatrix[i].length; j++)
            {
                matrix[i][j] = aMatrix[i][j];
            }
        }
    }

    // find the best path by getting the best starting cell and unfolding the information for it
    public int[] find()
    {
        int currentBestStartingCellColumn = 0;
        int currentBestStartingCellRow = 0;
        for(int i = 0; i < matrix.length; i++)
        {
            for(int j = 0; j < matrix[i].length; j++)
            {
               if(getInformationForBestPathFromCell(i, j).compareTo(getInformationForBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow)) == 1){
                   currentBestStartingCellColumn = i;
                   currentBestStartingCellRow = j;
               }
            }
        }

        return unfoldBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow);
    }

    // unfold the best path (starting) from a cell by walking the PathInformation structures in memory
    private int[] unfoldBestPathFromCell(int colNum, int rowNum)
    {
        PathInformation currentCellInformation = getInformationForBestPathFromCell(colNum, rowNum);
        int[] path = new int[currentCellInformation.length];
        path[0] = matrix[colNum][rowNum];
        int idx = 1;

        while(currentCellInformation.length > 1)
        {
            path[idx] = matrix[currentCellInformation.nextCellColumn][currentCellInformation.nextCellRow];
            idx++;
            currentCellInformation = getInformationForBestPathFromCell(currentCellInformation.nextCellColumn, currentCellInformation.nextCellRow);
        }

        return path;
    }

    // get the information for the best path (starting) from a cell: from memory if available or calculate otherwise
    private PathInformation getInformationForBestPathFromCell(int colNum, int rowNum)
    {
        if(informationForBestPathFromCellMemory[colNum][rowNum] == null)
        {
            informationForBestPathFromCellMemory[colNum][rowNum] = calculateInformationForBestPathFromCell(colNum, rowNum);
        }
        return informationForBestPathFromCellMemory[colNum][rowNum];
    }

    // calculate the information for the best path (starting) from a cell by using the information for best paths from neighboring cells
    private PathInformation calculateInformationForBestPathFromCell(int colNum, int rowNum)
    {
        List<PathInformation> possiblePathsFromCell = new ArrayList<PathInformation>();
        if(colNum != 0 && matrix[colNum - 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum - 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum - 1, rowNum));
        }

        if(colNum != matrix.length - 1 && matrix[colNum + 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum + 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum + 1, rowNum));
        }

        if(rowNum != 0 && matrix[colNum][rowNum - 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum - 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum - 1));
        }

        if(rowNum != matrix[colNum].length -1 && matrix[colNum][rowNum + 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum + 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum + 1));
        }

        if(possiblePathsFromCell.isEmpty())
        {
            return new PathInformation(1, matrix[colNum][rowNum], matrix[colNum][rowNum], -1, -1);   
        }

        return Collections.max(possiblePathsFromCell);
    }
}

public class PathInformation implements Comparable<PathInformation>
{
    int length;
    int startValue;
    int endValue; 
    int nextCellColumn;
    int nextCellRow;

    public PathInformation(int length, int startValue, int endValue, int nextCellColumn, int nextCellRow) 
    {
        this.length = length;
        this.startValue = startValue;
        this.endValue = endValue;
        this.nextCellColumn = nextCellColumn;
        this.nextCellRow = nextCellRow;
    }

    @Override
    public int compareTo(PathInformation other) {
        if(this.length < other.length || (this.length == other.length && this.startValue - this.endValue < other.startValue - other.endValue)){
            return -1;
        }
        if(this.length > other.length || (this.length == other.length && this.startValue - this.endValue > other.startValue - other.endValue)){
            return 1;
        }
        return 0;
    }
}
  • 2
    This is a good answer. Just a quick note for the future, posting code is technically ok in a question or answer, but we do prefer to use pseudo code where possible. It could be confusing to new users that may think this site is for help with code and debugging. – maple_shaft Jan 4 '16 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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