Connection Status:
Competition Arena > WordGuessingGame

WordGuessingGame

TCCC06 Sponsor 3 · 2006-08-22 · by Yarin

TCCC06 Sponsor 3 · 2006-08-22 · by Yarin · Dynamic Programming, Recursion
Class Name: WordGuessingGame
Return Type: String[]
Method Name: possibleWords
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

Consider the following two player word game, which slightly resembles Mastermind:

The first player secretly picks a word and tells its length to the second player. The second player then guesses a word, and the first player responds by telling whether the number of correct letters in correct positions is even or odd. This is repeated until the second player can figure out what the first player's picked word is (see the examples for clarifications).

Create a class WordGuessingGame containing the method possibleWords which takes a String[] even containing all the guessed words so far where the correct number of letters in the correct position were even, and a String[] odd containing all the guessed words so far where the correct number of letters in the correct position were odd. The method should return a String[] containing all possible words that the first player could have picked. The String[] should be sorted in alphabetical order.

Notes

  • Note that in this problem, "word" means any possible combination of uppercase letters ('A'-'Z').
  • If no words match the information given, return an empty String[] (see example 3).

Constraints

  • even and odd will together contain between 1 and 18 elements, inclusive.
  • All elements in even and odd will be of the same length (between 1 and 9 characters, inclusive).
  • All characters in even and odd will be uppercase letters ('A'-'Z').
  • The number of words matching the given information will be at most 100.
Examples
0)
{"DAY","MAY","BUY"}
{"SAY","DUE","TEN"}
Returns: {"SEE" }

0 or 2 letters are correct and at their correct location in the words "DAY" and "MAY". This tells us that the first letter can't be 'D' or 'M' because then one of the words would have an odd number of letters correct. "DAY" and "SAY" tell us that the first letter is either 'D' or 'S'. Therefore, the first letter must be 'S'. So the first letter is wrong in "MAY" and "BUY", and because they have the same parity, the second letter can't be 'A' or 'U'. Knowing that 'D' is not the first letter and 'U' is not the second, we can conclude from the word "DUE" that the last letter must be 'E'. Finally the word "TEN" tells us that the second letter must be 'E' because the other two letters in the word are wrong.

1)
{"QMNA","UQJE"}
{"HUIF","QMZB","QEHJ","LBJL"}
Returns: {"HBHB", "HBZJ", "HEZL", "LEIB", "LEZF", "LUHB", "LUZJ", "QBIA", "QBNF", "QUNL" }
2)
{"NODSN"}
{"MOOTN","CRXXU","SREQR","DEREX","HOYGF","CDLCP","ZTDOC","STEEB"}
Returns: {"CODER" }
3)
{}
{"AB","BC","CA"}
Returns: { }
4)
{"K"}
{}
Returns: {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z" }

Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WordGuessingGame with a public method vector<string> possibleWords(vector<string> even, vector<string> odd) · 64 test cases · 2 s / 256 MB per case

Submitting as anonymous