The file m269_tyre_shop.py implements the tyre shop dictionary as a class, TyreShop, and adds the following methods:

• add_stack (to add a given stack name to the dictionary)
• add_tyre (to add a given tyre diameter to a given stack name if possible and return success or failure)
• remove_tyre (to remove the top tyre from a given stack name, returning the diameter of the tyre removed)
• check_tyre (to return the diameter of the top tyre of the stack with the given stack, without removing it from the stack)
• is_empty (to return a Boolean indicating whether a stack is empty or not)
• top_tyres (returns a dictionary of stack names mapped to the top tyre diameters)
• get_stack_height (returns an integer height of a given stack name)
• show (a helper method to print out a visible representation of the stacks. This may help you in debugging!)

Jo is now considering the process of searching for exisiting tyres in the stacks.

As Jo always tries to put tyres on the most suitable stack, they assume that the tyre they are searching for is most likely to be in the stack(s) with the closest diameter top tyre, as long as that diameter is either equal to or smaller than the tyre being searched for.

Complete the Python function below which returns a list of stacks that a given tyre could be in. The list should be ordered so that the most likely stack is first and the least likely stack should be last. If it is not possible for the tyre to be in a stack, then that stack should not be included.

You should use at least one appropriate divide and conquer technique in answering this question. You should implement your own sorting technique rather than using any existing Python methods.

You can use the tests below to help check if your code is working. NOTE that failing the tests is a clear indication your code is faulty, but passing the tests is NOT a guarantee it is correct. Your tutor may run additional tests.

%run -i m269_tyre_shop #Tyre shop class %run -i m269_tyre_shop_test_data #Test data for your function %run -i m269_util #Utilities for testing data

def get_stacks_to_search(shop_to_search: TyreShop, tyre_to_find: int) -> list:

test_table = [ ['150',tyreshop,150,[('A', 190), ('B', 200), ('D', 400), ('E', 400), ('F', 400), ('G', 400)]], ['450',tyreshop,450,[]], ] test(get_stacks_to_search, test_table) #Ensure the function name in this line matches your function.