question 1

Implement this shortest path between nodes algorithm as a function in Python. Include a docstring. We have provided the reverse_in_place() code as given in the answer to Exercise 4.7.7. Make sure that your function inputs are in the order warehouse, start, end.

Test your implementation by running the test code given below. If any tests fail, then debug your implementation and run the test code again. You can repeat this iterative process as many times as you want. If there are any tests that fail and you are unable to identify the problem, you may add explanatory comments below the test code.

%run -i m269_util # The reverse_in_place code appears in Exercise 4.7.7 answer def reverse_in_place(values: list) -> None: """Reverse the order of the values.

Postconditions: post-values = [pre-values[len(pre-values) - 1], ..., pre-values[1], pre-values[0]] """ left_index = 0 right_index = len(values) - 1 while left_index

# Write your function code here

# Test code shortest_path_tests = [ # case, warehouse, start, end, shortest path ('neighbouring zones', warehouse, 'S', 'Y', ['S','Y']), ('zone neighbouring despatch', warehouse, 'despatch', 'D', ['despatch','D']), ('zone neighbouring despatch shortest path not direct', warehouse, 'despatch','Z', ['despatch','D','Z']), ('distant zones', warehouse, 'U', 'D', ['U','A','despatch','D']), ('distant zones opposite direction', warehouse, 'D', 'U', ['D','despatch','A','U']), ('two different shortest paths, choice depends on dijkstra', warehouse, 'Z', 'P', ['Z','D','P']), ] test(shortest_path, shortest_path_tests) # Add any explanatory comments here

QUESTION 2

For this example, the trail ends at the leaves of the tree, that is, D, E, F and G.

Given a trail represented by a rooted tree, trail, write a recursive function called ends that calculates the number of points at which a trail ends. For the example above, this would return 4.

Test your function by running the test code given below. If any tests fail, then debug your function, and run the test code again. You can repeat this iterative process as many times as you want. If there are any tests that fail and you are unable to identify the problem, you may add explanatory comments below the test code.

%run -i m269_tree %run -i m269_util # Compute the number of trail ends in trail # Write your recursive function here

# Test code EMPTY = Tree() F = join('F',EMPTY,EMPTY) G = join('G',EMPTY,EMPTY) C = join('C',F,G) D = join('D', EMPTY,EMPTY) A = join('A',C,D) E = join('E',EMPTY,EMPTY) B = join('B',E,EMPTY) START = join('START',A,B)

trail_tests = [ # case, trail, number of trail ends ('empty tree', EMPTY, 0), ('no subtrees, already trail end', F, 1), ('one subtree, trail end', B, 1), ('two subtrees, neither subtree is a trail end', START, 4), ('two subtrees, one subtree is a trail end', A, 3), ('two subtrees, both subtrees are trail ends', C, 2) ] test(ends, trail_tests) # Add any explanatory comments here

Question 3

Design an algorithm to implement the filter candidates function. You can call the colours and positions auxiliary functions. Ensure your filtered sequence is sorted in ascending order.

1.Let filtered be an empty list: 2.Iterate through the list of candidates. 3.For each candidate, use the colours and positions auxiliary functions to compare it to the given guess. 4.If the number of correct colours and right positions for the candidate match the given colours and positions values, add the candidate to the filtered list. 5.Sort the filtered list in ascending order. 6.Return the filtered list.

Complete the Python code to implement your filter candidates algorithm. Run the test code to test your implementation.

%run -i m269_util def filter_candidates(guess:tuple, col:int, pos:int, candidates:list) -> list: """ Preconditions: - guess is a sequence of four unique colours chosen from R, O,Y, G, B, V; - 0 # Write your code here

# Test code

# Test code filter_tests = [ # case, guess, col, pos, candidates, filtered space ('random guess', ('R','B','O','G'), 3, 2, candidates, [('B', 'V', 'O', 'G'), ('B', 'Y', 'O', 'G'), ('G', 'B', 'O', 'V'), ('G', 'B', 'O', 'Y'), ('O', 'B', 'V', 'G'), ('O', 'B', 'Y', 'G'), ('R', 'B', 'G', 'V'), ('R', 'B', 'G', 'Y'), ('R', 'B', 'V', 'O'), ('R', 'B', 'Y', 'O'), ('R', 'G', 'O', 'V'), ('R', 'G', 'O', 'Y'), ('R', 'O', 'V', 'G'), ('R', 'O', 'Y', 'G'), ('R', 'V', 'B', 'G'), ('R', 'V', 'O', 'B'), ('R', 'Y', 'B', 'G'), ('R', 'Y', 'O', 'B'), ('V', 'B', 'O', 'R'), ('V', 'B', 'R', 'G'), ('V', 'R', 'O', 'G'), ('Y', 'B', 'O', 'R'), ('Y', 'B', 'R', 'G'), ('Y', 'R', 'O', 'G')]), ('close guess',('O','B','Y','R'), 3, 3, candidates, [('G', 'B', 'Y', 'R'), ('O', 'B', 'G', 'R'), ('O', 'B', 'V', 'R'), ('O', 'B', 'Y', 'G'), ('O', 'B', 'Y', 'V'), ('O', 'G', 'Y', 'R'), ('O', 'V', 'Y', 'R'), ('V', 'B', 'Y', 'R')]), ('correct guess',('O','B','Y','G'), 4, 4, candidates, [('O', 'B', 'Y', 'G')] ) ]

test(filter_candidates, filter_tests)

START