COP3503C Programming Assignment #7: Run Like Hell Solution

Abstract
In this assignment, you will practice the art of dynamic programming. I think you will find this problem to have approximately the same level of difficulty as Fibonacci and the 0-1 Knapsack problem. It lends itself to an elegant recursive solution – albeit an inefficient one – that can be translated directly into a fast DP solution that only requires (at most) a 1D array.
This will be excellent practice for the final exam, where you are almost certain to encounter a DP problem of similar difficulty.
Deliverables
RunLikeHell.java
Note! The capitalization and spelling of your filename matter!
Note! Code must be tested on Eustis, but submitted via Webcourses.

Enchanted, the algorithmist stopped to rest awhile.
As he gazed upon the lofty and unlikely fruits of the golden pear tree, thoughts of dynamic programming came unbidden to his mind. With surprising clarity, he recalled his studies of the topic, and his understanding began to crystallize in ways it never had before. The mysteries of optimal substructure unfurled before him like the wings of the birds below. He saw, in that moment, that the branches of an exponential recursive function were as the branches of the golden pear tree, tangled and unruly; that memoized results were as overripe, falling pears splatting juicily against lower limbs; and that the bottom-up technique of dynamic programming was as the seeds of a fallen pear coming to sprout anew. In his mind, all these approaches became one: many paths from the same source, all leading to the same goal, like the roaring waterfalls whose waters all wended toward the golden pear tree at the heart of the vale. As his insight grew, the rivulets in the valley below began to swell, until they had become a single body of water that gently drowned the valley floor. And so the young algorithmist was awakened to the beauty of DP.
It was then that the algorithmist felt the ground rumble beneath him. At first, he took the tremor for the earth-moving awesomeness of dynamic programming (and perhaps it was), but the dangerous reality of the matter quickly set in: the cliff he was sitting on was starting to crumble!
The algorithmist sprang to action. His only chance for survival was to run as fast as possible to more stable ground before the rocky ledge disintegrated beneath his feet. As he ran toward safety, new crevices formed everywhere he stepped. The cracks were following him, spreading through the rocky ledge at an alarming rate. He needed to get off that cliff altogether. He needed to...
RUN LIKE HELL!
While the algorithmist is running for his life, he passes beneath a row of evenly-spaced “obscure knowledge blocks.”
Each block is clearly labeled with the amount of obscure knowledge the algorithmist will gain for jumping up and hitting it. However, given the speed at which he is running, the algorithmist is unable to hit them all. If he jumps to hit one block, he is unable to jump back up in time to hit the very next block in the sequence (see Figure 1).

Figure 1: Speed and trajectory prevent the algorithmist from hitting two consecutive blocks in the sequence.
The goal of the algorithmist is to maximize the amount of knowledge he gains as he flees the mountain. Notice that in some cases, it is advantageous for the algorithmist to skip more than one block in a row. For example, Figure 2 shows the sequence of jumps that will optimize the algorithmist’s knowledge gain for this particular sequence of blocks.

