The files mentioned in the text are shared in the comment, thanks!

Overview Mamr problems in computer science and in engineering are solved on a two dimensional numerical grid using techniques that are varioust called \"gradient ascent\" [or \"descent\"), greedy search, or hill-climbing. We are going to study a simplied version of this using hand-generated elevation data. The main representation we need is a list of lists of \"heights\" [also called \"elevations", but we will use the simpler term \"heights\" here). For exampic, grid = [[15, 1e, 1e, 19, 12, 11], [13, 19, 23, 21, 16, 12], [12, 15, 17, 19, 22, 10], [10, 14, is, 13, s, 6]] has four lists of six integer entries each. Each entry represents an height e.g. meters above sea. level and the heights are measured at regularly-spaced intervals, which could be as small as centimeters or as large as kilometers. The USGS, United States Geological Survey, maintains and distributes elevation data like this, but private companies do so as well. Such data are important for evaluating water run-o', determining placement of wind turbines, and planning roads and construction, just to name a few uses. We are going to use the analogy.r of planning hiking paths on a plot of land. Questions we might ask about this data include, 1. What is the highest point [greatest height)? This is also called the uglobal maximum\" because it is the greatest value in the data. in our example, this height value is 23 and it occurs in list 1, entry 2. We will refer to this as row 1, coiumn 2 (or \"col 2\"), and write these values as a tuple, {1, 2), where we assume the rst value is the row and the second is the column. We refer to (l, 2) as a \"location". 2. Are there \"local maxima" in the data? These are entries whose value is greater than their immediately surrounding values, but smaller than the global maximum. In our example there is a local maxima of 22 at location (2, 4). 3. Starting at a given location, what is the best path to the global maxima? This is a tricky question because we need to define "best path". Here is a simple one: can we start at a given location and only take the steepest route and get to the global maximum (can we hike up to the "peak" )? For example, if we start at (3, 0) then the path through locations (3, 0), (3, 1), (3, 2), (2, 2), (1, 2) follows the steepest route and reaches the top. This is a "gradient ascent" method. But, if we start at location (3, 5) then we will generate the route (3, 5), (3, 4), (2, 4), but then there is no way to continue up to reach the global maximum. There are many, many more questions that we can ask and answer. Some of them can be solved easily, while others require sophisticated algorithms and expensive computations. Before getting started on the actual assignment, it is important to define the notion of a "neighbor" location in the grid - one that we are allowed to step to from a given location. For our purposes, from location (r, c), the neighbor locations are (r-1, c), (r, c-1), (r, c+1), and (r+1, c). In other words, a neighbor location must be must be in the same row or the same column as the current location. Finally, neighbors can not be outside the grid, so for example at location (r, 0) only (r-1, 0), (r, 1), (r+1, 0) are allowed as neighbors, Getting Started Please download hw5_files. zip and place all the files in the same folder that you are going to write your solutions. Files hw5_util . py and hw5_grids. txt are quite important: hw5_util. py contains utility functions to read grids and starting locations from hw5_grids . txt. In particular, . hw5_util. num_grids() returns the number of different grids in the data, . hw5_util. get_grid(n) returns grid n, where n==1 is the first grid and n == hw5_util. num_grids() is the last. . hw5_util. get_start_locations(n) returns a list of tuples giving one or more starting lo- cations to consider for grid n, . hw5_util. get_path (n) returns a list of tuples giving a possible path for grid n. We suggest you start by playing around with these functions and printing out what you get so that you are sure you understand. You may assume the following about the data: 1. The grid has at least two rows. 2. Each row has at least two entries (columns) and each row has the same number of columns. 3. All heights are positive integers. 4. The start locations are all within the range of rows and columns of the grid. 5. The locations on the path are all within the range of rows and columns of the grid.Part 1 Write a python program, hw5_parti . py that does the following: 1. Asks the user for a grid number and loops until one in the proper range is provided. Denote the grid number as n. 2. Gets grid n 3. Asks the user if they want to print the grid. A single character response of 'Y' or 'y' should cause the grid to be printed. For anything else the grid should not be printed. When printing, you may assume that the elevations are less than 1,000 meters. See the example output. 4. Gets the start locations associated with grid n and for each it prints the set of neighbor locations that are within the boundaries of the grid. For example if grid n has 8 rows and 10 columns, and the list of start locations is [(4, 6), (0, 3), (7, 9)] then the output should be Neighbors of (4, 6): (3, 6) (4, 5) (4, 7) (5, 6) Neighbors of (0, 3): (0, 2) (0, 4) (1, 3) Neighbors of (7, 9) : (6, 9) (7, 8) Very important: we strongly urge you to write a function called get_nors that takes as parameters a row, col location, together with the number of rows and columns in the grid, and returns a list of tuples containing the locations that are neighbors of the row, col location and are within the bounds of the grid. You will make use of this function frequently. 5. Gets the suggested path, decides if it is a valid path (each location is a neighbor of the next), and then calculates the total downward elevation change and the total upward elevation change. For example using the grid above, if the path is (3, 1), (3, 0), (2, 0), (1, 0), (1, 1), (0, 1), (0, 2), (1, 2) the downward elevation changes are from (3, 1) to (3, 0) (change of 4) and from (1, 1) to (0, 1) (change) of 3 for a total of 7, and the upward elevation changes are from (3, 0) to (2, 0), from (2, 0) to (1, 0), from (1, 0) to (1, 1), from (0, 1) to (0, 2) and from (0, 2) to (1, 2) for a total of (2 + 1 + 6 + 2 + 5) = 16). The output should be: Valid path Downward 7 Upward 16 If the path is invalid, the code should print Path: invalid step from pointl to point2. Here point1 and point2 are the tuples representing the start and end of an invalid step. Submit just the file hw5_part1. py and nothing else.Part 2 Revise your solution to Part 1 and submit it as hs'5_part2.pr. The program should again ask the user for the grid number, but it should not print the grid. Next, it should nd and output the location and height of the global maximum height. For example for the simple example grid. the output should be global max: (1. 2) 23 You may assume without checking that the global maxiJJmm is unique. The main taskofPart2 is tondandoutput twopatbsfromeacbstartlocationir the grid. The rst is the steepest path up. and the second is the mostgradual pathup. The stepsoneacb path must be between neighboring locations as in Part 1. Also, on each path no steps to a location atthesameheightorlowerarealhwnd.andthstepsizeheohangeinheightloanbenomore than a maximum step height [difference between heights at the new location and at the current location}. Your code must ask the user for the value of this maximum step height. Next. determine For Bali path if it mocha the location of the global maximum height in the grid. a local maximum. or neither. The latter can happen at a location where the only upward steps are too high relative to the height at the current location. Of course, true hiking paths can go both up and down. but nding an \"optimal path'1 in this more omnplicated situation requires mum more Euphisticntod algorithms than we are ready to develop here. Assnexampleofthereqmredresults.hereisthesamegridssahow: grid - [[15, 15. 13. 19. 12. 11]. [13, 1s. 23. 21. 1e. 12]. [12, 15. 17. 19, 20. 10]. [1a. 14. 1s. 13. a. 6]] starting at location {3. [I] with a maximum height change ol' 4. the steepest path is (3, [I], {3. l}. {3. 2). (2. 2}. (2. 3]. (l. 3). [1. 2]. while the most gradual path is {3. [I]. {2. 0]. {1. ll). {0. U}. [I]. l}. (0.2].{01 3), {1,3}. (1.2}. Both reach the global maximum. and both avoid stepping to the global maximum the rst time theyr are close because the step height is too large. Note that both the steepest and most gradual paths from location [3. 5} would end at thel local maximum {2, t]. The steepest path would end alter four steps (ve locations on the path] and the most gradual would end after six steps {sewn locations on thel path]. If the max step height were only 3. then both paths from {3, 5] would stop at locationi. 4} before no},' maximum is readied. Paths should he output with 5 locations per line. for example stoop-eat path (3. OJ (2. U] (1. ] {0. {1} (CI. 1) (O. 2) (0. 3] (1. 3] (1. 2) global noxious See the mmplo output for further details. Finally, if requested by the user. outwit a grid we'll call it the I'path grid\" - giving at each location the number of paths that include that location. This can be handled by ion-min; a new list of lists, where each entry represents a count initialized to 0. For each path and for each location (1. j) on the path. the appropriate count in the list of lists should he incremented. At the end. after all paths have been generated and added to the counts, output the grid. In this output, rather than printing a 0 for a locations that are not on any path, please output a ' . '; this will make the output clearer. See the example output. Notes 1. In deciding the choice of next locations on a path, if there is a tie, then pick the one that is earlier in the list produced by your get_nors function. For example starting at (0, 5) with elevation 11 in the above example grid, both (0, 4) and (1, 5) have elevation 12. In this case (0, 4) would be earlier in the get_nors list and therefore chosen as the next location on the path. 2. Please do not work on the path grid output - the last step - until you are sure you have everything else working. 3. Both the most gradual and steepest paths are examples of greedy algorithms where the best choice available is made at every step and never reconsidered. More sophisticated algorithms would consider some form of backtracking where decisions are undone and alternatives recon- sidered