**Assignment 6: Dynamic Programming** *Due Tue Nov 23 11:00 PM Pacific Time* [Back to Algorithms](http://cs.pomona.edu/classes/cs140/) # Learning Goals - Implement a solution to a dynamic programming problem. - Learn how to analyze and develop dynamic programming algorithms. # Grading This assignment will be graded as pass/no-pass by a TA. To pass the assignment, you must 1. Complete every question in the PDF and submit your answers to gradescope. 2. Complete the programming component and submit your answers to gradescope. 3. Schedule a time to meet with a TA (see section Important Dates for deadlines). 4. Walk the TA through your answers. 5. The TA will then either - mark your assignment as 100% on gradescope, or - inform you that you have some corrections to make. 6. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA. If you have concerns about the grading walk-through, you can meet with me after you've first met with a TA. # Walk-Through Guidelines - Walk-through should take no more than 20 minutes. You should be well prepared to walk a TA through your answers. - You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected--nobody is perfect. - We will use the Google Sheet found on Slack to schedule your walk-through. This helps TAs manage their time and balance the grading load. - You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through--this is best left to a mentor session. # Important Dates - You should start this assignment Nov 18 - Submit your work prior to end of day Nov 23 - You must meet with a TA for grading prior to end of day Nov 30 + **It is a good idea to complete the assignment as early as possible** + **You must book a time to meet with a TA** - You should complete corrections by end of day Dec 3 # Overview This assignment includes two parts: 1. Answer the [question in this PDF](resources/dynamic-programming.pdf). 2. Write a program for the problem described in section The Jump-It Problem (must be compatible with Python 3.8). You may work on this assignment alone or with a partner. Please send me a message on Slack if you want me to assign you to work with a random partner. Whether you work alone or with a partner, only one partner will submit both parts to [gradescope](https://www.gradescope.com/). Three key points for the hand written part: 1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with Edge (Windows) or Preview (OSX) (using the correct format and spacing will help us grade), 2. ensure that the uploading partner adds the other partners after submission, and 3. **if you have any questions please ask them on [Slack](https://divisionii.slack.com/archives/G019H3HEXBK)**. # Example Execution I always like to start by showing you the end result. If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/370816 **You can copy and past from the above animation!** # The Jump-It Problem In this assignment you will be implementing a dynamic programming solution to the **Two-Dimensional Jump-It Problem** (2D-JI). The 2D-JI problem is a board game optimization problem. Your program will output the optimal (minimal) cost of moving from the top-left cell to the bottom-right cell. ## Moves In the 2D-JI you are given a game board with $m$ rows and $n$ columns. You start at the top-left **entry** cell and you want to reach the bottom-right **exit** cell with a minimal cost. You are allowed to make the following moves: 1. one cell right, 2. one cell down, 3. two cells right (jump over the cell to the right), or 4. two cells down (jump over the cell below). These moves assume that the cell you are moving into exists. For example, if you are in the second-to-last row you cannot perform move four (two cells down). Specifically, if you are in cell (1,1) (base index of 0) you can perform the following moves:  Below are three possible paths and costs for the above game board:  To solve this problem, you will be writing code for a **dynamic programming** algorithm. Essentially, you will be filling in a table of costs, where each cell in the costs table denotes the minimum cost of getting to the **exit** cell (bottom-right cell) from the current cell. For example, the cost table for the above game board looks like this:  In the above table, you can see that it *costs* 3 to get to the exit cell from the exit cell. You can also see that it *costs* 11 to get to the exit cell from the cell above the exit cell, and that it **optimally** *costs* 18 to get to the exit cell from the entry cell. ## The input file Your programs will start by reading in the contents of a file, the name of which will be provided via a program argument (e.g., from the command line). The file will include all of the information needed to create a two-dimensional Jump-It game board: ~~~text m n c11 c12 c13 ... c1n c21 c22 c23 ... c2n ... cm1 cm2 cm3 ... cmn ~~~ Where the first line gives values for $m$ and $n$, which are the number the number of rows and the number of columns, respectively. Each line after the first provides $n$ **integers** for all of the values of a given row. Here is an example input file for the game boards shown above: ~~~text 4 5 5 7 2 4 8 1 6 8 1 3 9 1 6 5 8 4 1 7 9 3 ~~~ [And here are all of the test files.](resources/tests.zip) ## Your program Your source file should be named `jumpit2d.py`. You will be implementing a dynamic programming solution the the 2D-JI. The 2D-JI problem is tricky because it has many edge cases to consider when developing the solution. You must account for the bounds of the cost table (you don't want to go beyond the end of the table when moving or jumping). Specifically, you have 9 cases to handle when filling in the cost table: 1. If you are at the exit cell, then you cannot move. 2. If you are 1 cell to the left of the exit cell, then your only choice is to move right (into the exit cell). 3. If you are 1 cell above the exit cell, then your only choice is to move down (into the exit cell). 4. If you are 1 cell above and 1 cell to the left of the exit cell (the diagonal cell), then you have two choice: (a) go down and then right or (b) go right and then down. 5. If you are in the last row (and not at the exit cell or the cell to the left of the exit cell) then you need to consider two choices: (a) go right or (b) jump right. You should fill in these values starting at the cell 2 to the left of the exit cell, working your way to the first cell in the last row. 6. If you are in the last column (and not at the exit cell or the cell above the exit cell) then you need to consider two choices: (a) go down or (b) jump down. You should fill these values in starting at the cell 2 above the exit cell, working your way to the first cell in the last column. 7. If you are in the second-to-last row (and not at the diagonal cell or the last cell in the row), then you need to consider three choices: (a) go down, (b) go right, or (c) jump right. 8. If you are in the second-to-last column (and not at the diagonal cell or the last cell in the column), then you need to consider three choices: (a) go right, (b) go down, or (c) jump down. 9. Finally, for all other cells you must consider four cases: (a) go right, (b) jump right, (c) go down, or (d) jump down. In all cases, you should take the value of the **board** at the current cell and add it to the minimum value for all choices in the **cost** table. As you can see, we are filling in the cost table starting at the exit cell (bottom-right) and moving our way up to the entry cell (top-left). I'd encourage you to work through these 9 cases individually. Once you have done that, you should think of some ways to reduce all of these cases into a single double-nested for-loop (*hint: you can add "padding" around the table with certain values that eliminate the need for handling all of these cases separately*). **Once you have the final table, you must print the value in the entry cell of the cost table.** I'd encourage you to first try implementing this program from scratch. But I am also providing [this skeleton code](resources/jumpit2d-9cases-skeleton.py) to help you get started if you are stuck. # Submitting Your Assignment You will submit your PDF assignment on [gradescope](https://gradescope.com/). **Only one partner should submit your PDF.** The submitter will add the other partner through the gradescope interface. You will also submit your code to gradescope. You will submit your Python file to gradescope. **Only one partner should submit your code.** The submitter will add the other partner through the gradescope interface. Please add your names in comments at the top of the file. To pass the autograder, your output must exactly match the expected output. You can use [text-compare](https://text-compare.com/) to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do). I've enabled a leaderboard for the assignment. You do not need to worry about it affecting your grade. I just thought it looked like a cute feature. Feel free to give yourself (your group) any name you'd like for the leaderboard. Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Scanning Work on a Mobile Device](https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)