algorithm - Finding snake sequence in XY graph - Java

Question

I am working on a problem to try to find what is called a Snake Sequence in a typical XY graph (aka grid). A Snake sequence is defined as a sequence of numbers where each new number, which can only be located to the right or down of the current number, is either plus or minus one. For example, if you are in the center of the graph, you can either move right (if that number is + or - 1) or move down (if that number is + or - 1). The goal of the problem is to find the longest path (aka Snake Sequence) through the graph (keeping in mind you can only chart a path to a new cell whose value is +- 1 with the current cell).

So, for the following XY graph, the longest snake sequence is: 9, 8, 7, 6, 5, 6, 7

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

Below is my code, which does not seem to work.

Question: How would you solve this problem above? (I offer my code showing what I have thus far, but it does not work)

import java.util.ArrayList;

public class SnakeSequence {
  private final int maxX = 3;
  private final int maxY = 3;
  private final int[][] board = new int[][]{
      {1, 2, 3, 4},
      {2, 1, -1, 5},
      {3, 0, -1, 6},
      {6, 2, 1, 7}
  };

  private ArrayList<Integer> findSequence(int xPos,
      int yPos, ArrayList<Integer> currentPath) {
    currentPath.add(board[yPos][xPos]);

    ArrayList<Integer> pathRight = new ArrayList<Integer>(currentPath);
    ArrayList<Integer> pathDown = new ArrayList<Integer>(currentPath);

    if (xPos < maxX || yPos < maxY) {
      if (yPos < maxY && (board[yPos + 1][xPos] + 1 == board[yPos][xPos] ||
                          board[yPos + 1][xPos] - 1 == board[yPos][xPos])) {
        pathDown = findSequence(xPos, yPos + 1, currentPath);
      }
      if (xPos < maxX && (board[yPos][xPos + 1] + 1 == board[yPos][xPos] ||
                          board[yPos][xPos + 1] - 1 == board[yPos][xPos])) {
        pathRight = findSequence(xPos + 1, yPos, currentPath);
      }

      if (pathDown.size() > pathRight.size()) {
        return pathDown;
      } else {
        return pathRight;
      }
    }
    return currentPath;
  }

  private void getSequence() {
    ArrayList<Integer> currentPath = new ArrayList<Integer>();
    ArrayList<Integer> result;
    result = findSequence(0, 0, currentPath);

    for (int i = 0; i < result.size(); i++) {
      System.out.println(result.get(i));
    }
  }

  public static void main(String[] args) {
    SnakeSequence sequence = new SnakeSequence();
    sequence.getSequence();
  }
}

Answer 1

You can imagine your table as an oriented graph, then you problem is just to find the longest path.

Fortunatly for you, only moving down and right is allowed, so your graph is acyclic, so you can use algorithms like critical path method.

This is how your graph would look like:

However, you want to find longest path between any two cells. To do that, I would compute for each cell the longest path starting at that cell. It is simmilar to what you do, but you compute same thing more times. Consider this:

6 -> 5
|    |
v    v
7 -> 6

At both 5 and 7 you compute how long is the path from 6 at down right, and that is useless repeated computation. In worst case scenario, this could lead to exponential time consumption, while the problem can be resolved in linear time!

Moreover, there is no guarantee that the longest path will start at (0,0).

(one possible) Solution:

Compute longest path from each cell, starting from bottom-right to upper-left. At each cel.. remember how long the longest path from that cell is, and witch way from that cell the path leads. (I will measure path length by number of cells on it). So for example, for the only 8 in your grapth, we would remeber [length=8, direction=right].

Why so complicated? Because it is now extramly easy to compute longest path at a cell, if we know the longest path of the cells to the right and down. Example (I made up):

The correct data for 2 now would be [length=4, direction=down] because can't go from 2 to 4.

You can also keep globally longest path and it's start. After the computation is complete, just walk the longest path from that start through the direction and write the numbers, position or whatever you need.