Assignment 5
Submit Assignment
- Due Dec 11 by 11:59pm
- Points 110
- Submitting a file upload
- File Types py
- Available Nov 21 at 12am – Dec 11 at 11:59pm 21 days
Programming Assignment #5: Graph Solution to the Water Container Problem
What is the assignment?
- To implement a function that uses a graph-search approach to produce a “path” that represents a solution to the water container problem.
- See the following wikipedia page for more information about this problem, which dates back much further than the Die-Hard movie that it appears in 😉
What to hand in?
- One (and only one) *.py file should be handed in. All your checks, unit tests should be inside of this file.
- The name of the function in your program should be findWaterContainerPath, and it should except three integer arguments.
- Note that your program should be able to run at the console/terminal (e.g. $ python your_file.py). If it does not, then the execution portion of the assignment will be 0.
What needs to be done?
- Ultimately, all that needs to be done is to have a function, named findWaterContainerPath, return a list of states that represents a solution to the water container problem.
- Note that each state can be thought of a vertex on a graph, and the transitions between the states can be thought of as the edges.
- To successfully implement the function you will need to figure out what all of the possible state transitions (i.e. edges). You’ll then perform a BFS across all of these states; adding a state to your final solution path when it is used (and being sure to not add, or to remove, states that are not on the solution path).
Be careful…
- As with all assignments, do not copy code from the internet, and do not share/copy code directly from others. There are lots of poor implementations of this problem online, so even if you look at some to better understand the problem, be sure that you implement your own so that you can be confident that you understand what each step is doing.
- Remember, copying/sharing code is a violation of the Student Code of Conduct. If you are found to have been doing this, then the grade for this assignment may be a zero, and a report with the Dean of Students may be filed.
Getting Started
- Use the following code to get started if you like. If, however, you decide not to, be sure that you still name your function “findWaterContainerPath”, and that it accepts the three given arguments.
import math
import unittest
def findWaterContainerPath(a, b, c):
""" DOCUMENTATION FOR THIS FUNCTION """
starting_state = (0, 0)
final_path = list()
final_path.append(starting_state)
""" THIS IS WHERE THE REAL WORK FOR THIS ASSIGNMENT WILL BE """
return final_path
""" ADD ANY OTHER (HELPER) FUNCTIONS THAT ARE NEEDED HERE """
class TestWaterContainerGraphSearch(unittest.TestCase):
def testFindWaterContainerPath(self):
""" INSERT DESCRIPTION OF WHAT THIS TEST IS CHECKING """
""" IMPLEMENT YOUR FIRST TEST HERE """
pass
""" ADD MORE TESTS TO CHECK YOUR FUNCTIONS WORKS FOR OTHER VALUES """
def main():
capacity_a = input("Enter the capacity of container A: ")
capacity_b = input("Enter the capacity of container B: ")
goal_amount = input("Enter the goal quantity: ")
# ADD SOME TYPE/VALUE CHECKING FOR THE INPUTS (OR INSIDE YOUR FUNCTION)
if int(goal_amount) % math.gcd(int(capacity_a), int(capacity_b)) == 0:
path = findWaterContainerPath(int(capacity_a), int(capacity_b), int(goal_amount))
else:
print("No solution for containers with these sizes and with this final goal amount")
print(path)
# unittest_main() - run all of TestWaterContainerGraphSearch's methods (i.e. test cases)
def unittest_main():
unittest.main()
# evaluates to true if run as standalone program
if __name__ == '__main__':
main()
unittest_main()Good luck!
Rubric
Assignment 5 RubricAssignment 5 RubricCriteriaRatingsPtsThis criterion is linked to a Learning OutcomeProgram Execution and Output30.0 to >25.0 ptsGoodProgram executes with no syntax or runtime errors and produces nearly all of the appropriate output when run through the test script (26pts – 30pts).25.0 to >10.0 ptsFairProgram executes with via the test script but does not produce all of the desired/correct output (11pts – 25pts).10.0 to >0 ptsPoorProgram does not execute via the test script without some modification and/or produces none or very little of the desired output in the test script (0pts – 10 pts).30.0 pts
This criterion is linked to a Learning OutcomeCode Logic and Design40.0 to >30.0 ptsGoodProgram has all required classes, variables, and methods defined (31pts – 40pts).30.0 to >10.0 ptsFairProgram has at least some but not all requisite classes, methods, or variables (11pts – 30pts).10.0 to >0 ptsPoorProgram has few or none of the classes, variables, or methods that were required (0pts – 10pts).40.0 pts
This criterion is linked to a Learning OutcomeCoding Standards and Documentation30.0 to >20.0 ptsGoodProgram has documentation for each class, method, function and this is displayed when using Python’s help function, “help()”. Documentation should clearly explain how and why methods are implemented as is (e.g. when and how does HashTable choose to resize itself). In addition to this, for full points the code should be consistently formatted, with consistency in how methods and variables are named (21pts – 30pts).20.0 to >10.0 ptsFairProgram has some documentation and is somewhat consistent in formatting, variable/method naming, etc. However, at least one of those is missing/incorrect (11pts – 20pts).10.0 to >0 ptsPoorProgram has little to no documentation, is not structured/formatted well, and does follow a consistent approach towards naming variables/method (0pts – 5pts).30.0 pts
This criterion is linked to a Learning OutcomeTesting10.0 to >5.0 ptsGoodProgram tests edge cases, or scenarios that would produce unexpected results using Python’s unittest (4pts – 5pts).5.0 to >2.0 ptsFairProgram tests for some edge cases but is missing important/obvious edge cases and may not be using unittest (3pts – 4pts).2.0 to >0 ptsPoorProgram has very few or no checks for edge cases, and does not make use of unittest (0pts – 2pts).10.0 pts
Total Points: 110.0PreviousNext