Homework 5: Dynamic Programming

--- tags: hw, spr22 --- # Homework 5: Dynamic Programming ### Due Date: Friday, April 15, 2022 at 11:59pm EST ## Learning Objectives * Use dynamic programming to reduce the running time of a program * Use concrete examples, invariants, hand tracing, and debugging to explore or explain how a program works * Comment code effectively * Develop a collection of examples and tests that exercise key behavioral requirements aspects of a problem * Write programs that behave as expected based on a provided description or collection of test cases ## Assignment Link Here is the [GitHub Classroom link](https://classroom.github.com/a/jEeC3Pvz) If you're having trouble with VSCode, check out our VSCode problems handout. Please make sure to read [our Gradescope submission guide](https://hackmd.io/oTbF1IUuRs27VgVJF4z2rA) before handing in your assignment! This [HW5 FAQ](https://edstem.org/us/courses/16807/discussion/1373957) post will be maintained on Ed. ## Style Expectations For all future assignments, including this one, we expect your code to conform to the [CS200 Python Style Guide](https://hackmd.io/@csci0200/rkeoOF22Y). If you know how to do something in Java but need help translating it into Python, then you can reference our [Going to Python from Java Guide](https://hackmd.io/@csci0200/S15mJUUM9). For more information on **testing** and **formatting tests** in Python, please see our [Python Testing Guide](https://hackmd.io/@csci0200/B1g1ZvvpF). ## Code Breaker ### Problem Description Your goal is to find the “difference” between two words, which we quantify as a number indicating the minimum number of edits required to transform one word into the other. There are three possible operations: inserting a letter, removing a letter, and substituting a letter. For example, consider the words “apple” and “opal”: apple -> opple (substituting 1st letter: a for o) opple -> opale (substituting 3rd letter: p for a) opale -> opal (deleting last letter) Here, the difference between the words would be 3, because it takes 3 operations to go from “apple” to “opal”! For the purposes of this problem, you should count uppercase and lowercase letters as the same letter. This means the difference between “opal” and “OPAL” should be 0. The difference between two words could be computed recursively, by looking at the number of edits needed to convert substrings from the two words. As discussed in class, one way to avoid doing the redundant computations that result from a recursive computation, we can instead use a two-dimensional array to store edit distances. **Task 1-a:** Come up with your own word pairs that would be good examples of the sorts of computations you might encounter for this problem. For example, one example is the pair of words "code" and "cods", because they only differ by one substitution. Try to come up with more examples that will help illustrate the problem, including pairs that differ by different combinations of multiple operations. **Task 1-b:** Now consider how you would compute the difference between those examples based on the difference between their substrings. For example, to compute the difference between "code" and "cods," it might help to first compute the difference between "code" and "ods", or "ode" and "ods", or something else. One way to represent this reasoning is by using a table: | | C | O | D | E | - | |---|---|---|---|---|---| | **C** | | | | | | | **O** | | | * | | | | **D** | | | | | o | | **S** | | | | | | | **-** | | | | x | | In this sort of table, you can write down the differences between iteratively smaller substrings of the two strings. For example, the cell with the \* should hold the difference between the substrings "de" and "ods". We use "-" to represent the empty substring, so the cell marked "o" should hold the difference between the substrings "" and "ds" and the cell marked "x" should hold the difference between the substrings "e" and "". :::info **Hints for coding:** What are the height and width of this table, as expressions in terms of the input strings? How would you write code to access the bottom-right corner of this table? How would you write code to loop through the rightmost column of this table, from bottom to top? What about the bottom row of the table, from right to left? This is a good exercise to try to code up before you even write the rest of your code! ::: Just by reasoning about it manually, fill out the table for "code" and "cods" based on the differences between the corresponding substrings for each cell. For example, in the cell with the \*, you should put 2, because the difference between "de" and "ods" is 2 (a substitution and an insertion). In the cell with the o, you should put 2, because the difference between "" and "ds" is 2 (2 insertions), and in the cell with the x, you should put 1, because the difference between "e" and "" is 1 deletion. :::spoiler Hints The value in the top-left cell should be 1. Why? For this particular pair of strings, there should only be one cell with value 0. Which one is it? ::: **Task 1-c:** Test your understanding by entering your table into [this spreadsheet](https://docs.google.com/spreadsheets/d/1ZXp4RBRcyGhe92NZ2EZYPRmbniNBs9gSbsPmz0JHmaU/edit?usp=sharing) (first, go to File > Make a Copy to duplicate the spreadsheet, then edit your copy). You should only have to edit the light red cells for this task. You will know you've gotten the correct values if **all** of the cells are white. If a cell is unfilled, it will be light red, and if it is wrong, it will be dark red. **Task 1-d:** Go through the rest of the examples you wrote down in Task 1-a and repeat tasks 1-b and 1-c to test your understanding of the problem. It will likely help to make a new copy of the spreadsheet for each task so that you can come back to your work. Take screenshots of at least 3 tables with your own examples. Put the screenshots in a document, and, for each pair of example words, give a sentence explaining why you chose this example. :::warning **Note:** Make sure that, after the cells that hold the letters for each word, there is a *single* cell with "-" at the end and the rest of the cells in the first row/column blank. Also ***please do not delete rows or columns,*** because this will invalidate our error-checking. If your spreadsheet does not have rows 1-30 and columns A-P, start over with a new copy of the spreadsheet. Finally, only work in the sheet called "practice," and do not make new sheets or rename this sheet. ::: In class, we discussed that the key idea of dynamic programming is to perform our computations by breaking them up into smaller problems (such as substrings instead of strings), to store the result of the smaller computation, and to leverage these stored results in doing the larger computation. This suggests that, programmatically, we can fill out a similar table in code by starting at the bottom-right cell and working our way up to the top-left cell. **Task 1-e:** In prose, describe the patterns you notice while doing task 1-d that would allow you to do this. Said differently, what is the computation that can be done to get the value for a cell, given the values in the cells below and to the right of it? Put this in the document with your screenshots. :::info **Example:** What we're looking for is something that reads like the following answer (the computation for the below answer is incorrect, so only pay attention to the phrasing). *For a given cell, if the letter corresponding to the column of the table is equal to the letter corresponding to the row of the table, we compute the value of the cell as (1 + [the value of the cell directly below it]). Otherwise, we compute the value of the cell to be the maximum of all of the cells in the row that are to the right of it.* ::: **Task 1-f:** What are the base case(s) you need to think about? One way to answer this question is to think about the times the computation you just described fails. Write down your answer in prose. Also put this in your document. :::info **Example:** Following along with the example in Task 1-e, we notice that we cannot perform the computation of "(1 + [the value of the cell directly below it])" if there are no cells below the current one. This indicates that we need to account for the case where we initialize the bottom row of the table to some values. This would lead to the (again, computationally incorrect) possible answer of *We should initialize the bottom row of the table to be all 0s.* **Hint:** it will help to look back at your examples here. What is similar across tables, no matter what examples you chose? ::: **Task 1-g:** Translate your prose from task 1-e into code. That is, assume you have set up your outer loop(s) correctly so that they work through your task from the bottom-right corner upwards and leftwards. What would go inside the body of these loop(s)? :::info **Example:** Following along with the example in Task 1-e, say we had a 2-d array called `similarity_array` and were trying to populate cell `similarity_array[row][col]`. Assuming we had already filled in `similarity_array[row_down][col_right]` for all `row_down` > `row` and all `col_right` > `col`, and assuming `str1` and `str2` were our input strings, we could write the expression ``` if str1[row] == str2[col]: similarity_array[row][col] = 1 + similarity_array[row + 1][col] else: similarity_array[row][col] = max(similarity_array[row][col+1:]) end ``` ::: ### The starter code We've provided you with a `codebreaker.py` file which defines the `CodeBreaker` class. This class consists of: * a constructor which takes in two parameters representing the "start" and "end" words of your codebreaker sequence. The constructor initializes `self.start_word` and `self.end_word` with these parameters, you are responsible for initalizing 2-dimensional`self.similarity_array` to store the distances between the suffixes of each word * a method `fill_similarities`, takes in no parameters and returns nothing. This should fill in the cells of `similarity_array` using dynamic programming. * This will include your code from task 1-g along with code that makes sure to loop through the array in the correct order. * You should call `fill_similarities` inside your class constructor in order to fill the `similarity_array` * **Note:** You do NOT need to write the plain recursive solution for this problem, but you are welcome to if it will help you understand the computation before you try to optimize it * a method `find_score`, which takes in no arguments and returns an integer representing the smallest difference between the two words input into the class. Because `fill_similarities` is called in the constructor, this method should simply use the completed `similarity_array` to return relevant value **Task 1-h**: Initialize your `self.similarity_array` and fill in the `find_score` and `fill_similarities` methods following the instructions above **Task 1-i**: As always, write your tests for this problem in `test_hw5`. You should test `fill_similarities` and `find_score`, and any helper functions you wrote. *Refer to our [Python testing guide](https://hackmd.io/cLCJRBbXTSyOyEoNQq4N-Q?both) for tips and tricks about writing tests!*  ## Seamcarve ### Problem Description Your goal is to resize (shrink) an image horizontally by removing "unimportant" pixels from the image. We can do this by finding vertical "seams" in the image representing the pixels that have the lowest difference in color from their neighbors and, thus, can be removed without significantly altering the image. More information on seamcarve can be found on the [Wikipedia page](https://en.wikipedia.org/wiki/Seam_carving) and in [this video](https://www.youtube.com/watch?v=c-SSu3tJ3ns). ![](https://i.imgur.com/9OuCLog.png) ![](https://i.imgur.com/6lKyzaq.png) ### Understanding The Algorithm To resize an image, the seamcarve algorithm completes two main steps: 1. Finding the importance value of each pixel in the image. * This is determined by how much each pixel varies from its neighbors. It can be calculated as the average of the differences between its value and the value of each of its horizontal and vertical neighbors. These values are stored in a 2D list called an importance array. **This code is given to you, in the** `ImportanceCalculator` **class, which is used by the `calculate_importance_values` method.** 2. Finding the seam of least importance in the image to be removed. * The *seam of least importance* is defined by these constraints: there is exactly one pixel from each row in the seam, the seam is "connected" (for any row, the seam pixel of that row must border, diagonally or vertically adjacently, the seam pixel above and below it), and the sum total of pixel importances for this seam is the lowest out of all of the possible seams. * This computation can be done using the data structures explained further below. These steps are repeated multiple times until the remaining image has decreased by the desired amount of width (assuming vertical seams are being removed). :::info See [Step 2-f (testing)](#Running-the-code) for an explanation of our interactive spreadsheet that shows these concepts in action. ::: ### Data Structures Used To Find a Seam To aid us with our task, it will be helpful to define three 2D arrays: `vals`, `costs`, and `dirs`. #### `vals` The `vals` array is given as our input. The stencil code computes this for you, and passes it in into the `find_least_important_seam` method. Each cell represents the importance value of the pixel corresponding to that position in the image. An example `vals` array is provided below. | vals| | | | --- | --- | --- | | `3 `| `6` | `8` | | `5` | `7` | `2` | | `4` | `9` | `3` | **Task 2-a:** Make your own small (3x3, 3x4, 4x3, or 4x4) vals table. As you work through the `costs` and `dirs` computations by hand, also work through the computations on your own table. You will be asked to provide these computations in the document you turn in. #### `costs` The `costs` array represents the minimum `cost`-- or difference in pixel values -- of a seam going through that cell in the image. Each cell of the `costs` array can be calculated using the following expression: ```python= costs[row][col] = min(costs[row+1][col-1], costs[row+1][col], costs[row+1][col+1]) + vals[row][col] ``` Intuitively, this looks at the minimum cost of the three pixels *below* the pixel in question, and adds that to the importance value of the pixel in question. If we do this computation starting with the bottom row going upwards, that means that, in the top row, we will find the pixel that starts the seam with the least *total* importance by finding the minimum value of `costs` in the top row. This is very similar to the trick-or-treating example done in class, except using a minimum instead of a maximum! :::info **Stop and think:** What should the base case(s) be for this expression? Think back to how we reasoned about the base case in Task 1-f, and think about what this computation is doing! ::: Using the `vals` array provided above, fill in its corresponding `costs` array. Remember to also do the same for the `vals` array you came up with! | costs | | | | --- | --- | --- | |`fill!`|`fill!`|`fill!`| |`fill!`|`fill!`|`fill!`| |`fill!`|`fill!`|`fill!`| :::spoiler Check your work | costs | | | | --- | --- | --- | |`12`|`11`|`13`| |`9`|`10`|`5`| |`4`|`9`|`3`| ::: At which pixel (0, 1, or 2) of the top row will our seam start? :::spoiler Check your work It will start at pixel 1, because that has the minimum `costs` value in the top row (11) ::: Figuring out which pixel to start with is called an "argmin" problem. `argmin` looks through an array and returns the index of the minimum element of the array. **Task 2-b:** Implement the `argmin` function in the starter code. Notice that, in the starter code, the `SeamCarve` class has a constructor that defines the following fields: ```python= self.image_array # the image array (3d array - 1st dim rows, 2nd dim cols, 3rd dim RBG pixel values) self.image_height # the number of rows in the image array (height dimension) self.image_width # the number of columns in the image array (width dimension) self.costs self.dirs ``` Also notice that the `find_least_important_seam` method takes in the `vals` array, and that you have a `check_bounds` helper function, should you need it. **Task 2-c:** Based on the above, begin to fill in the `find_least_important_seam` method with some code that: * Initializes the `costs` array to be of the correct size * Fills in the values for the base case(s) of the `costs` array * Fills in the rest of the `costs` array based on the formula above. #### `dirs` The `dirs` array represents the direction of the pixel below the current cell that the seam should continue in (either left, right, or straight). It can be calculated using the following: ``` min_cost = min(costs[row+1][col-1], costs[row+1][col], costs[row+1][col+1]) dirs[row][col] = -1 if min_cost is costs[row+1][col-1] 0 if min_cost is costs[row+1][col] +1 if min_cost is costs[row+1][col+1] ``` Intuitively, this tells us if the seam is going to the left (-1), straight down (0), or to the right (1), based on which pixel contributed the minimum value when we were computing the `costs` table. If we start at the lowest importance seam's topmost pixel (which we determined using costs), we can use `dirs` to trace down the seam.  With your `costs` array complete, fill in its corresponding `dirs` array. Also remember to do the same the example you came up with! | dirs | | | | --- | --- | --- | |`fill!`|`fill!`|`fill!`| |`fill!`|`fill!`|`fill!`| | `-` | `-` | `-` | :::info **Stop and think:** What is the reasonable thing to do at the edges? Why don't we need to fill out the bottom row? *Hint: think back to the goal of keeping the `dirs` array.* ::: :::spoiler Check your work | dirs | | | | --- | --- | --- | |`0`|`+1`|`0`| |`0`|`+1`|`0`| |`-`|`-`|`-`| ::: Which pixels will our example seam traverse, row-by-row? :::spoiler Check your work We said in the previous example that our seam will start at pixel 1 of the top row. Because the value of `dirs` at row 0, pixel 1 is `+1`, we move one pixel down and *right*, meaning that our seam will continue with pixel 2 of the next row. Because the value of `dirs` at row 1, pixel 2 is `0`, we move one pixel down and *straight,* meaning that our seam will end with pixel 2 of the last row. We can represent this seam as the list `[1, 2, 2]`. What does this traversal look like when we look at `costs`? | costs | | | | --- | --- | --- | |`12`|**!`11`!**|`13`| |`9`|`10`|**!`5`!**| |`4`|`9`|**!`3`!**| It shows us which pixels we went through, bottom to top, to get the lowest cumulative cost of 11! ::: **Task 2-d:** Based on this, continue to fill in `find_least_important_seam` with code that: * Initializes the `dirs` array to be of the correct size * Fills in the values for the `dirs` array :::warning **Think about where this computation belongs!!** Instead of running the entire computation to compute the `costs` table and then running the entire computation to compute the `dirs` table, might you be able to use some logic that they share to populate both at once? ::: **Task 2-e:** Complete the`find_least_important_seam` function by using your `costs` and `dirs` arrays to create a 1D list holding the indices for the seam of least importance. :::spoiler Reminder For our example, we said that this would have been [1, 2, 2] ::: ### Running the code Running your program will produce two images: the first will be a modification of your original image that has the seam(s) carved out, the second is the original image with a visual representation of the seam(s) that were carved. Running your code normally will automatically use the default image (`sample1.png`) provided in the `seamcarve_images` folder of the stencil code and will carve just 1 seam. You can also use your own custom image, or increase the number of seams carved! * ~~**Note:** We recommend first running your code with this default image and comparing the visual representation of your seam that is carved with the one we've provided in `seamcarve_images/demo1.png`~~ * The original demo image we provided is slightly off. For the first demo image, you can compare your image to the image below. **We want you to use the demo image in the handout, not the image from the stencil code. (Correction April 12th)** ![](https://i.imgur.com/Wy4Mw1g.png) To run your program with custom images/number of seams, you must provide that information as inputs to your main method. To do so, you should first navigate to your `hw05-<githubName>` directory in the terminal. (Tip: In VSCode you can click "Terminal" > "New Terminal" at the top of your screen for a terminal to appear) To run your code... * with the default image and 1 seam: `python3 seamcarve.py` * with the default image and more than one seam: `python3 seamcarve.py --seamcount <number>` * with a custom image and one seam: `python3 seamcarve.py --path <path to custom image>` * with a custom image and more than one seam: `python3 seamcarve.py --path <path to custom image> --seamcount <number>` **Note:** You **must** run the above commands from your `hw05` directory. You will get a "No such file or directory" error if you try running it from another location! **Task 2-f:** Test your code! Write tests for your `argmin` and `find_least_important_seam` functions. To help with generating tests, we have created an interactive spreadsheet [here](https://docs.google.com/spreadsheets/d/1GitYfKQxHkplQJtE_K0AdSiWgnwqZ0iktbSGsAcNrHg/edit?usp=sharing). For the 5x5 version, you can edit cells `A2:E6` to contain any number between 0 and 255, and the spreadsheet will automatically calculate `vals`, `costs`, `dirs`, and the seam, and display the resulting image. :::success We suggest experimenting with this spreadsheet before you start coding, to help you understand seamcarve! ::: If you copy the value of each of the light blue cells (`K1`, `R1`, `Y1`, `AB1`), you will get Python-friendly arrays that you can use in your tests! For example: ```python= import pytest from seamcarve import SeamCarve ... sc_spreadsheet = SeamCarve("5x5_blank.png") # importance_arr is copied from cell K1: importance_arr = [[255,168.3333333,125,211.6666667,255],... # expected_costs is copied from cell R1: expected_costs = [[706.25,619.5833333,576.25,... # expected_dirs is copied from cell Y1: expected_dirs = [[1,0,-1,-1,-1],[1,0,-1,-1,-1],[1,1,0,-1,-1],[0,1,1,0,-1]] #expected_seam is copied from cell AB1: expected_seam = [2,1,1,2,3] calculated_seam =\ sc_spreadsheet.find_least_important_seam(importance_arr) for i in range(0, 5): for j in range(0, 5): assert sc_spreadsheet.costs[i][j] == pytest.approx(expected_costs[i][j]) assert sc_spreadsheet.dirs == expected_dirs assert calculated_seam == expected_seam ``` :::info **Note:** Here, we use a bit of a trick to input the `vals` array, by using a 5x5 blank image in the constructor (so that the sizes of all of the arrays are generated correctly based on width and height). ::: :::info **Note:** Our spreadsheet breaks ties (such as in the calculation that is analogous to `argmin`) by selecting the smallest index. For example, if the cells in `costs` below the cell in question for computing `dirs` are `[24, 45, 24]`, we would put `-1` in `dirs`, not `+1`. If your spreadsheet tests are failing but your manually-entered tests are not, make sure you don't have ties, or that you are handling them in the same way we do! ::: :::warning **Note:** while you should generate some tests using this spreadsheet, also write out some other tests. Write out the tests for the `vals` array you have been using as an example here! ::: ### Further Specifications - You must use dynamic programming to find the lowest cost seam. In other words, your code should not have a running time greater than O(w∗h) where w is the picture width and h is the height in pixels. If you choose to find the lowest cost seam using brute force, your seam carver will be unreasonably slow and you’ll lose points. - You’re only asked to implement vertical seam carving. We do not ask you to do both, as there is no algorithmic difference between vertical and horizontal seam carving. ### Testing Requirements You should catch 70% of the codebreaker chaffs and 70% of the seamcarve chaffs. ## Handing In The deadline for the final submission is **Friday, April 15, 2022 at 11:59pm EST**. You should submit all your files on Gradescope, with solution files going in **HW5 Implementation** and your test file going in **HW5 Testing**. ### Files to Submit **HW5 Implementation** * `solution.pdf`, containing: * example Codebreaker tables and written answers to the Codebreaker tasks * example `vals` table with your `costs`, `dirs`, and seam array outputs * a completed `codebreaker.py` * a completed `seamcarve.py` **HW5 Testing** * a `test_hw5.py` with unit tests ______________________________ *Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the [anonymous feedback form](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*