DisjointSet Class Implementation of this class is done in a1_partc.py A DisjointSet class represents a disjoint set which is a set of sets where every element can only belong to exactly one set. When a DisjointSet class is instantiated it is passed nothing and contains no sets. It make an empty Python dictionary which will be used to store the elements of the DisjointSet. The DisjointSet has the following member functions: def make_set(self,element) If element already exists within the Disjoint set, the function does nothing and returns false. If element does not exist in the DisjointSet, this function will add it to the DisjointSet by: make a new SetList object containing only one node, with the element as only value in the SetList adding a new dictionary entry where element is the key and a reference to the node containing element as the value return true Suppose we ran the following code: ds = DisjointSet() ds.make_set("cat") ds.make_set("dog") ds.make_set("fish") The following is what we would make: def find_set(self, element) Function returns the representative of the set containining element. def get_num_sets(self) This function returns the number of sets in the DisjointSet. Note that this is not the same as the number of elements. You can start with 2 elements in unique sets and join them using the union_set() function. def __len__(self) This function returns the number of elements in the DisjointSet. def get_set_size(self, element): This function returns the size of the set containing element. If element does not exist within the disjoint set, function returns 0 def union_set(self, element1, element2) Function performs a union of the two sets containing element1 and element2 respectively. If the two elements are already in the same set or if either of the elements do not exist, function does nothing and returns false. otherwise perform a union on the two sets, make one set and return true Example, suppose we ran the following code: ds = DisjointSet() ds.make_set("cat") ds.make_set("dog") ds.make_set("fish") ds.union_set("cat","dog") Our DisjointSet would look like: Maze Runner Function Implementation of this function is done in a1_partd.py We describe a maze as having row x col cells. For example if row was 3, and col was 4, then we would have a grid of cells as follows. We describe a wall by the two cell numbers the wall separates. If every single wall existed, there would be (row-1)(col) + (col-1)(row) walls. Note please provide solution and output
Types of Linked List
A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.
Linked List
When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).
DisjointSet Class
Implementation of this class is done in a1_partc.py
A DisjointSet class represents a disjoint set which is a set of sets where every element can only belong to exactly one set.
When a DisjointSet class is instantiated it is passed nothing and contains no sets. It make an empty Python dictionary which will be used to store the elements of the DisjointSet.
The DisjointSet has the following member functions:
def make_set(self,element)
If element already exists within the Disjoint set, the function does nothing and returns false.
If element does not exist in the DisjointSet, this function will add it to the DisjointSet by:
- make a new SetList object containing only one node, with the element as only value in the SetList
- adding a new dictionary entry where element is the key and a reference to the node containing element as the value
- return true
Suppose we ran the following code:
ds = DisjointSet() ds.make_set("cat") ds.make_set("dog") ds.make_set("fish")
The following is what we would make:
def find_set(self, element)
Function returns the representative of the set containining element.
def get_num_sets(self)
This function returns the number of sets in the DisjointSet. Note that this is not the same as the number of elements. You can start with 2 elements in unique sets and join them using the union_set() function.
def __len__(self)
This function returns the number of elements in the DisjointSet.
def get_set_size(self, element):
This function returns the size of the set containing element. If element does not exist within the disjoint set, function returns 0
def union_set(self, element1, element2)
Function performs a union of the two sets containing element1 and element2 respectively. If the two elements are already in the same set or if either of the elements do not exist, function does nothing and returns false. otherwise perform a union on the two sets, make one set and return true
Example, suppose we ran the following code:
ds = DisjointSet() ds.make_set("cat") ds.make_set("dog") ds.make_set("fish") ds.union_set("cat","dog")
Our DisjointSet would look like:
Maze Runner Function
Implementation of this function is done in a1_partd.py
We describe a maze as having row x col cells. For example if row was 3, and col was 4, then we would have a grid of cells as follows. We describe a wall by the two cell numbers the wall separates. If every single wall existed, there would be (row-1)(col) + (col-1)(row) walls.
Note please provide solution and output
![0 | 1 | 2 | 3
4 | 5 | 6 | 7
8 | 9 | 10 | 11
A Maze class (which you do not need to implement) describes a maze as mentioned above. This class is defined in
maze.py. It has methods that you can use to travel through the maze (i.e. figure out where you are, find a neighbour
cell etc.)
use a recursive maze runner function:
def find_path(maze, from_cell, to_cell);
The find_path function will find a path from cell number from_cell to cell number to_cell and will return it as a list
containing all the cell numbers along the path, from the from_cell to the to_cell.
You are allowed to use this function as a wrapper to a recursive function that does the work, allowing for other
arguments to your function prototype or additional processing. However, the function that does the work to find the
path must be recursive.
For example, suppose the from_cell was O and the to_cell was 3, using the maze below:
0 | 12 3
4
‒‒‒‒
5 6 7
8 9 10 | 11
The find_path function would return this path: [0, 4, 5, 1, 2, 3].
Online visualizer
To help you debug your program, when you run the tester, the tester will make a "path" file based on the path your
find_path function generates (its return values.) You can see what is happening by going to this site:
Online Visualizer
• Use the radio buttons to select the test in question (see your error message.)
Then, load the corresponding testpath file.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa5602bda-7b39-4a2b-a1a8-06efc64b3411%2Fd5336488-caf3-467d-bdda-249d12a9fbee%2Feume0l_processed.png&w=3840&q=75)
Step by step
Solved in 4 steps
