In this question we are neither provided with a path nor an assignment of ponies. Our task is to get the trolley from the initial point (0,0) to the final point (M,N). Recall that the final point (M,N) is at the corner, that is, M and N are the maximum values that x and y can take.

Try choosing the path step direction and pony assignment at each time step, one at a time, starting from the initial point (0,0).

Specifically, you will need to use a greedy algorithm. Greedy algorithms make the best available choice at each step, regardless of whether that choice leads to the overall optimal solution. You can see more info here. As an example, you want to buy a 12-dollar meal using the smallest number of coins, and the available coins are 5-dollar, 4-dollar and 1-dollar coins. What would you do? The optimal solution would be to use three 4-dollar coins. But if youre using a greedy algorithm, you will select coins one at a time and always select the coin with the largest value you will select a 5-dollar coin, another 5-dollar coin, a 1-dollar coin, and then another 1-dollar coin, resulting in using 4 coins total instead of just 3.

The greedy algorithm that we will use for this question works in a similar way to the coin problem: At each location (x, y), we consider either moving to the next location (x+1, y) or (x, y+1). We choose the move by comparing the four criteria (described below) for the two possible next locations. Then we repeat the same procedure until the final destination cell is reached. For example, at (0,0), we first choose to go to (0,1) because it is better than (1,0) based on the four criteria. Then from (0,1), we choose to go to (0,2); then we go to (1,2) from (0,2) until we reach (M,N).

Similar to the previous question, the following criteria should be used (make sure you follow the order):

Assignment is superior if it has lower total unused pony capacity

Prefer smaller differences between the capacity of two assigned ponies

If moves are different, prefer the one with greater elevation raise

Prefer moves into lower(x,y) coordinates

Apply the first rule and, if some move assignments are preferrable based on the first rule, adopt this decision. If some move assignments tie in the first rule, we proceed to the next rule, and so on. Check the details in Q2.

Write the function find_path_greedy(elevations, capacities)

Arguments:

elevations - a list of rows, where each row is a list of cells, each cell (village) is provided with its absolute elevation level

capacities a list of elevations by which every pony can pull the trolley

The function should return a tuple with path and assignments. The structure of variables should be consistent with that in previous questions. It is possible that no allocation exists for some point on the path. In the example image:

Figure 2

No allocation exists for the next move at the location (5,5). In this case, we return the partial assignments and partial path (i.e. the path is [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5), (5, 5)] in this example) until the location where we get stuck.

>>> pony_capacities = [17, 37, 73]

>>> journey_path = [(0,0), (0,1), (0,2), (0,3), (1,3), (1,4), (1,5)]

>>> village_elevations = [[ 100, 200, 300, 400, 100, 600], [0, 100, 200, 300, 400, 500 ]]

>>> path, assignment = find_path_greedy(village_elevations, pony_capacities)

>>> path

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (1, 4), (1, 5)]

>>> assignment

[(37, 73), (37, 73), (37, 73), (17, 17), (37, 73), (37, 73)]