Homework 4 (Spring 2025) - HedgeDoc

<style> h3 { border-bottom: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; } section.think { background-color: oklch(95% 0.01 0); border: 1px solid oklch(80% 0.01 0); color: oklch(40% 0.024 0); } section.conceptual { background-color: oklch(95% 0.01 150); border: 1px solid oklch(80% 0.01 150); color: oklch(40% 0.024 150); } section.design { background-color: oklch(95% 0.01 290); border: 1px solid oklch(80% 0.01 290); color: oklch(40% 0.024 290); } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; margin-top: 1em; margin-bottom: 1em; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # **Homework 4: Python Practice** **Due: Friday, April 4, 2025 at 11:59 p.m.** # Overview In this assignment, you'll gain some practice working with Python. You'll do this in two ways: - **Part 1**: We'll give you a starter file (`group_utils.py`), which has some bugs. You'll debug this file by writing **tests** and using the **debugger** to help you identify the bugs based on a specification. - **Part 2**: You'll write some of your own code in an environment that you've already seen: GraphQuest. We'll give you a stencil similar to `IGraph` and `NodeEdgeGraph` from your last project, and you'll implement your solution to the scheduler problem, based on your feedback. - **Part 3 (optional)** You can try out an interactive tutor to check whether you really understand how core programming concepts work. **Why is the assignment structured this way?** At this point in the course, you know most of the programming concepts (what a loop is, what a class is, what a list is, etc) to pick up Python, and you mostly need to learn to translate the syntax differences between Java and Python. **Some common challenges that you might encounter as you start using CS in the “real world” are being able to read language documentation, and being able to read other people’s code.** We have you practice these simultaneously as a way of starting to pick up Python syntax! As usual, if you have questions, please ask us on EdStem or in office hours! We'll be maintaining an FAQ/reading list post of common questions on Edstem, so please check here first. **Learning goals**: Concretely, in this assignment, you will: - Write comprehensive test cases based on function specification in order to debug existing code - Learn list comprehension in order to reduce total lines of code - Be able to understand already written Python code and what it does - Gain more practice with graphs by implementing your solution to the scheduling problem ### :sparkles: Important Python Resources :sparkles: As we are giving you less guidance, we expect you to use the resources you have available such as: - **[Our Python Stencil setup guide](https://docs.cs200.io/s/python-stencil-setup-guide)** (for how to load the stencil) - **[Our guide for going to Python from Java](https://docs.cs200.io/going-to-python-from-java)** which includes links to the Python documentation that you should refer to - **[Our Python Testing Guide](https://docs.cs200.io/s/python-testing-guide)**: how to run and debug tests, as well as this [annotated VSCode debugging guide](https://brown-csci0200.github.io/assets/lectures/23python1/Lec25_whiteboard_f22.pdf) - **[Our Python Style Guide](https://docs.cs200.io/python-style-guide)**: how to format your Python code - **The optional SMOL tutor in Part 3**: online quiz of how programming language features work, with examples presented in Python <br /> # Stencil and Setup Logistics You can download the stencil code using this **[Github Classroom](https://classroom.github.com/a/eSBdvEWs)** link. :::warning :warning::warning::warning: **Warning**: Since this is our first Python assignment, **be sure to read the [**Python Stencil Setup Guide**](https://docs.cs200.io/s/python-stencil-setup-guide)** for important instructions on how to set up VSCode to use the stencil. In particular, **make sure you [set up your environment](https://docs.cs200.io/s/python-stencil-setup-guide#Setting-up-your-environment)**--if you don't this, you won't be able to run any tests! ::: # Part 1A: Writing tests from specification ### Task 1A.1 Open up the starter code file called `group_utils.py`. **This file contains many bugs, and the code behavior does not match the documentation!** Similar to javadoc, python classes and methods have a *docstring* that describes what each class/method should do, what arguments it takes, and what it returns. **Read every docstring and familiarize yourself with what the code is meant to do.** :::info <details><summary><b>Python syntax note</b>: why do some field and method names start with _?</summary> In Python, a leading underscore (_) in field and method names is a convention that signals that the field/method is not public. The level of visibility that the programmer indicates (by including or not including _) is not enforced by the compiler; as with type annotations, it's simply convention to make code more easily readable. In other words, Python will still let you call/access a method/field with a leading underscore in its name from a different class (but you shouldn't do this!). ::: </details> ### Task 1A.2 Based on the _specification_ (docstrings), **write tests for the code**. See instructions below for guidance on how to think about writing tests. Overall, your tests should: - Pass only *well-formed* input into the `Group` constructor, for now (see note below for guidance). - Test every method (except for `_populate_skills`, which is a helper method to the constructor) - Test what you perceive might be common interactions between methods - Test edge cases based on the docstrings (for example, cases where a given input does not exist in the data) <details><summary><b><i>Note:</i> What is well-formed input?</b></summary> Well-formed input is a list of dictionaries, where each dictionary representing a person has the keys “name” (mapping to a string), “time in group” (mapping to a float), and “skills” (mapping to a list of strings). See <code>test_group_utils.py</code> for an example of such an input. </details> <details><summary><b><i>Note:</i> What does <code>import group_utils as g</code> mean?</b></summary> To use definitions (classes, methods/functions) from another file, you need to <i>import</i> that file. We will see multiple ways of importing files as we finish up the semester, but this particular line lets you refer to the definitions in group_utils.py by prepending <code>g</code>. to them (for example, to create a new Group, use <code>g.Group(...)</code>). In the next section, you can see how this comes in handy. </details> <br /> :::info ### Important: instructions for writing tests We’ve given you a testing file to start with that shows common ways to set up tests and use assertions. You should refer to our <a href="https://docs.cs200.io/s/python-testing-guide">Python testing guide</a> for more guidance. - **When you run your tests locally, your tests will not pass.** The code we have given you is buggy and your job will be to fix the code using your tests and the debugger. - <b>For readability, please remove the <code>test_example</code> function from this file after you’re done reading it</b>, and make your own test functions. Our testing guide contains the contents of this example test if you need to refer to it after you’ve removed it. - You do not have to test for violations of stated assumptions in this document (e.g. all names are unique). You can also assume that the constructor (and helper <code>_populate_skills</code> method) are correct (free of bugs) for well-formed inputs. - You should not modify `group_utils.py` (e.g. adding getters or setters) or directly test field values (e.g. `student_numcourses == 3`). Instead, verify the side-effects of methods using assertions on other methods. For instance, after calling `add_skill`, use `measure_progress` to confirm that a duplicate skill was not added. :::danger **For example, the below test will NOT work with the Homework 4: Testing Gradescope submission:** ```python def test_add_skill: test_group.add_skill("Claire","multiplication") assert len(test_group._person_list[1]["skills"]) == 4 # we should not directly access _person_list values ``` ::: ::: ### Task 1A.3 Submit your testing file to the Gradescope assignment called **Homework 4: Testing**. The grading system uses wheat/chaff grading to indicate if you’ve caught all the bugs in the file. Ensure your test set is complete by verifying that you receive full points for this task before proceeding to the next step. This will save you time in the overall process. :::warning #### Note: Ed and Hours policy for Parts 1A and 1B The TAs will not tell you which exact tests you missed (but you can ask for some hints), and they cannot solve the bugs for you. To be clear, you **can** use Ed and hours for: - Asking for clarification on <i>specific</i> Python documentation - Asking for guidance in interpreting the debugger (but you should not ask the TA to run through the debugger for you) - Asking how to translate a specific Java/programming concept to Python - Any other components of the assignment (using our normal hours/Edstem policies) <b>We are not trying to trick you here – all of the chaffs should be catch-able if you think through the expected behaviors and the edge cases of the code.</b> ::: # Part 1B: Testing and debugging others' code ### Task 1B.1: Debug and fix the program Use your testing file and the VScode debugger to **debug and fix the bugs in `group_utils.py`**, so that all of your tests pass. As you do this, you'll need to take some note on your debugging process--**read [Task 1B.2](#Task-1B2) before starting, for an overview of what you'll need to write down**. :::success <details><summary><b>Debugging Tip</b></summary> You might find yourself editing your testing file as you find and fix bugs. If you want to run tests locally on the buggy file, we suggest making a copy of <code>group_utils.py</code> <i>before</i> changing it (for example, copying the file to <code>group_utils_buggy.py</code> in the same folder, and then making changes to <code>group_utils.py</code>). Then, you can switch between which file you are testing by changing just the import line. <br> <br> <code>import group_utils as g</code> (for the file with your fixes) vs. <code>import group_utils_buggy as g</code> (for the file with bugs) <br> <br> Nothing else in the testing file needs to change, because all of your tests just reference the name <code>g</code>! <br> <br> <b>When you submit your work, make sure that your final test submission to Gradescope has</b> <code>import group_utils as g</code> <b>at the top to ensure we use your fixed version when grading!</b> ::: </details> :::info <details><summary><b>Seeing new Python syntax for the first time?</b></summary> Read through the resources we gave you to try to interpret the syntax, and if you’re really stuck, ask for some help on Ed. While long, the Python built-in types documentation is your friend here. For example, if you encounter syntax like <code>my_list[1:3]</code>, which is very different from what we’ve seen in Java, try scrolling through the built-in types documentation until you encounter something that looks like this syntax. Hint: it appears in a helpful table in a section for list operations, and it has something to do with slicing. Once you find the documentation and read what it does, we encourage you to play around with it – make a new file and try making your own data structures that call on the new syntax in multiple ways. Just like we did in class, you can also put a `pass` statement at the end of any file, debug the file, and then use the debug console to try out the new syntax: ![](https://lh3.googleusercontent.com/v2pQ0nmrdFfc5Ldgac1lPKG0-1bb2LlQvGcH5JNzW4MEYdg_ryjgqom9oJQGmoBm9R3R2VIo6Wb-ehieQlsgkTp-J4g_aCcXqyzL-878wMTOOmz_dsScG8BNxz1jp0hkiaRcxZxi6hlmFqEDEEhbw5o) ::: </details> ### Task 1B.2: Document your debugging process for `add_skill` Create a document called `hw4_debug.pdf` with a series of screenshots/images that shows **your debugging process for the `add_skill` method only**, based on the guidelines listed below. (There are other bugs outside of `add_skill`, but you only need to write your up your debug process for this method.) Your document should have screenshots/images for: 1. **Failing test function**: Include a screenshot of the failing test function that catches the bug. Add a caption specifying the line number of the assertion that failed, especially if the test function contains multiple assertions. 2. **Expected state drawing:** A drawing of what you expect the field(s) of `Group` to look like after you run `add_skill` with the inputs you used in your test function. This doesn’t have to follow a specific format, but make sure we can understand what is a list, what is a dictionary, etc. 3. **Debugging window screenshot:** Include a screenshot of the debugging window showing: - The paused line of code where the debugger detected the issue. - Relevant variables expanded in the debugger’s variables pane (highlight those that differ from your expected state drawing in step 2). Write a short (3-5 sentence) caption that explains how the screenshot from (3) demonstrates the issue with the code and how it contributes to the failing assertion from (1). If there were multiple issues with `add_skill`, include a debug screenshot and explanation for each one. Save the screenshots and captions in a file called `hw4_debug.pdf`. # Part 1C: Writing your own code :::success **Helpful tip**: The following tasks ask you to modify the code we have given you. **After you make your modifications, you should make sure the tests you wrote in the previous part still pass.** The point is for you to use your tests to help you fix your implementation! ::: </details> ### Task 1C.1 Change the `average_length_of_membership` method to use a list comprehension instead of a loop. All of your tests should still pass after you complete this task, but there should be no for-loops in your code. :::success <details><summary>Hint</summary> There is a built-in function to add up all of the elements of a list. Read the documentation to find it. ::: </details> ### Task 1C.2 Add a method called `people_with_skill` to the `Group` class that takes in a skill (as a string) and returns a list of all of the names of people with that skill. If the skill is not found, this method should return an empty list. The order of the names does not have to be the same as they appear in `self._person_list`. Add test(s) for this method in your test file. ### Task 1C.3 Add a method called `_validate_data` to the Group class that takes in no inputs (except for self, which is an input to all methods in a class). Specifically, `_validate_data` should check each `person` in `self._person_list` and do the following: - Verify that the `person` is a dictionary - Verify that the `person` has the keys `"name"`, `"time in group"`, and `"skills"` - Cast `person["name"]` to a string - Cast `person["time in group"]` to a float - Verify that `person["skills"]` is a **list** of **strings** If any of these attributes are violated, the method should `raise ValueError("Data unable to validate")` :::info <details><summary><b>Python syntax note</b>: type-checking and casting</summary> To check if something is of a certain type in Python, you can use <code>type()</code>: <br> <code>my_list = ["a", "b", "c"]</code> <br> <code>assert type(my_list) is list # will pass</code> <br> <code>assert type(my_list) is dict # will fail</code> <br> <br> To cast something to another type, you can use <code>float()</code>, <code>int()</code>, <code>str()</code>, etc: <br> <code>val1 = "0.1"</code> <br><code>val2 = 0.1</code> <br><code>val3 = "oh point one"</code> <br><br><code>res1 = float(val1) # will be a float with value 0.1</code> <br><code>res2 = float(val2) # will be a float with value 0.1</code> <br><code>res3 = float(val3) # will raise a ValueError</code> ::: </details> Call this method from the constructor, and write test(s) for the constructor to make sure the validation works. # Part 2: Implementing the scheduler :::danger You should wait to start this component until after you've received your peer review feedback. ::: :::warning :warning: **Required background**: This component assumes that you have worked on **Part 2B of the GraphQuest assignment**, which deals with using graphs to manage lab schedules. For more conceptual background about how to use graphs to represent schedules, see the GraphQuest handout. <br /> If you have not completed Part 2B of GraphQuest for any reason (eg. extenuating circumstance), please reach out to the instructor at cs200-profs@brown.edu before working on this part. ::: In this next part, you'll gain some experience transferring your own ideas about programs from Java into Python. In GraphQuest Part 2B, you created a plan to validate and check lab schedules when formulated as a graph problem. Now, you'll implement functions to implement these, based on your prior plans and feedback you receive. Specifically, you'll implement: - `check_validity`: which checks whether a *proposed schedule* for two people indeed respects all of the constraints - `find_schedule`: which computs a valid schedule for two people, if one exists, or raises an exception if none exists For more conceptual background about these components, and how to think about graphs as schedules, please see the **Part 2B of the GraphQuest Handout**. ## Background: new stencil code for graphs (`scheduler.py`) As a starting point for your implementation, we've provided a new stencil for working with graphs in the following files: - `node_graph.py` contains an implementation for a node-based graph (`NodeEdgeGraph`), which behaves exactly like `NodeEdgeGraph` from GraphQuest (same methods, data structures, etc.). You shouldn't need to modify this file. - `scheduler.py`: Is contains blank functions for `check_validity` and `find_schedule`--your implementation will go here! - `test_scheduler.py`: Look here for some examples of how to build and work with graphs; you'll also write your tests here. :::info <details> <summary>Where's the <code>IGraph</code> interface?</summary> Good catch! The way Python handles typing is much more flexible than Java, so Python doesn't really have a built-in notion of an interface. Instead, Python simply expects that the programmer will implement all of the required methods--if a method isn't available when Python needs to use it, an error will occur. Thus, any object can technically be used with any code (regardless of type), so long as it has the required methods and fields! This is called *[duck typing](https://en.wikipedia.org/wiki/Duck_typing)*, from the phrase "if it looks like a duck and quacks like a duck, it must be a duck". Duck typing is useful for building programs quickly and making classes flexible, but it can be difficult to manage on large projects--see the link (and its citations) for more info. </details> ::: To build your implementation, you'll implement the methods in `scheduler.py` and write some tests in `test_scheduler.py`. ## Task 2.1: Skim over the new stencil Before you start your implementation **skim over the new stencil code** in `node_graph.py` and `scheduler.py` and compare it to your stencil for GraphQuest. To do this, we recommend looking at the code side-by-side. Some things to consider: - The Python version of `NodeEdgeGraph` is pretty much a one-to-one translation of the Java code (this is often called a *port* of the code). Take a look at how both versions achieve the same goals - Notice where the structure between the Java and Python versions is the same and where it isn't. For example, `NodeEdgeGraph` is a class in both versions, whereas `scheduler.py` just has functions in a file (and not a separate `Scheduler` class) **There's nothing to hand in for this part**--we just want you to be vaguely familiar with the code (and see more examples of comparing Python and Java code) before continuing. When you're ready, proceed to the next task! ## Task 2.2: Implement your scheduler tests As part of your plan for GraphQuest part 2B (specifically, Task 2B.1), you made some sample lab-constraint graphs to help you reason about your plan. In the file `test_scheduler.py`, **implement some tests for `check_validity` and `find_schedule` based on your plan**--see the existing tests in `test_scheduler.py` for some examples. To do this: 1. You should **write separate tests for `check_validity` and `find_schedule`**, so that you can test these separately. 3. **Remember that a graph can have multiple possible valid schedules.** How, then, should you test `find_schedule`? Consider using `check_validity` to help! 4. **Be sure to create graphs with only *undirected* edges.** In our lab scheduling problem, all edges are undirected: e.g., if lab 1 conflicts with lab 2, then lab 2 conflicts with lab 1. For more about directed vs. undirected edges, see [here](https://docs.cs200.io/s/VCxw1Ydog#IGraph-An-interface-for-graphs). 5. **You don't need to exactly create the graphs from your plan.** If you come up with other ideas, or smaller graphs that can express the same properties, feel free to use them. Overall, your tests don't need to be super comprehensive (there's no wheat/chaff testing), but **you should cover both valid an invalid schedules for both `check_validity` and `find_schedule` on at least 3 different graphs**. You'll be using your tests to help check your implementation, so it's in your best interest to have some good tests! ### Task 2.3: Implement `check_validity` Using your plan, tests, and peer review feedback as a guide, **implement `check_validity`** in `scheduler.py`. To get started, here's some things to think about (similar to the advice from GraphQuest): - For help with Pyhon syntax, remember our [Important Python Resources](#-Important-Python-Resources-) - When working with the graph, remember that you can use all the methods in the `NodeEdgeGraph` class - You can start by thinking about how to handle *connected* graphs (ie, graphs where all the nodes are in one big cluster). After that, consider how you can handle graphs with multiple, non-connected components When you're confident in your implementation, **run your tests** to check your work. At this stage, you should be able to pass your own tests on `check_validity`. To help you test and debug, remember the debugging skills you learned from Part 1! ### Task 2.4 After you've implemented `check_validity`, use your tests, plan, and review feedback to **implement `find_schedule`**. For more info on this, take a look at Task 2B.3 from GraphQuest. As with Task 2.3, keep the following in mind: - Remember our [Important Python Resources](#-Important-Python-Resources-) - Start with connected graphs first :::success <details> <summary>Hint (and syntax example for BFS in Python)</summary> As we hinted during GraphQuest, **your implementation can use BFS to help with this problem, similar to `hasRoute` and `getRoute` in GraphQuest**. You should *not* need to implement `hasRoute` or `getRoute` directly to solve this problem, but your implementation for `find_schedule` should be able to leverage similar ideas. To get you started thinking about this, here's an example for `hasRoute` (using BFS) in Python so you can see the syntax: ```python def has_route(graph: NodeEdgeGraph, from_node: str, to_node: str) -> bool: """ Parameters: graph -- The graph to check from_node -- Node from which to start searching to_node -- Node we want to reach """ # Set up and initialize data structures visited = set() to_check = [] to_check.append(from_node) # Process nodes to search for to_node while len(to_check) != 0: check_node = to_check.pop(0) # remove first element if check_node == to_node: return True elif check_node not in visited: visited.add(check_node) for n in graph.get_neighbors(check_node): to_check.append(n) return False ``` </details> ::: Again, once you're confident in your implementation, **run your tests** to help check your work!  # Part 3 (Optional) If you want to test you understanding of some of the corner cases of programming with arrays, functions, and variables, work through the exercises in the [SMoL Tutor](https://script.google.com/a/macros/brown.edu/s/AKfycbxFr5YtuHHRT8wLrruPRfa0lnMYdrzFn7uDJz9Iz2TGjL2DwOs3lui1WMjghkk16Y2v/exec). This tutor was built by a Brown CS PhD student as part of his dissertation work on helping students correct misconceptions of core programming language features (SMoL stands for "small model of languages"). Our version is configured to use Python, though the exact same issues arise in other languages (Java, Javascript, and more). Using the tutor is optional -- you do not need to work with it. We are, however, offering it as something to try if you want to check how well you are understanding programming nuances that apply across most mainstream languages. # Handin To hand in your homework, you should submit your work to both the implementation and testing assignments: 1. Submit the following files to **Homework 4: Implementation** on Gradescope: - `group_utils.py` - `test_group_utils.py` - `hw4_debug.pdf` (your debugging process document from Part 1B) - `scheduler.py` - `node_graph.py` - `test_scheduler.py` 2. Submit the following files to the **Homework 4: Testing** assignment on Gradescope: - `test_group_utils.py` *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our_ [_anonymous feedback form_](https://docs.google.com/forms/d/e/1FAIpQLSfe9cDwpzv7xCbbevbrAZacuB4MB8yxer8jiK0SK-CQH3RXuQ/viewform)_!_