2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 1/15 Assignment 2 Automated Puzzle Solving Due date: Thursday, April 8, 2021, before 1:00 pm sharp, Toronto time. You may complete this assignment individually or with a partner who can be from any section of the course. Learning goals By the end of this assignment, you should be able to: read complex code you didn’t write and understand its design and implementation, including: reading the class and method docstrings carefully (including attributes, representation invariants, preconditions, etc.) understanding relationships between classes, by applying your knowledge of composition and inheritance complete a partial implementation of a class, including: reading the representation invariants to enforce important facts about implementation decisions reading the preconditions to factor in assumptions that they permit writing the required methods according to their docstrings use inheritance to define a subclass of an abstract parent class implementing algorithms by translating their steps into python code by: choosing an appropriate ADT to solve the problem deciding if recursion is appropriate implement recursive methods for trees when provided with their specifications. perform unit testing on a program to verify correctness And more specifically: implement depth and breadth first searches to solve logic puzzles 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 2/15 implement a simple expression tree class be able to implement additional logic puzzles beyond those in this assignment explore the behaviour of depth and breadth first solvers on various logic puzzles Coding Guidelines These guidelines are designed to help you write well-designed code that will adhere to the interfaces we have defined. You must: write each method in such a way that the docstrings you have been given in the starter code accurately describe the body of the method. avoid writing duplicate code. write a docstring for any class, function, or method that lacks one. *clarification added March 24th - you aren't required to add docstrings to any of the provided code* You must NOT: change the parameters, parameter type annotations, or return types in any of the methods or functions you have been given in the starter code. add or remove any parameters in any of the methods you have been given in the starter code. change the type annotations of any public or private attributes you have been given in the starter code. create any new public attributes. create any new public methods or functions. write a method or function that mutates an object if the docstring doesn’t say that it will be mutated. add any more import statements to your code, except for imports from the typing module and the modules you’re implementing in this assignment. You may find it helpful to: create new private helper methods or functions for the classes you have been given. 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 3/15 if you create new private methods or functions you must provide type annotations for every parameter and return value. You must also write a full docstring for each method as described in the function design recipe (https://www.teach.cs.toronto.edu/~csc148h/winter/notes/python-recap/function_design_recipe.pdf) create new private attributes for the classes you have been given. if you create new private attributes you must give them a type annotation and include a description of them in the class’s docstring as described in the class design recipe (https://www.teach.cs.toronto.edu/~csc148h/winter/notes/object-oriented- programming/class_design_recipe.pdf) import more types from the typing module All code that you write should follow the function and class design recipes. While writing your code you can assume that all arguments passed to the methods and functions you have been given in the starter code will respect the preconditions and type annotations outlined in the provided docstrings. Introduction: Problem Domain Puzzle solving is a typically human activity that, in recent decades, has been explored in the context of computers. There are many potential benefits to this. For example, we can offload some puzzle-solving tasks to computers, we may better understand human puzzle-solving by programming computer puzzle solvers, or we might generate novel puzzles using a computer program. This assignment investigates a class of puzzles that have the following features in common: feature description full information all information about the puzzle state at any given point is visible to the solver; there are no hidden or random aspects well-defined extensions a definition of legal "extensions" from a given puzzle state to new states is given well-defined solution a definition of what it means for the puzzle to be in a solved state is given These features are common to a very large class of puzzles: crosswords, sudoku, peg solitaire, verbal arithmetic, and so on. This assignment generalizes the required features into an abstract superclass Puzzle and solving such puzzles is written in terms of this abstract class. 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 4/15 Once this is done, particular concrete puzzles can be modelled as subclasses of Puzzle and solved using the solve method of a subclass of the Solver abstract class, which will be described later. Although there may be faster puzzle-specific solvers for a particular puzzle that take advantage of specific features of that puzzle, the general solvers you will build are designed to work for all puzzles of this sort. The Puzzles We will start by introducing how the puzzles will be represented and what specific puzzles we will consider in this assignment. abstract Puzzle class The abstract class Puzzle has the following methods: , which are not implemented, but meant to be implemented in subclasses: method description is_solved (abstract) returns True iff the puzzle is in a solved state extensions (abstract) returns a list of extensions from the current puzzle state to new states that are a single ‘move’ away fail_fast (has a default implementation in Puzzle ) returns True if it is clear that the puzzle can never, through a sequence of extensions, move into a solved state And that’s it! Note: each subclass will need its own __init__ method in order to represent that particular puzzle’s state information. Sudoku This puzzle commonly appears in print media and online. You are presented with an n × n grid with some symbols, for example digits or letters, filled in. The symbols must be from a set of n symbols. The goal is to fill in the remaining symbols in such a way that each row, column, and subsquare, contains each symbol exactly once. In order for all of that to make sense, n must be a square integer such as 4, 9, 16, or 25. ×n − √ n − √ 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 5/15 You may want to read more about sudoku (https://en.wikipedia.org/wiki/Sudoku) to get a feel for the puzzle if you aren’t already familiar with it. Word Ladder This puzzle involves transforming one word into a target word by changing one letter at a time. Each word must belong to a specified set of valid words. Here’s an example where we assume that the set of valid words is a rather large set of common English words, and the goal is to get from the word ‘cost’ to the word ‘save’: cost → cast → case → cave → save Expression Tree Puzzle This puzzle consists of an algebraic equation containing one or more variables, and a target value. The puzzle is solved when the variables are assigned values such that the expression evaluates to the target value. The Solvers Now that we know a bit about the puzzles that we will be implementing, we will turn our attention to how we will implement the solvers. Searching Solving a puzzle can be done by systematically searching for a solution, starting from its current state. To make this daunting task even possible, we have to be sure that we have a systematic way of exploring all possible puzzle states - without needlessly re-visiting the same state twice. You will implement two systematic searching techniques. The implicit tree underlying our search To understand our searching techniques, it helps to think of the tree that is defined by all the possible states of a puzzle: each node is one puzzle state, the root is the initial state of the puzzle, and the children of a node are its extensions (puzzle states that are one 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 6/15 move away). When we actually implement the algorithms, we don't need to explicitly form this tree, but it is useful to remember that it is there. (The A2: Search Algorithms Visual Guide (https://q.utoronto.ca/courses/204422/pages/a2-search-algorithms-visual-guide) examples for the Word Ladder do a good job helping us visualize this tree.) The search algorithms Depth-first search and breadth-first search are two approaches to searching through the space of possibilities for a solution. With depth-first search, we search deeply before we search broadly. We exhaustively search the first subtree before considering any other subtree. And we use the same strategy when we search that subtree: exhaustively searching its first subtree before considering any other subtree. And so on - think recursively! With breadth-first search, we search broadly before we search deeply. We consider all puzzle states at depth 1, then all puzzle states at depth 2, and so on until we have searched all puzzle states in our tree. (You will find a queue is helpful for keeping track of puzzles states to be checked when their turn comes.) Because we consider states that are “closer” to the starting state before those that are “farther”, we are guaranteed to find the shortest path to a puzzle’s solution. For both solvers, we run the risk of encountering a puzzle state that we've already seen, and which already failed to produce a solution. To avoid exploring that state all over again, we will keep track of states we've seen before and just ignore them if we encounter them again. For certain puzzle types, we might also be able to check whether we can quickly tell if a puzzle state is unsolvable. Such a check can be incorporated into our search algorithms and you will do so in your implementation. Rather than spell out the algorithms in full detail and simply have you translate them into code, we have put together some worked examples (https://q.utoronto.ca/courses/204422/pages/a2-search-algorithms-visual-guide) - one of your tasks in this assignment will be to turn the above high level descriptions and the concrete examples into 2 algorithms you can implement in Python! The Solver Class The abstract class Solver defines the interface for the following method: method description 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 7/15 method description solve returns a path to a solution of a given puzzle. This method is abstract and must be implemented in a subclass. You will create two subclasses of the Solver class - DfsSolver , which uses the depth first search strategy in its implementation of solve , and BfsSolver , which uses the breadth first search strategy in its implementation of solve . Setup and Starter Code To get started: 1. Download a2.zip (https://q.utoronto.ca/courses/204422/files/13398949?wrap=1) (https://q.utoronto.ca/courses/204422/files/13398949/download?download_frd=1) . It contains the starter code. 2. Unzip the file and place the contents in PyCharm in your a2 folder (remember to set your a2 folder as a sources root) *NEW* Note: In order to run the provided a2_starter_tests.py module, you will need to install the python package networkx , which is imported by the expression_tree.py module in Task 4 (since the starter tests file contains tests for each of the tasks you will complete). Please follow the instructions at the bottom of the Software Guide’s Installing Python libraries section (https://q.utoronto.ca/courses/204422/pages/software-guide#part-3-installing-python-libraries) to install the networkx package. Ask on Piazza or visit office hours if you need help with this. Tasks We have broken down the assignment into several tasks. For the most part you, can tackle the assignment in any order that you want, but note that Task 5 requires Task 4 and part of Task 3 requires Task 2. Task 6 is optional, but is a great way to try out your code and 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 8/15 see it in action! After reading the handout, docstring examples, and comments in the starter code, please ask for clarification on Piazza if you still find any of the specifications below to be unclear. Any official clarifications will be added to the Assignment 2 FAQ (https://piazza.com/class/ki8belwj4u65yb?cid=2353) on Piazza. Task 1: SudokuPuzzle We provide you with a mostly-implemented subclass SudokuPuzzle of class Puzzle . 1. Read and understand the provided code in puzzle.py for the abstract Puzzle class. 2. Read through the SudokuPuzzle class. Understand how the puzzle is represented, how extensions is implemented, and familiarize yourself with the provided helper methods. Note that some parts of the code use list comprehensions, as well as the functions any and all . You do not need to use list comprehensions, but you may find them helpful in making your code simpler in the next step. These are covered in a worksheet on list comprehensions (https://q.utoronto.ca/courses/204422/files/12900032?wrap=1) if you are looking for a quick reference. 3. Implement fail_fast for the SudokuPuzzle class by having it return True for any sudoku where there is at least one empty position that will be impossible to fill in because the set of symbols has been completely used up by other positions in the same row, column or subsquare. You should run the provided doctests to test your code, but you are encouraged to add more doctests to fail_fast (or write pytests) for further testing. Task 2: solver.py 1. Read the docstrings provided in solver.py and familiarize yourself with the interface that the Puzzle class provides. 2. Go through the A2: Search Algorithms Visual Guide (https://q.utoronto.ca/courses/204422/pages/a2-search-algorithms-visual- guide) (courtesy of Sophia!) to make sure you understand how the depth first and breadth first search algorithms work. 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 9/15 3. Implement the DfsSolver and BfsSolver classes in solver.py , based on the depth first search and breadth first search algorithms described earlier. The provided starter tests test_dfs_solver_example and test_bfs_solver_example in a2_starter_tests.py can be used as a starting point for testing your solvers. 4. Many logic puzzles, like Sudoku, actually require their solution to be unique. Implement the has_unique_solution method in the SudokuPuzzle class, based on its docstring description. We'll be posting an additional play_sudoku.py module later (now available here (https://q.utoronto.ca/courses/204422/files/13362316?wrap=1) (https://q.utoronto.ca/courses/204422/files/13362316/download? download_frd=1) !) which will make use of this method to generate random sudoku for you! Task 3: WordLadderPuzzle 1. Read and understand the provided code in word_ladder_puzzle.py . 2. Override the __str__ and __eq__ methods. 3. Override extensions . A legal extension of a WordLadderPuzzle is a new puzzle state where the new from_word differs by a single letter from the previous from_word . 4. Override is_solved . The puzzle is solved when from_word is the same as to_word . 5. Implement method get_difficulty according to its docstring. (Requires Task 2) Once you have completed the above methods and Task 2, you can try running the provided play_word_ladder.py module. Note: We do NOT require you to implement fail_fast for this puzzle type, as it isn't entirely obvious what it should look like! Of course, you are certainly welcome to attempt to devise a strategy to quickly check if a WordLadderPuzzle has no solution. Feel free to discuss your approach on Piazza if you come up with anything good! 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 10/15 Task 4: ExprTree Note: This part of the assignment requires you to install two python packages in order for your code to run (you don’t need to write any code using them, but the code we have provided makes use of them): networkx and pygame_gui. You don’t need pygame_gui except for in the optional Task 6, but you can install them both now. Please follow the instructions at the bottom of the Software Guide’s Installing Python libraries section (https://q.utoronto.ca/courses/204422/pages/software-guide#part-3-installing-python-libraries) to install these two packages. Ask on Piazza or visit office hours if you need help with this. Before we can implement the ExpressionTreePuzzle class, we need to develop an ExprTree class to represent an Expression Tree. 1. Read and understand the provided code in expression_tree.py . 2. Implement the methods in the ExprTree class, as specified in the starter code. Some additional details are provided below to help you get started. 3. Implement the construct_from_list function at the bottom of expression_tree.py . (See below for a description of how this function works.) Expression Tree Specification In this assignment, an expression tree can contain the single digit constants (1-9), single letter variables containing only the letters a-z, and the operations: addition (+) and multiplication (*). Numbers and variables are leaves of the tree. Operators must have at least 2 children. The same variable name may appear more than once in the expression tree. Variables can be given single digit values 0-9. Note that unlike constants, variables can have a value of 0. (As we will see, in the context of the ExpressionTreePuzzle class, the value 0 corresponds to an "unassigned variable".) A Convenient Way to Construct Expression Trees 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 11/15 It is cumbersome to create a substantial expression tree using the initializer from class ExprTree . Function construct_from_list allows client code to create one from a list of lists instead. Here is a simple example: [['+'], [3, '*', 'a', '+'], ['a', 'b'], [5, 'c']] The first '+' will be the root of the tree. The next list contains the children of '+' : 3 , '*' , 'a' , and '+' . Of these, only the operators have children. The next list contains the children of '*' : 'a' and 'b' . Neither has children itself. And the last list contains the children of the second '+' : 5 and 'c' . Neither has children itself. Hint: A queue can help keep track of whose children the next list contains. Visually, the resulting expression tree looks like this (note we use the symbol to denote multiplication in the diagram): This expression tree’s string representation would be: (3 + (a * b) + a + (5 + c)) Evaluating an ExprTree In order to evaluate an expression tree, a variable lookup dictionary is provided to specify the value of each variable (see the eval method). All variables in the expression must appear in the lookup dictionary. For our example above, if the lookup dictionary was {'a': 0, 'b': 0, 'c': 0} , then the expression tree would evaluate to 8 . × 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 12/15 If the lookup dictionary was instead {'a': 2, 'b': 5, 'c': 6} , then the expression tree would evaluate to 26 . Task 5: ExpressionTreePuzzle Once your ExprTree class is complete, you can implement the ExpressionTreePuzzle class in expression_tree_puzzle.py . 1. Read and understand the provided code in expression_tree_puzzle.py . 2. Override the __str__ method for the ExpressionTreePuzzle subclass in expression_tree_puzzle.py . 3. Override extensions . Legal extensions of a state assign a value from 1-9 to a single variable that has no assigned value. For example, if the variables dictionary was formerly {'v': 0} , then each extension would assign a different value from 1-9 to 'v' . If the variables dictionary was formerly {'v': 5} , then the puzzle would have no extensions, as all variables have been assigned a non-zero value. 4. Override is_solved as specified in the code. 5. Implement fail_fast for the ExpressionTreePuzzle class. The exact implementation is up to you, but we have provided a couple of hints in the code if you aren’t sure how to approach this. Task 6: Try out your code! Once you have completed the first 5 tasks you will be able to run: play_sudoku.py (requires Tasks 1 and 2) play_word_ladder.py (requires Tasks 2 and 3), experiment.py (requires Tasks 2 and 3), and play_expression_tree.py (requires Tasks 2, 4, and 5) 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 13/15 There are no marks for this part, but it can be a fun way to debug your code and further explore what you can do with the code you have written. Module play_sudoku.py (now posted! - download a2-play-sudoku.zip (https://q.utoronto.ca/courses/204422/files/13362316?wrap=1) (https://q.utoronto.ca/courses/204422/files/13362316/download?download_frd=1) and copy the files into your a2 directory) This module contains a simple GUI to let you try playing the sudoku puzzle you implemented. It makes use of your solvers in two ways: (1) to create a random SudokuPuzzle of a selected difficulty level and (2) to provide you with hints as you try solving the puzzle. The code also has a nice application of inheritance to let us add randomness to the puzzles we generate. Module play_word_ladder.py This module contains a simple text UI to let you try playing the word ladder puzzle you implemented. It makes use of your solvers in two ways: (1) to create a random WordLadderPuzzle of a selected difficulty level and (2) to provide you with hints if you get stuck solving the puzzle. Module experiment.py This module runs a small experiment and produces output that you can review to verify your understanding of how the solvers perform on different puzzles. Feel free to add your own experiments and share any interesting observations you make with the class! Sample Output: Puzzle Type Solver len(sol) time Sudoku Bfs 13 0.01907 Sudoku Dfs 13 0.00139 Sudoku Bfs 54 0.43171 Sudoku Dfs 54 0.15584 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 14/15 Puzzle Type Solver len(sol) time WordLadder Bfs 5 0.03384 WordLadder Dfs 703 0.04225 Module play_expression_tree.py This module contains a simple GUI to let you try playing the expression tree puzzle you implemented. It makes use of your solvers to provide you with hints. You are free to modify or add to any of the code provided in these 4 modules. Polish! Take some time to polish up. This step will improve your mark, but it also feels so good. Here are some things you can do: In each module you are submitting, run the provided python_ta.check_all() code to check for errors and violations of the “PEP8” Python style guidelines. Fix them! Check your docstrings to make sure that they are precise, complete, and that they follow the conventions of the Function and Class Design Recipes. Read through and polish your internal comments. Remove any code you added just for debugging, such as print statements. Remove the word “TODO” wherever you have completed the task. Take pride in your gorgeous code! Submitting your work Submit the following files on MarkUs (https://markus148.teach.cs.toronto.edu/csc148-2021-01/) sudoku_puzzle.py solver.py 2021/4/5 Assignment 2: CSC148H1 S (All Sections) 20211:Introduction to Computer Science https://q.utoronto.ca/courses/204422/pages/assignment-2 15/15 Category Weight pyTA 10 marks MarkUs self tests 20 marks hidden tests 70 marks word_ladder_puzzle.py expression_tree.py expression_tree_puzzle.py We strongly recommend that you submit early and run the provided self tests on MarkUs as you go. We will grade the latest version you submit within the permitted submission period. Be sure to run the tests we’ve provided within MarkUs one last time before the due date. This will make sure that you didn’t accidentally submit the wrong version of your code, or worse yet, the starter code! How your assignment will be marked There will be no marks associated with defining your own test cases with pytest or hypothesis. The marking scheme will be approximately as follows:
欢迎咨询51作业君
