Plase write it in Python programinmg.

start up code

from puzzle import Puzzle

class PuzzleDP(Puzzle):

def distances(self, end): rev = self.reverse() tovisit = {end} visited = set() dist = {end: 0} d = 1 while tovisit: # Add all the tovisit positions to the visited set. visited.update(tovisit) # set s to be the set of positions that can reach the tovisit set. # Be sure to leave out those positions that were already visited. s = set.union(*(rev[p] for p in tovisit)) - visited # Update the distances to all the positions in s dist.update({p:d for p in s}) # The set s is the next set to visit. tovisit = s # update the distance. d += 1 return dist

HW 05: A Maze without Walls (part 2) In this homework, we will extend our code from the lab to make it do a couple more tricks including the ability to solve it with dynamic programming. We will write a new class PuzzleDP that will extend our class from the homework. Put the new class in a file called puzzle_dp.py. For your submission, be sure to zip together both your puzzle.py file and also puzzle_dp.py Find the path In the lab, we used recursion to find if a path exists from start to end in the puzzle. Now, we're going to write a new method called pathsolve that returns a valid path from start to end. The code will work mostly like the code from the lab. The tricky part is to understand how the path is constructed as the recursive calls return. As it is quicker to append to a list, you can append the current state to the list as you return from recursive calls and reverse the final list. The other possibility is to use a deque. Python has an efficient, built-in deque data structure that supports adding to the front with a method called appen dleft.Don't forget to import it: from collections import deque Begin from the end A classic trick for solving a maze is to start from the end and work backwards. It's a little tricky to do this with this puzzle, because one square can be reached by many other squares Write a method called reverse that returns a dictionary mapping positions (row,column)-tuples) to sets of positions that can reach that position. Using this dictionary, it will be possible to find paths by going backwards. Find distances using dynamic programming Now, we're going to modify our old approach to remove the recursion entirely. Here's the idea. We're going to build a table of solutions that is like the original puzzle grid, but each entry stores the distance to the end, After we have filled up the whole table, we will be able to quickly return the HW 05: A Maze without Walls (part 2) In this homework, we will extend our code from the lab to make it do a couple more tricks including the ability to solve it with dynamic programming. We will write a new class PuzzleDP that will extend our class from the homework. Put the new class in a file called puzzle_dp.py. For your submission, be sure to zip together both your puzzle.py file and also puzzle_dp.py Find the path In the lab, we used recursion to find if a path exists from start to end in the puzzle. Now, we're going to write a new method called pathsolve that returns a valid path from start to end. The code will work mostly like the code from the lab. The tricky part is to understand how the path is constructed as the recursive calls return. As it is quicker to append to a list, you can append the current state to the list as you return from recursive calls and reverse the final list. The other possibility is to use a deque. Python has an efficient, built-in deque data structure that supports adding to the front with a method called appen dleft.Don't forget to import it: from collections import deque Begin from the end A classic trick for solving a maze is to start from the end and work backwards. It's a little tricky to do this with this puzzle, because one square can be reached by many other squares Write a method called reverse that returns a dictionary mapping positions (row,column)-tuples) to sets of positions that can reach that position. Using this dictionary, it will be possible to find paths by going backwards. Find distances using dynamic programming Now, we're going to modify our old approach to remove the recursion entirely. Here's the idea. We're going to build a table of solutions that is like the original puzzle grid, but each entry stores the distance to the end, After we have filled up the whole table, we will be able to quickly return the