In this question, we will write a function to assign ponies for each segment on the path provided.

The function should find the best allocation according to the following criteria:

(the main optimization criterion) 1. Assignment is superior if it has lower total unused pony capacity

(an extra heuristic to resolve a tie at criterion 1) 2. Smaller differences between the capacity of two assigned ponies are preferred

[Used in Q3 only] (an extra heuristic to resolve a tie at criterion 2) 3. If moves are different, prefer the one with greater elevation raise

[Used in Q3 only] (an extra heuristic to resolve a tie at criterion 3) 4. Prefer moves into lower value (x,y) coordinates

Here "lower" means (x1,y1)<(x2,y2). The last criterion is used to make our solutions more deterministic.

Write a function assign_pony_to_path(elevations, path, 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

path a list of tuples, each tuple provides (x,y) coordinates for each path segment to take the trolley on. Should start with (0,0) and finish at (M,N)

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

The function should return a list assignments a list of assignments (tuples) for each pair of ponies to a path segment.

If there are two possible ways to create a pony pair, then use the one with the smaller value first. For example, if (37, 73) and (73, 37) are both valid pairs, then keep (37, 73).

You may assume all inputs are well-formatted.

>>> pony_capacities = [17, 37, 73] >>> journey_path = [(0,0), (0,1), (0,2), (0,3), (1,3), (1,4), (1,5)] >>> pony_assignments = [(73, 73)] * 6 >>> village_elevations = [[ 100, 200, 300, 400, 100, 600], [0, 100, 200, 300, 400, 500 ]] >>> lower_village_elevations = [[ 10, 20, 30, 40, 10, 60], [0, 10, 20, 30, 40, 50 ]] >>> assign_pony_to_path(village_elevations, journey_path, pony_capacities) [(37, 73), (37, 73), (37, 73), (17, 17), (37, 73), (37, 73)] >>> assign_pony_to_path(lower_village_elevations, journey_path, pony_capacities) [(17, 17), (17, 17), (17, 17), (17, 17), (17, 17), (17, 17)] >>> another_journey_path = [(0,0), (1,0), (1,1), (1,2), (1,3), (1,4), (1,5)] >>> assign_pony_to_path(village_elevations, another_journey_path, pony_capacities) [(17, 17), (37, 73), (37, 73), (37, 73), (37, 73), (37, 73)] >>> impossible_journey_path = [(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (1,5)] >>> assign_pony_to_path(village_elevations, impossible_journey_path, pony_capacities) [(37, 73), (37, 73), (37, 73), (17, 17), None, (17, 17)]