PA4 - Busch Gardens Charlottesville

Before the pandemic, Busch Gardens was planning to build a new amusement park a little closer to Charlottesville. The time has finally come to begin planning for the new park, so they’ve asked for your help!

Busch Gardens wants to build the tallest roller coaster possible to draw people into the park. Charlottesville and the Blue Ridge Mountains are notoriously hilly, so the company would like to make the best use of the terrain as possible. Given a 2D representation of the terrain under consideration, your task is to determine the longest possible slope–the longest downward path that could be used for the roller coaster’s main drop.

More specifically, The land will be represented by topographical map, which is a two-dimensional grid of elevations. The grid will have \(r\) rows and \(c\) columns. Each grid location~– or grid cell~– will have an integer height elevation.

Your task is to figure out the longest sequence of grid locations from a high elevation to a low elevation. The top of the coaster’s main drop will start at a higher elevation and proceed down to a lower elevation to the bottom of the main drop. For the purposes of this problem, the coaster’s main drop path will never move from a given elevation to the {\em same} elevation, nor will it travel uphill. Furthermore, to prevent whiplash or injury to the riders, the coaster can only travel from one grid cell to an adjacent cell (adjacent cells are above, below, left, and right; not diagonal!).

As an example, consider the following 5x5 grid.

66 78 41  3 77
 4 90 41  8 68
12 11 29 24 53
 0 51 58  9 28
97 99 96 58 92

There are many such valid coaster paths in this grid. One starts in the second cell of the second row (1,1), and flows from 90-78-41-3. Note that 90-41-41-3 is not a valid coaster main drop path, as the track is not always flowing downhill (41-41 is not downhill). The longest main drop path in this example is of length 7, and flows from the 99 in the bottom row at position (4,1) to the 3 in the top row at position (0,3); the full path is 99-96-58-29-24-8-3.

You must solve this problem using top-down Dynamic Programming or using bottom-up Dynamic Programming; a brute-force solution’s running time will be too long.

Input

For this assignment, you are provided scaffolding code that reads in the file named terrain.txt, containing a 2D grid of integers not greater than \(2000 \times 2000\) cells. Each integer in that grid will be a height ranging from 0 to 100. It then passes the 2D grid to the RollerCoaster class, which you will implement, to find the longest downhill slope. Finally, it prints out the length of that slope and the ordered terrain values in the slope from highest to lowest elevation.

You must implement the compute() method that accepts the 2D list of elevations and returns the length of the longest downhill slope. Your method must also use backtracking to store the roller coaster’s path as an ordered list of elevations (from highest to lowest elevation) and the starting point for the coaster’s drop as instance variables to be returned by the getCoasterPath() and getCoasterStart() getter methods that you must also implement. The first method should return an array of integers; the second should return an array with the first element defining the row and the second defining the column of the path.

Examples

For each of the examples below, we’ll provide 2D terrain input and an example correct coaster path (there may be multiple!).

terrain1.txt

Terrain

66 78 41  3 77
 4 90 41  8 68
12 11 29 24 53
 0 51 58  9 28
97 99 96 58 92

Example Output

length:    7
terrains:  [99, 96, 58, 29, 24, 8, 3]
start pos: [4, 1]
time:      0.0001518726348876953

terrain2.txt

Terrain

82 90 81 42 84 30 97 9 40 66 41 75 76 56 33 4 76 94 56 36
55 77 79 15 95 48 7 40 42 40 50 100 62 28 30 44 26 62 43 55
18 0 76 12 40 21 43 96 87 48 80 20 51 14 31 11 68 6 95 83
89 40 45 95 29 36 95 58 80 36 26 99 41 58 51 80 95 59 98 72
72 10 19 31 85 10 61 96 51 23 99 40 33 74 2 81 57 20 77 4
45 58 18 58 30 79 34 22 68 87 10 92 100 2 51 54 49 37 42 88
43 99 33 41 74 61 68 68 22 68 89 3 100 79 92 33 47 44 18 33
46 85 47 14 47 13 1 56 6 59 39 40 1 71 71 53 88 48 77 37
58 58 58 76 55 74 78 56 39 25 67 16 100 66 91 25 16 82 95 59
52 97 63 30 81 70 89 49 86 42 62 28 67 78 57 68 9 69 7 87
1 11 58 55 31 10 33 9 50 1 36 54 28 14 56 64 98 12 70 27
25 30 25 67 20 1 96 44 65 36 52 57 99 54 53 74 30 59 90 8
44 42 3 49 46 4 36 40 50 70 29 65 57 54 43 84 83 86 55 38
88 63 70 50 55 66 34 28 95 59 14 74 36 27 50 59 93 89 43 3
92 63 76 9 95 69 61 53 64 12 62 57 98 22 59 43 73 12 95 65
69 52 24 79 52 18 23 26 94 68 21 49 74 11 21 24 89 97 39 52
9 62 57 18 17 62 18 59 70 83 93 80 57 95 24 41 68 79 40 8
38 56 65 2 56 51 46 31 1 93 69 90 55 91 39 53 2 66 91 61
48 1 38 94 41 51 38 26 89 67 72 68 66 29 39 15 8 18 80 74
36 59 51 78 55 38 2 9 17 5 43 63 16 23 92 5 16 41 36 32

Example Output

length:    9
terrains:  [95, 69, 66, 55, 50, 49, 46, 4, 1]
start pos: [14, 4]
time:      0.0017747879028320312

Implementation

Your program should have the following properties:

• Your algorithm must be written in Python 3.10.6 or Java 19.0.2 (OpenJDK)
• You must download the appropriate wrapper code based on the language you choose: Main.py and RollerCoaster.py for Python, Main.java and RollerCoaster.java for Java.
  • Java package: pa4-java.zip
  • Python package: pa4-python.zip
• Implement the compute(), getCoasterPath(), and getCoasterStart() methods in the RollerCoaster class. The compute() method should execute the entirety of your algorithm (or call a helper function if you are writing a top-down algorithm) and store the path information as instance variables; getCoasterPath() and getCoasterStart() should return the resulting values without additional computation (i.e. it should be a “getter”).
• Two test terrains are provided. You should produce additional tests, including edge cases.
• You may modify the Main files to test your algorithm, but they will not be used during grading.
• You must submit your RollerCoaster file to Gradescope. Do not submit Main.java, Main.py, or any test files.
• You may submit your code a maximum of 15 times to Gradescope. After the 15th submission, Gradescope will not run your code.
• A few other notes:
  • Your code will be run as:
    python3 Main.py for Python, or javac *.java && java Main for Java.
  • You may upload multiple files if you need additional classes for Java, but do not assign packages to the files.
  • You may use any editor or IDE you prefer as long as the code can be executed as stated above.
  • We strongly encourage you to practice good development as you write code: use meaningful variable names, break your code into functions, “code a little then test a little”, use the debugger, etc.

Rules on Collaboration and Outside Sources

You may discuss the problem and the overall strategy with up to 4 other students, but you must list those people in your submission under collaborators. You may not share code, look at others’ code, or help others debug their code. You must write your own code. Not just type it (though you need to do that too): compose it yourself, as your own original work. Please read the syllabus carefully around coding. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite them. Do not submit a solution that you are unable to explain orally to a member of the course staff.

Use of Generative AI

For PA4, you are not allowed to use generative AI tools to help you solve this problem.