Step 1. Construct a text file that follows the input specifications of the problem, i.e. it can serve as a sample input. Specifically, you should give an input file representing a 10x10 patch. The patch should contain two or three islands, according to your choice. The shape of the islands can be arbitrary, but try to be creative. The text file should be of the form firstname-lastname.txt.
Notice that each cell in the patch is characterized by its coordinates. The top left coordinate is (0,0) and coordinate (i,j) is for the cell in the i-th row and j-th column.
Step 2. Write a function that reads an input file with the given specifications and returns the list of the coordinates of the land points, i.e. the list of coordinates for the ‘X’ points. Suppose now that the input is an m×n patch. This means that there are mn different coordinates.
Step 3. Write a function CoordinateToNumber(i,j,m,n) that takes a coordinate (i,j) and maps it to a unique number t in [0,mn−1], which is then returned by the function.
Step 4. Write a function NumberToCoordinate(t,m,n) that takes a number t and returns the corresponding coordinate. This function must be the inverse of CoordinateToNumber. That is, for all i,j,m,n we must have
NumberToCoordinate(CoordinateToNumber(i,j,m,n),m,n) = (i,j)
The two steps above mean that besides its coordinates, each cell has its own unique identity number in [0,mn−1]
Step 5. Write a function Distance(t1,t2), where t1 and t2 are the identity numbers of two cells, and the output is the distance between them. The distance is the minimum number of connected cells that one has to traverse to go from t1 to t2. (Hint: Use function NumberToCoordinate for this) Recall that in Step 2 of Milestone 1 we wrote a function for finding the list of land cells. Let’s call this function FindLandCells, and its output LandCell List. This list of land cells can look like this:
LandCell List = [10, 11, 25, 12, 50, 51, 80, 81, 82]
(this is only an example, it does not correspond to some specific input).
Now this lists can be further broken into islands. So, we have something that looks like this:
Island List = [[10, 11, 12], [25], [50, 51], [80, 81, 82]]
You see how all the cells from the original list appear in the second data structure, which is a list of lists, with each list being an island. Observe how cells belonging to the same island (e.g. cell 12), can be mixed up with other islands in LandCell List. In other words, one island’s cells do not have to be in contiguous positions in LandCell_List.
In this milestone, we will write functions to help find the list of islands.
Step 6. Write a function GenerateNeighbors(t1, n, m), that takes one cell number t1 (and also the dimensions), and returns the numbers for the neighbors of t1 in the grid. Notice that t1 can have 2, 3, or 4 neighbors.
Step 7. Write a function ExploreIsland(t1, n, m). This function should start from cell t1, and construct a list of cells that are on the same island as t1. (Hint: t1 can add itself to a dictionary representing the island, and also its neighbors, then the neighbors should recursively do the same. But when new neighbors are inserted in the dictionary, we should first check if they are already in it. The process should terminate when it’s not possible to add more cells to the dictionary, meaning that we found the island. Finally, the function should return a list with the cells on the island)
Step 8. Write a function FindIslands that reads the list LandCell List and converts its to Island List as explained above. The idea for this step is to scan the list of land cells and call repeatedly the ExploreIsland function
Step 9. Write a function Island Distance(isl1, isl2), which takes two lists of cells representing two islands, and finds the distance of these two islands. For this, you will need to compute the Distance function
Step 10. We will now construct a graph of islands. Consider an example of this. Suppose Island List contains 3 islands. We will assign to each island a unique number in [0, 3).
Then Island Graph will be a list of the following form:
[[0, 1, d(0, 1)], [0, 2, d(0, 2)], [1, 2, d(1, 2)]].
Here d(i, j) is the distance between islands i and j, as computed with the function in Step 9. In other words, for each pair of islands, we have a triple consisting of the identities of the pair, and their distance. This is a complete weighted graph. The goal of this Step is to write a function Island Graph that outputs this list.
Final Step. We now have a data structure which is the adjacency list (with weights) of the graphs. To connect all islands, we need to find a minimum-weight spanning tree for this graph. However, for this assignment, I will ask you to use the python library networkx.
Here is the documentation of a function that computes minimum-weight spanning trees.
https://networkx.github.io/documentation/networkx 1.10/reference/generated/networkx.
algorithms.mst.minimum_spanning_tree.html#networkx.algorithms.mst.minimum_spanning_ tree
The task in this final step will be to familiarize yourself with this documentation. Island Graph is a list that has all information needed, and it just needs a bit more work to convert it in the appropriate format that can be handled by networkx. So, your task will be to do this conversion, then run the MST function and find the tree. Finally, you should compute the total length (weight) of the edges in the tree, so that the question of the problem is answered.
Codersarts is a top-rated website for students which is looking for online Programming Assignment Help, Homework Help, Coursework Help in C, C++, Java, Python, Database, Data structure, Algorithms, Final year project, Android, Web, C sharp, ASP NET to students at all levels whether it is school, college and university level Coursework Help or Real-time project.
Hire us and Get your projects done by computer science expert
If you have project or assignment files, You can send at contact@codersarts.com directly
コメント