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.

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 all possible 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'))

We can do a linear search to filter the search space as described above. The guess compared to the hidden code has colcorrect 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 colcorrect 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 ascendingly

question

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 <= 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 Postconditions: output is all items in candidates that have the same number of correct colours and right positions as guess """ # Write your code here

# 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)

Question

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

#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 2 %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 measure the run-time of filter_candidates on the reduced search space reduced.

new_guess = ('V', 'R', 'O', 'B') new_col = colours(new_guess, hidden) # result is 2 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_reducedof 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)