In the previous question we provided ponies for each segment. That is often not the case in real-world scenarios. 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)]

Hint

It would be a nice idea to use helper functions. For example, possible helper function(s) can (1) compare two assignments and decide which one is better, and/or (2) find the best pony allocation for a given move, etc. Split your logic into defined units, with individual functions for each section of logic!

Using helper functions (instead of having a very long and complicated main function) improves readability and makes your life easier.

You may want to use these helper functions in Q2, Q3 and in Project 2.

Allocation criteria are hierarchical, so we can represent an allocation's score as a tuple where component scores are enumerated in (descending) order of priority.

If you choose to create allocation scores in this way, youll be able to use Pythons built-in comparison operators like <, , >, to determine which score is superior. A tie-resolution decision procedure will be properly implemented by the operators.

Consider two tuples (a1, b1, c1) and (a2, b2, c2). An operator (a1, b1, c1) > (a2, b2, c2) will return True if a1 > a2 regardless of b1, c1, b2, c2 values. Otherwise, if a1==a2, it will consider b1 and b2. If b1 > b2, it will return True; otherwise, if b1==b2, it will proceed to compare c1 and c2. If c1 > c2, it will return True; otherwise, its result will be False.