Figure 2: For the path shown in this figure, the algorithmist’s total knowledge gain is 15 + 17 + 20 = 52, which is the maximum knowledge gain possible for this particular sequence of blocks.
In this assignment, the values of these blocks, ordered from left to right, will be given to you as an array of positive integers. For example, the array corresponding to the blocks in Figures 1 and 2 is:
int [] blocks = { 15, 3, 6, 17, 2, 1, 20 }
Your goal is to write a DP algorithm that will determine the algorithmist’s maximum knowledge gain for any arbitrary sequence of blocks. (In the example above, the answer is 52.) For more examples, see the attached test cases, but please realize that those test cases are not comprehensive. You should also create some of your own.
Method and Class Requirements
Implement the following methods in a class named RunLikeHell. Please note that they are all public and static.
public static int maxGain(int [] blocks)
Given an array of positive integers containing the block values that the algorithmist will encounter (in order, from left to right), return the maximum knowledge the algorithmist can gain before making his way safely off the mountain. Recall that the algorithmist’s speed and trajectory prevent him from ever hitting two blocks that are right next to each other.
You must use an O(n) dynamic programming solution to receive credit. The space complexity must also be no worse than linear. I suggest starting with a top-down recursive algorithm and then transforming it into a bottomup DP approach using the technique taught in class.
public static double difficultyRating()
Return a double indicating how difficult you found this assignment on a scale of 1.0 (ridiculously easy) through 5.0 (insanely difficult).
public static double hoursSpent()
Return a realistic estimate (greater than zero) of the number of hours you spent on this assignment.
Style Restrictions (Same as in Program #1) (Super Important!)
Please conform as closely as possible to the style I use while coding in class. To encourage everyone to develop a commitment to writing consistent and readable code, the following restrictions will be strictly enforced:
 Capitalize the first letter of all class names. Use lowercase for the first letter of all method names.
 Any time you open a curly brace, that curly brace should start on a new line.
 Any time you open a new code block, indent all the code within that code block one level deeper than you were already indenting.  Be consistent with the amount of indentation you’re using, and be consistent in using either spaces or tabs for indentation throughout your source file. If you’re using spaces for indentation, please use at least two spaces for each new level of indentation, because trying to read code that uses just a single space for each level of indentation is downright painful.
 Please avoid block-style comments: /* comment */
 Instead, please use inline-style comments: // comment
 Always include a space after the “//” in your comments: “// comment” instead of “//comment”
 The header comments introducing your source file (including the comment(s) with your name, course number, semester, NID, and so on), should always be placed above your import statements.
 Use end-of-line comments sparingly. Comments longer than three words should always be placed above the lines of code to which they refer. Furthermore, such comments should be indented to properly align with the code to which they refer. For example, if line 16 of your code is indented with two tabs, and line 15 contains a comment referring to line 16, then line 15 should also be intended with two tabs.
 Please do not write excessively long lines of code. Lines must be no longer than 100 characters wide.  Avoid excessive consecutive blank lines. In general, you should never have more than one or two consecutive blank lines.  Please leave a space on both sides of any binary operators you use in your code (i.e., operators that take two operands). For example, use (a + b) - c instead of (a+b)-c. (The only place you do not have to follow this restriction is within the square brackets used to access an array index, as in: array[i+j].)
 When defining or calling a method, do not leave a space before its opening parenthesis. For example: use System.out.println("Hi!") instead of System.out.println ("Hi!").
 Do leave a space before the opening parenthesis in an if statement or a loop. For example, use use for (i = 0; i < n; i++) instead of for(i = 0; i < n; i++), and use if (condition) instead of if(condition) or if( condition ).
 Use meaningful variable names that convey the purpose of your variables. (The exceptions here are when using variables like i, j, and k for looping variables or m and n for the sizes of some inputs.)  Do not use var to declare variables.
Compiling and Testing on Eustis (and the test-all.sh Script!)
Recall that your code must compile, run, and produce precisely the correct output on Eustis in order to receive full credit. Here’s how to make that happen:
1. To compile your program with one of my test cases:
javac RunLikeHell.java TestCase01.java
2. To run this test case and redirect your output to a text file:
java TestCase01 > myoutput01.txt
3. To compare your program’s output against the sample output file I’ve provided for this test case:
diff myoutput01.txt sample_output/TestCase01-output.txt
If the contents of myoutput01.txt and TestCase01-output.txt are exactly the same, diff won’t print anything to the screen. It will just look like this:
seansz@eustis:~$ diff myoutput01.txt sample_output/TestCase01-output.txt seansz@eustis:~$ _
Otherwise, if the files differ, diff will spit out some information about the lines that aren’t the same.
4. I’ve also included a script, test-all.sh, that will compile and run all test cases for you. You can run it on Eustis by placing it in a directory with RunLikeHell.java and all the test case files and typing:
bash test-all.sh
Super Important: Using the test-all.sh script to test your code on Eustis is the safest, most sure-fire way to make sure your code is working properly before submitting.
Grading Criteria and Miscellaneous Requirements
Important Note: When grading your programs, we will use different test cases from the ones we’ve released with this assignment, to ensure that no one can game the system and earn credit by simply hard-coding the expected output for the test cases we’ve released to you. You should create additional test cases of your own in order to thoroughly test your code. In creating your own test cases, you should always ask yourself, “What kinds of inputs could be passed to this program that don’t violate any of the input specifications, but which haven’t already been covered in the test cases included with the assignment?”
The tentative scoring breakdown (not set in stone) for this programming assignment is:
100% Passes test cases using an O(n) dynamic programming solution.
All the policies stated in the previous programming assignment specifications still apply:
Important! Programs that do not compile on Eustis will receive zero credit. When testing your code, you should ensure that you place RunLikeHell.java alone in a directory with the test case files (source files, the sample_output directory, and the test-all.sh script), and no other files. That will help ensure that your RunLikeHell.java is not relying on external support classes that you’ve written in separate .java files but won’t be including with your program submission.
Important! You might want to remove main() and then double check that your program compiles without it before submitting. Including a main() method can cause compilation issues if it includes references to home-brewed classes that you are not submitting with the assignment. Please remove.
Important! Your program should not print anything to the screen. Extraneous output is disruptive to the grading process and will result in severe point deductions. Please do not print to the screen.
Important! No file I/O. Please do not read or write to any files from RunLikeHell.java.
Important! Please do not create a java package. Articulating a package in your source code could prevent it from compiling with our test cases, resulting in severe point deductions.
Input specifications are a contract. We promise that we will work within the confines of the problem statement when creating the test cases that we’ll use for grading. Please reflect carefully on the kinds of edge cases that might cause unusual behaviors for any of the methods you’re implementing.
Start early! Work hard! Ask questions! Good luck!