The Longest Increasing Sequence in a Two-Dimensional Grid of Numbers

[frankfjf]

Homework Statement

"Write a recursive Java program that finds the longest increasing sequence in a two-dimensional grid of numbers. A sequence is simply a series of adjacent squares. Squares may not be used twice. A grid might have multiple longest sequences. If an input grid does have multiple longest subsequences, your program should display only one such subsequence."

Homework Equations

Example: In the following grid:

97 47 56 36 60 31 57 54 12 55
35 57 41 13 82 80 71 93 31 62
89 36 98 75 91 46 95 53 37 99
25 45 26 17 15 82 80 73 96 17
75 22 63 96 96 36 64 31 99 86
12 80 42 74 54 14 93 17 14 55
14 15 20 71 34 50 22 60 32 41
90 69 44 52 54 73 20 12 55 52
39 33 25 31 76 45 44 84 90 52
94 35 55 24 41 63 87 93 79 24

the longest increasing sequence has length 10, consisting of entries (r,c) (row and column, starting at zero) as follows:

(5,0) with value 12
(6,0) with value 14
(6,1) with value 15
(6,2) with value 20
(7,2) with value 44
(7,3) with value 52
(7,4) with value 54
(6,3) with value 71
(5,3) with value 74
(4,3) with value 96

The Attempt at a Solution

Here is my program thus far, hopefully not too messy:

public class gridRunner
{
	public static int testGrid[][] = {{97, 47, 56, 36, 60, 31, 57, 54, 12, 55}, {35, 57, 41, 13, 82, 80, 71, 93, 31, 62},
								  				 {89, 36, 98, 75, 91, 46, 95, 53, 37, 99}, {25, 45, 26, 17, 15, 82, 80, 73, 96, 17},
								  				 {75, 22, 63, 96, 96, 36, 64, 31, 99, 86}, {12, 80, 42, 74, 54, 14, 93, 17, 14, 55},
								  				 {14, 15, 20, 71, 34, 50, 22, 60, 32, 41}, {90, 69, 44, 52, 54, 73, 20, 12, 55, 52},
								  				 {39, 33, 25, 31, 76, 45, 44, 84, 90, 52}, {94, 35, 55, 24, 41, 63, 87, 93, 79, 24}};
								  
	public static void main(String[] args)
	{
		System.out.println(getMaxPath(1, 5, 0));
	}
	
	public static String getMaxPath(int startL, int r, int c)
	{
		String maxPath = "\n(" + r + "," + c + ") with value " + testGrid[r][c];
		int length = startL;
		
		if (checkBounds(r - 1, c)) //check North
			{
				if (testGrid[r][c] < testGrid[r - 1][c])
				{
					length++;
					return maxPath += getMaxPath(length, r - 1, c);
				}
			}
			
		if (checkBounds(r - 1, c + 1)) //check Northeast
		{
			if (testGrid[r][c] < testGrid[r - 1][c + 1])
			{
				length++;
				return maxPath += getMaxPath(length, r - 1, c + 1);
			}
		}
		
		if (checkBounds(r, c + 1)) //check East
		{
			if (testGrid[r][c] < testGrid[r][c + 1])
			{
				length++;
				return maxPath += getMaxPath(length, r, c + 1);
			}
		}
		
		if (checkBounds(r + 1, c + 1)) //check Southeast
		{
			if (testGrid[r][c] < testGrid[r + 1][c + 1])
			{
				length++;
				return maxPath += getMaxPath(length, r + 1, c + 1);
			}
		}
		
		if (checkBounds(r + 1, c)) //check South
		{
			if (testGrid[r][c] < testGrid[r + 1][c])
			{
				length++;
				return maxPath += getMaxPath(length, r + 1, c);
			}
		}
		
		if (checkBounds(r + 1, c - 1)) //check Southwest
		{
			if (testGrid[r][c] < testGrid[r + 1][c - 1])
			{
				length++;
				return maxPath += getMaxPath(length, r + 1, c - 1);
			}
		}
		
		if (checkBounds(r, c - 1)) //check West
		{
			if (testGrid[r][c] < testGrid[r][c - 1])
			{
				length++;
				return maxPath += getMaxPath(length, r, c - 1);
			}
		}
		
		if (checkBounds(r - 1, c - 1)) //check Northwest
		{
			if (testGrid[r][c] < testGrid[r - 1][c - 1])
			{
				length++;
				return maxPath += getMaxPath(length, r - 1, c - 1);
			}
		}
		
		return maxPath + "\nGreatest path is of length " + length + ".";
	}
	
