Problem M
Last Guess
If you spent any amount of time on social media at the end of last year, you are probably familiar with the word finding game Wordle, in which you need to find a five-letter English word using at most six guesses. After each guess, the letters in that guess are marked in either green, yellow or black to provide information about the hidden word:
-
Green indicates that the letter is in the hidden word and appears in the same position.
-
Yellow indicates that the letter is in the hidden word, but in a different position.
-
Black indicates that the letter has no more occurrences in the hidden word.
-
If a letter appears more than once in the guessed word, first all the green markings for that letter are placed. Then, from left to right in the guessed word, yellow markings are placed for each remaining occurrence of the letter in the hidden word. Finally, black markings are placed for any surplus of the letter in the guessed word. See Figure 1 for an example.
In this problem, we consider a variant of Wordle where you
need to find a hidden word of length
In your current play of this variant, you have already used all but one of your guesses, and now you need to find the hidden word using your final guess. Find any word that could be the hidden word based on the information you have.
Input
The input consists of:
-
One line with two integers
and ( , ), the maximal number of guesses allowed in the game and the length of the word. -
lines, each with two strings and of length , where is one of the guesses so far and gives the colours for that guess according to the rules above. The string consists of lowercase English letters (a-z) and the string consists of uppercase letters ‘G’, ‘Y’, and ‘B’ indicating green, yellow, and black respectively.
It is guaranteed that the input describes a valid state of a
Wordle game before the last guess and that a valid solution
exists, in the form of a length
Output
Output a valid last guess that gives you a chance of winning.
If there are multiple valid solutions, you may output any one of them.
Sample Input 1 | Sample Output 1 |
---|---|
4 5 reply YYGBB refer BBBGG puppy YYGBB |
upper |
Sample Input 2 | Sample Output 2 |
---|---|
2 12 aabbccddeeff GGGYGBYYYBBB |
aabdcbegdhij |