Algorithm
Problem Name: 843. Guess the Word
You are given an array of unique strings words where words[i] is six letters long. One word of words was chosen as a secret word.
You are also given the helper object Master. You may call Master.guess(word) where word is a six-letter-long string, and it must be from words. Master.guess(word) returns:
-1ifwordis not fromwords, or- an integer representing the number of exact matches (value and position) of your guess to the secret word.
There is a parameter allowedGuesses for each test case where allowedGuesses is the maximum number of times you can call Master.guess(word).
For each test case, you should call Master.guess with the secret word without exceeding the maximum number of allowed guesses. You will get:
"Either you took too many guesses, or you did not find the secret word."if you calledMaster.guessmore thanallowedGuessestimes or if you did not callMaster.guesswith the secret word, or"You guessed the secret word correctly."if you calledMaster.guesswith the secret word with the number of calls toMaster.guessless than or equal toallowedGuesses.
The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).
Example 1:
Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
We made 5 calls to master.guess, and one of them was the secret, so we pass the test case.
Example 2:
Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10 Output: You guessed the secret word correctly. Explanation: Since there are two words, you can guess both.
Constraints:
1 <= words.length <= 100words[i].length == 6words[i]consist of lowercase English letters.- All the strings of
wordlistare unique. secretexists inwords.10 <= allowedGuesses <= 30
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int idx[100];
int n;
} set_t;
#define IDX(I, J) ((I) * 100 + J)
int solve(set_t *p, int *xp, int *match, int sz) {
int groups[7] = { 0 }; // max match number is 6
int max_group, min_group;
int i, j, g;
if (p->n < = 2) return p->idx[0];
g = -1; min_group = 1000;
for (i = 0; i < sz; i ++) {
if (xp[i]) continue;
memset(groups, 0, sizeof(int) * 7);
for (j = 0; j < p->n; j ++) {
if (i != p->idx[j]) groups[match[IDX(i, p->idx[j])]] ++;
}
max_group = groups[0];
for (j = 1; j < 7; j ++) {
if (max_group < groups[j]) max_group = groups[j];
}
if (min_group > max_group) {
min_group = max_group;
//printf("groups: %d, %d %d, %d, %d, %d, %d\n", groups[0], groups[1], groups[2], groups[3], groups[4], groups[5], groups[6]);
g = i;
}
}
return g;
}
void findSecretWord(char** wordlist, int wordlistSize, Master* master) {
int match[100 * 100];
int i, j, k, m, g;
char *a, *b;
set_t buff[2] = { 0 };
set_t *p1, *p2, *p3;
int xp[100] = { 0 };
p1 = &buff[0];
p2 = &buff[1];
// caculate match matrix
for (i = 0; i < wordlistSize; i ++) {
a = wordlist[i];
for (j = i + 1; j < wordlistSize; j ++) {
b = wordlist[j];
m = 0;
for (k = 0; k < 6; k ++) {
if (a[k] == b[k]) m ++;
}
match[IDX(i, j)] = match[IDX(j, i)] = m;
}
}
// all are possible in the beginning
for (i = 0; i < wordlistSize; i ++) {
p1->idx[p1->n ++] = i;
}
while (p1->n > 0) {
//printf("POSSIBLE: %d\n", p1->n);
g = solve(p1, xp, match, wordlistSize);
printf("GUESS: %d, %s\n", g, wordlist[g]);
m = guess(master, wordlist[g]);
//printf("MATCH: %d\n", m);
if (m == 6) return;
// find out next possible words
p2->n = 0; // reset p2
for (i = 0; i < p1->n; i ++) {
if (match[IDX(g, p1->idx[i])] == m) {
p2->idx[p2->n ++] = p1->idx[i];
}
}
// swap p1, p2
p3 = p1;
p1 = p2;
p2 = p3;
// exclude g in future guess
xp[g] = 1;
}
}
Input
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output
You guessed the secret word correctly.
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
void findSecretWord(vector<string>& wordlist, Master& master) {
vector<string>cur, next;
cur = wordlist;
for (int i = 0; i < 10; ++i) {
int n = cur.size();
auto word = cur[rand() % n];
int match = master.guess(word);
if (match == 6) {
break;
}
for (auto& s: cur) {
if (distance(s, word) == match) {
next.push_back(s);
}
}
cur.clear();
swap(cur, next);
}
}
int distance(string& a, string& b) {
int res = 0;
for (int i = 0; i < a.size(); ++i) {
if (a[i] == b[i]) {
++res;
}
}
return res;
}
};
Input
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output
You guessed the secret word correctly.
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findSecretWord = function (wordlist, master) {
let group = wordlist
for (let i = 0; i < 10; i++) {
let currentGuess = findTheTypical(group)
let res = master.guess(currentGuess)
if (res === 6) return
let tmp = []
for (let j = 0; j < group.length; j++) {
if (diff(group[j], currentGuess) === 6 - res) tmp.push(group[j])
}
group = tmp
}
}
function findTheTypical(wordlist) {
const count = Array.from({ length: 6 }, (x) => new Object())
for (let i = 0; i < wordlist.length; i++) {
for (let j = 0; j < 6; j++) {
const cur = wordlist[i][j]
if (count[j][cur] === undefined) count[j][cur] = 1
else count[j][cur]++
}
}
let maxPos = 0,
maxCount = 0,
maxAlp = ''
for (let i = 0; i < 6; i++) {
for (let k of Object.keys(count[i])) {
if (count[i][k] > maxCount) {
maxCount = count[i][k]
maxPos = i
maxAlp = k
}
}
}
for (let i = 0; i < wordlist.length; i++) {
if (wordlist[i][maxPos] === maxAlp) return wordlist[i]
}
}
function diff(a, b) {
let count = 0
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) count++
}
return count
}
Input
secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
Output
You guessed the secret word correctly.
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findSecretWord(self, wordlist, master):
n = 0
while n < 6:
count = collections.Counter(w1 for w1, w2 in itertools.permutations(wordlist, 2) if sum(i == j for i, j in zip(w1, w2)) == 0)
guess = min(wordlist, key = lambda w: count[w])
n = master.guess(guess)
wordlist = [w for w in wordlist if sum(i == j for i, j in zip(w, guess)) == n]
Input
secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10
Output
You guessed the secret word correctly.
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0843_GuesstheWord
{
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
* public int Guess(string word);
* }
*/
public void FindSecretWord(string[] wordlist, Master master)
{
var random = new Random();
var wordlistHashSet = new HashSet < string>(wordlist);
for (int i = 0; i < 10; i++)
{
var word = wordlistHashSet.ElementAt(random.Next(wordlistHashSet.Count));
var result = master.Guess(word);
if (result == word.Length) return;
wordlistHashSet.RemoveWhere(anotherWord => MatchCount(word, anotherWord) != result);
wordlistHashSet.Remove(word);
}
}
public int MatchCount(string word1, string word2)
{
var count = 0;
for (int i = 0; i < word1.Length; i++)
if (word1[i] == word2[i])
count++;
return count;
}
}
public class Master
{
private readonly string secret;
private readonly HashSet < string> wordlist;
public Master(string secret, string[] wordlist)
{
this.secret = secret;
this.wordlist = new HashSet < string>(wordlist);
GuessCount = 0;
}
public int GuessCount { get; set; }
public int Guess(string word)
{
GuessCount++;
if (this.secret.Length != word.Length) { return -1; }
if (!wordlist.Contains(word)) { return -1; }
var count = 0;
for (int i = 0; i < word.Length; i++)
if (word[i] == secret[i])
count++;
return count;
}
}
}
Input
secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output
You guessed the secret word correctly.