	public static boolean checkBounds(int r, int c)
	{
		if ((r >= 0 && r <= 9) && (c >= 0 && c <= 9))
			return true;
			
		return false;
	}
}

However, this does not produce the result obtained in the example. What can I do to cause my recursive method to find the longest path correctly that I am currently not doing in the code? Also, should the starting coordinates matter?

 

[MisterX]

[retracted]

getMaxPath should return the length of the maximum length path with increasing numbers starting with location r, c. But you are supposed to get the longest path starting anywhere.

To get the maximum length path of increasing numbers in the grid, you have a call to getMaxPath(L, r, c) for every r,c combination in the grid.

Although I don't think this is the most efficient method. If you found the longest path from a square, would a square further on in that path have a longer path that started with it? The program could also look for a decreasing path as well to form a complete increasing path.

 

[frankfjf]

Well, how can it visit the same square twice if it's already checking if the square it wishes to jump to is greater than the one it is currently on?

 

[MisterX]

Oops, I guess I made a mistake with regards to that.

 

[frankfjf]

Also, I understand about checking all starting positions and streamlining and so forth, but for the moment I'd like to test using the starting position of the posted solution. I can always modify the code to check all possible starting positions later. All it does for me as-written is give a path of length 3, not the largest path. It starts at 12, goes north to 75, goes southeast to 80, then stops there.

 

[L2E]

The problem with your code is that it checks to see if there is a number that it can jump to, then it jumps there. When it does the first jump to the next square it can't continue to check the other surrounding squares.

Your function should eliminate the impossible moves, then call itself for EVERY possible move and keep a count.

once you have that working you could add memorisation so that it doesn't have to start the check again from every square and also like someone mentioned before in a less simple way, If a square can be jumped to by any other square, then the longest path does not start on that square.

 

[frankfjf]

I understand the proposed fix in theory but am a little uncertain as to how to implement it codewise.

 

[ideasrule]

I think it's necessary to rewrite your code a bit. Right now, you make the code print out the result at the deepest layer of recursion. However, since you need to change the code per L2E's suggestion, the deepest layer has no way of knowing what the final answer is, so the code needs to print out at the shallowest layer. Another problem is that your code doesn't check whether it has already visited a cell or not. There should be an array to keep track of this, or else the code will go into an infinite recursion.

In order to implement induction, there needs to be an induction rule and a base case. The idea of the induction rule is that if I can make someone else tell me what the maximum path is starting from all of the neighbors of a cell, I can just choose the maximum result, add 1 to it, and return the answer. That "someone else" is just your own function, called with different arguments. The base case is what happens at the deepest layer of recursion, when there are no more neighbors that haven't been visited. In this case, I think the logical base case return value should be 0, since the maximum path is 0.

 

[frankfjf]

But due to the code as-is checking if a potential move would result in hopping to a number that is greater than the one at the current position, the program does not wind up visiting the same cell twice, nor does infinite recursion take place as-is. My problem remains how to change it to go with L2E's suggestion. I'm stumped on this point.

 

[frankfjf]

Well, after quite a bit of trial-and-error and brainstorming, I've solved the assignment more or less on my own, though I did get a friend's advice on one or two finer points. Thanks to everyone who helped me along on here.