You are to write a function build_pq(current_pos, goal_pos, matrix), where:

• current_pos is Eve's current coordinate in form (x, y);
• goal_pos is the goal coordinate in form (x, y);
• and matrix is the nested list representation you should be familiar with from Project 1.

The function should use the heuristic function defined from Question 1 to score all possible coordinates the turtle can visit from current_pos. Your function should then return:

• a list of tuples;
• where each tuple includes the coordinate to visit and the heuristic score for that coordinate.

The returned list should be sorted in reverse score order (descending order). That is, the tuple with the highest scoring coordinate should be the first element in the list. If a tie occurs, then precedence is given to the larger coordinate (x and then y). For example:

• If (0,0) and (0,1) were tied for scores, then (0,1) should precede (0,0).
• If (1,0) and (0,1) were tied for scores, then (1,0) should precede (0,1) as the x value is larger. This tie breaking system is only for this question.

A correct implementation of heuristic_score has been provided for you to use. The heuristic_score function takes in next_pos (next coordinate), goal_pos (goal coordinate), and a score (matrix score for the next_pos). If you wish to use your own, you may remove the import.

For this question, you may assume the following:

• You can assume that the input arguments are syntactically correct given the definitions, and will always be non-empty.
• current_pos and goal_pos will always both exist within the matrix, and will never be on the same coordinate.
• You can assume the grid passed through as matrix will always have dimensions 22 or greater.
• Remember, Eve can move in all 8 directions now!

Remember that this is an assessment task, and the work must be your own. It is illegal for others to do this work on your behalf.

Here are example calls to your function:

>>> build_pq((0,0),(2,2), [[0,150,-10],[100,0,20],[1,1000,-10]])

[((1, 0), -150), ((1, 1), -200), ((0, 1), -200)]

>>> build_pq((1,1),(2,2), [[0,1000,-10],[100,0,1000],[1,1000,-10]])

[((2, 1), 900), ((1, 2), 900), ((1, 0), 700), ((2, 2), -10), ((0, 2), -199), ((0, 1), -200), ((2, 0), -210), ((0, 0), -400)]

>>> build_pq((2,2),(0,0), [[1000,1000,-10],[100,0,1001],[1,1000,0]])

[((2, 1), 701), ((1, 2), 700), ((1, 1), -200)]

python