Question: Oh no ! Your pet sloth has managed to get itself lost in some hilly grasslands. It needs to make its way across this area

Oh no! Your pet sloth has managed to get itself lost in some hilly grasslands. It needs to make its way across this area to get back to its home in the forest. Since sloths aren't so great at crawling on hills, it needs to conserve as much energy as possible. Fortunately, your sloth is well-versed in computer science and also has access to GPS data on the elevation of the area.
We will model the grasslands as a grid of elevations, stored in a rectangular 2D list of int values. Your sloth starts somewhere on the western edge of this grid, and its objective is to travel to the eastern edge where the forest lies. The sloth moves west to east one column at a time. The sloth wants to make constant progress towards the eastern edge, so it always chooses to move northeast, east, or southeast. It picks the direction that minimizes its energy usage, which is calculated like this:
If the sloth is moving from a lower elevation L to a higher elevation H, its energy usage is 5(H-L),
If the sloth is moving from a higher elevation H to a lower elevation L, its energy usage is just H-L(after all, it has gravity on its side).
If the sloth is moving from one elevation to the same elevation, its energy usage is 3.
If two or more directions have the same energy usage, it chooses the northernmost one (i.e., northeast is prioritized over east, and east is prioritized over southeast). Note that if the sloth is on the northern or southern edge of the grasslands, either the northeast or southeast direction is no longer an option.
For example, suppose the grasslands elevations are given by the 2D list below:
\table[[4,4,0,9,8],[4,6,5,-3,6],[5,5,4,5,9],[7,1,6,6,0]]
The sloth always starts from the western edge (i.e., column 0 of the list). Suppose the sloth starts from row 3, column 0. This is the lower left corner of the grid, where the elevation is 7.
From row 3, column 0, it must choose to go NE(elevation 7 to 5, energy usage: 7-5=2), or E(elevation 7 to 1, energy usage: 7-1=6). NE has the lowest energy usage, so the sloth moves northeast to row 2, column 1.
From row 2, column 1, it must choose to go NE (elevation 5 to 5, energy usage: 3),E(elevation 5 to 4, energy usage: 5-4=1), or SE (elevation 5 to 6, energy usage: 5(6-5)=5. E has the lowest energy usage, so it moves east to row 2, column 2.
From row 2, column 2, it must choose to go NE (elevation 4 to -3, energy usage: 4-(-3)=7),E(elevation 4 to 5, energy usage: 5(5-4)=5), or SE (elevation 4 to 6, energy usage: 5(6-4)=10. E has the lowest energy usage, so it moves east to row 2, column 3.
From row 2, column 3, it must choose to go NE (elevation 5 to 6, energy usage: 5(6-5)=5),E(elevation 5 to 9, energy usage: 5(9-5)=20), or SE(elevation 5 to 0, energy usage: 5-0=5.NE and SE are tied for lowest energy usage. The sloth chooses the northernmost of the tied directions, so it moves northeast to row 1, column 4.
The sloth reaches the forest as soon as it gets to any point in the last column, so we're now done. Yay!!
Create a Python file named lost_sloth.py. Within that file, write a function find_path(data, starting_row). The parameter data is a 2D list of int elevation values; the parameter starting_row is the index of the sloth's starting row on the western edge. Assume the list is rectangular and non-empty, and the starting row is a valid row in the list. The function returns a list containing the indices of the rows of the sloth's path as it moves from west to east, according to the previously described algorithm.
For example, if data is a 2D int list containing the data above, then calling find_path(data,3) should return the list 3,2,2,2,1.
Oh no ! Your pet sloth has managed to get itself

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!