PLEASE ANSWER THIS AS A NEW QUESTION AND DO NOT COPY AND PASTE AN OLD ANSWER.

In this question we consider a code-breaking game in which a player has to guess a hidden code.

The hidden code is an ordered sequence of 4 unique colours, chosen from 6 colours R, O, Y, G, B, V, which stand for Red, Orange, Yellow, Green, Blue and Violet.

For each guess, the player is told how many colours are correct and how many are in the right position.

For example, if the hidden code is OBYG and the player guesses RBOG, then three colours (O, B and G) are correct and two (B and G) are in the right position.

There are 6 5 4 3 = 360 different possible codes. (6 choices for the first colour, 5 remaining choices for the second colour, 4 remaining choices for the third colour, 3 remaining choices for the fourth colour.)

We can generate the search space of all 360 candidates as follows:

from itertools import permutations candidates = [] for permutation in permutations({'R','O','Y','G','B','V'}, 4): candidates.append(permutation) candidates.sort()

where permutations({'R', 'O', 'Y', 'G', 'B', 'V'}, 4) returns all possible arrangements of 4 elements taken from the set {'R', 'O', 'Y', 'G', 'B', 'V'}. Note that candidates have been sorted to ensure consistent results.

len(candidates) # = 360

We can filter the search space of candidates by selecting all those that match the guess in that they have the same number of colours correct and the same number in the right position. For example, if our guess has three correct colours and two are in the right position, then the filter would return allpossible combinations that have three correct colours with two in the right position.

We will use some auxiliary functions.

The auxiliary function colours finds the number of correct colours in guess.

def colours(guess:tuple, hidden:tuple) -> int: """ Preconditions: - guess is a sequence of four unique colours chosen from R, O, Y, G, B, V; - hidden is a sequence of four unique colours chosen from R, O, Y, G, B, V; Postconditions: output is number of correct colours in guess """ correct = 0 for colour in ('R','O','Y','G','B','V'): if colour in guess and colour in hidden: correct = correct + 1 return correct colours(('R','B','O','G'),('R','B','V','O'))

The auxiliary function positions finds the number of colours in guess that are in the right position.

def positions(guess:tuple, hidden:tuple) -> int: """ Preconditions: guess is a sequence of four unique colours chosen from R, O, Y, G, B, V; hidden is a sequence of four unique colours chosen from R, O, Y, G, B, V; Postconditions: output is number of colours in guess that are in the right position """ right = 0 for position in range(0,4): if guess[position] == hidden[position]: right = right + 1 return right positions(('R','B','O','G'),('R','B','V','O'))

Q1(a)

What is the worst-case complexity of colours? What is the worst-case complexity of positions? Explain your answers.

Q1(b)

We can do a linear search to filter the search space as described above. The guess compared to the hidden code has col correct colours and pos right positions. A candidate is a possible solution (that is, the possible hidden code) if the guess compared to the candidate also has col correct colours and pos right positions. We will use a filter candidates function with the following definition:

Function: filter candidates Inputs: guess, a sequence; col, an integer; pos, an integer, candidates, a sequence of sequences Preconditions: guess is a sequence of four unique colours chosen from R, O, Y, G, B, V; 0 <= col <= 4; 0 <= pos <= 4; each item in candidates is a unique sequence of four unique colours chosen from R, O, Y, G, B, V Outputs: filtered, a sequence of sequences Postconditions: filtered is all items in candidates that have the same number of correct colours and right positions as guess, sorted in the same order as candidates

Q1(b)(i)

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.

Note: Designing an algorithm in a numbered list is used. Expected to use a similar format here.

Q1(b)(ii)

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

%run -i m269_util

# WRITE CODE HERE

Q1(c)(i)

Run the following code to measure the run-time of your implemented filter_candidates function on the search space candidates:

#Note: This will only work after you have programmed filter_candidates() my_guess = ('R', 'B', 'O', 'G') hidden = ('B', 'R', 'V', 'G') col = colours(my_guess, hidden) # result is 3 pos = positions(my_guess, hidden) # result is 1 %timeit -r 3 -n 1000 filter_candidates(my_guess, col, pos, candidates)

Run the following code to list the reduced search space:

# Note: This will only work after you have programmed filter_candidates() reduced = filter_candidates(my_guess, colours(my_guess, hidden), positions(my_guess, hidden), candidates) print(reduced) print('Candidates remaining:', len(reduced))

We can choose a new guess from the reduced search space and repeat the process. Let us choose ('V', 'R', 'O', 'B'). Run the following code to create the reduced search space new_reduced.

new_guess = ('V', 'R', 'O', 'B') new_col = colours(new_guess, hidden) # result is 3 new_pos = positions(new_guess, hidden) # result is 1 new_reduced = filter_candidates(new_guess, new_col, new_pos, reduced) print(new_reduced) print("Candidates remaining:", len(new_reduced))

new_reduced is a fraction of the size of candidates. Do you see a run-time on new_reduced of approximately the same fraction of the time observed on candidates or not? Do your run-times suggest filter_candidates has linear complexity or not? You may wish to time the last run of filter_candidates and include your timings in your answer.

%timeit -r 3 -n 1000 filter_candidates(new_guess, new_col, new_pos, new_reduced)

Q1(c)(ii)

Analyse the worst-case complexity of your filter_candidates implementation. Explain whether your run-times support your analysis.