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

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 code here