Data Abstraction and Problem Solving with Java

USING Janet J. Prichard & Frank M. Carrano, Data Abstraction and Problem Solving with Java, 3nd Edition, Addison Wesley, 2010 (paperback), ISBN-10: 0132122308 , ISBN-13: 9780132122306

Create a program that will read the data for a two-dimensional integer array from a file. Using this array, your program is to determine the longest increasing path within the array starting from an arbitrary starting point that is, the longest path can start from any element within the array. Additionally, your program will find the longest incrementally increasing path within the array starting from an arbitrary starting point. In the event that two longest paths exist (both the same length), the path with the highest total value of elements will be selected.

An increasing path is one in which the subsequent value in the path is always larger than its predecessor (example 2 4 5 8 12 20). An incrementally increasing path is one in which the subsequent value in the path is exactly one larger than its predecessor (example 3 4 5 6). For both, only moves up, down, left and right are permitted.

Several test data files are provided to help you test your program. Sample output for the first two files are shown below. Format your output to match these samples.

Enter name of problem file: testData1.txt

[ 3, 4, 5 ]

[ 9, 6, 7 ]

[ 2, 1, 8 ]

The longest increasing path with maximum total is: 3-4-6-7-8

The length of this path is 5 and the total of the values is 28.

The longest incrementally increasing path with maximum total is: 6-7-8

The length of this path is 3 and the total of the values is 21.

............

Enter name of problem file: testData2.txt

[ 7, -1, 7, 3, -5, -6, -4, 3 ]

[ 0, 0, 8, 7, -6, 10, -5, 6 ]

[ -2, 2, 3, 8, -2, 2, 6, 2 ]

[ 5, 6, 1, 0, 2, -5, 1, 7 ]

[ 8, -1, 2, -8, -5, 7, -3, 10 ]

The longest increasing path with maximum total is: (-1)-0-2-3-8

The length of this path is 5 and the total of the values is 12.

The longest incrementally increasing path with maximum total is: 0-1-2

The length of this path is 3 and the total of the values is 3.

For each path, you will provide the following information:

a) The length of the path in terms of elements.

b) The total value of the path.

c) The description of the path shown as the values separated by hyphens.(Show negative numbers in parenthesis).

You should observe the following fact: the longest path with the highest value from any element in a given path is in fact the longest path from that element whether it is the starting point of the path or an element in another path. Consider the solution to testData1 above: 3-4-6-7-8. The longest path from 3 starts at 3 and includes the longest path starting at 4. The longest path from 4 starts at 4 and includes the longest path from 6. There are clearly redundancies here. To find the longest path for 3, you must first find the longest path from 4. To improve efficiency, you should save the solution of all the subproblems so that you do not need to recalculate them again when encountered a second (or further) time. If you started by calculating the longest path from 4 and you saved it, you could save your program from calculating the answer again when it calculates the longest path from 3. When moving from 3 to 4, you would detect that you already have the solution for 4 and use that solution. This would be your base case. This works because the ordering of the values (lowest to highest) prevents looping.

The solution to the longest path starting at 4 is one sub-problem; the longest path starting at 3 is another. To promote good software engineering, you should use an object to hold the solution to each sub-problem. The object could contain: the length of the solution, the total of the elements, and a String describing the path.