Guess the Word

hard array math game theory interactive

Problem

You're given a list of 6-letter words and an interactive Master that reports the number of matching letter-positions between your guess and the hidden secret. Find the secret in ≤ 10 guesses.

Inputwordlist = ["acckzz","ccbazz","eiowzz","abcczz"], secret="acckzz"

Output"acckzz"

Each round, pick the candidate whose worst-case partition is smallest, then filter by the Master's feedback.

wordlist (space-separated, 6 letters each)

secret

def findSecretWord(wordlist, master):
    def match(a, b):
        return sum(1 for x, y in zip(a, b) if x == y)
    candidates = wordlist[:]
    for _ in range(10):
        # pick word that minimizes worst-case 0-match group
        best, best_score = candidates[0], len(candidates)
        for w in candidates:
            zeros = sum(1 for c in candidates if match(w, c) == 0)
            if zeros < best_score:
                best_score, best = zeros, w
        m = master.guess(best)
        if m == 6: return
        candidates = [c for c in candidates if match(c, best) == m]

function findSecretWord(wordlist, master) {
  const match = (a, b) => { let m = 0; for (let i = 0; i < 6; i++) if (a[i] === b[i]) m++; return m; };
  let candidates = wordlist.slice();
  for (let round = 0; round < 10; round++) {
    let best = candidates[0], bestScore = candidates.length;
    for (const w of candidates) {
      let zeros = 0;
      for (const c of candidates) if (match(w, c) === 0) zeros++;
      if (zeros < bestScore) { bestScore = zeros; best = w; }
    }
    const m = master.guess(best);
    if (m === 6) return;
    candidates = candidates.filter(c => match(c, best) === m);
  }
}

class Solution {
    public void findSecretWord(String[] wordlist, Master master) {
        List<String> cands = new ArrayList<>(Arrays.asList(wordlist));
        for (int r = 0; r < 10; r++) {
            String best = cands.get(0); int bestScore = cands.size();
            for (String w : cands) {
                int zeros = 0;
                for (String c : cands) if (match(w, c) == 0) zeros++;
                if (zeros < bestScore) { bestScore = zeros; best = w; }
            }
            int m = master.guess(best);
            if (m == 6) return;
            final String guess = best; final int mm = m;
            List<String> next = new ArrayList<>();
            for (String c : cands) if (match(c, guess) == mm) next.add(c);
            cands = next;
        }
    }
    int match(String a, String b) { int m = 0; for (int i = 0; i < 6; i++) if (a.charAt(i) == b.charAt(i)) m++; return m; }
}

void findSecretWord(vector<string>& wordlist, Master& master) {
    auto match = [](const string& a, const string& b){ int m = 0; for (int i = 0; i < 6; i++) if (a[i] == b[i]) m++; return m; };
    vector<string> cands = wordlist;
    for (int r = 0; r < 10; r++) {
        string best = cands[0]; int bestScore = (int)cands.size();
        for (auto& w : cands) {
            int zeros = 0;
            for (auto& c : cands) if (match(w, c) == 0) zeros++;
            if (zeros < bestScore) { bestScore = zeros; best = w; }
        }
        int m = master.guess(best);
        if (m == 6) return;
        vector<string> next;
        for (auto& c : cands) if (match(c, best) == m) next.push_back(c);
        cands = next;
    }
}

Explanation

This is a guessing game where each guess returns how many letter positions match the hidden secret. The strategy is to keep a shrinking list of candidates and pick guesses that throw away as many wrong words as possible.

The clever part is which word to guess. We want a guess that is informative. The code uses a simple heuristic: for each candidate w, count how many other candidates share zero matching positions with it, then guess the word whose zero-match group is smallest. Words with many zero-matches tend to be outliers that leave big groups untouched, so avoiding them keeps the candidates from staying large.

After guessing best, the Master returns a number m. The real secret must share exactly m positions with our guess, so we filter the candidate list down to only words where match(c, best) == m. Everything else is impossible and gets dropped.

We repeat this for up to 10 rounds. If a guess returns m == 6, all six letters matched, so we found the secret and stop.

Example: with candidates like acckzz, ccbazz, eiowzz, guessing one word and learning it matches in, say, 2 positions instantly removes every word that does not also match it in exactly 2 positions, quickly narrowing things to the answer.

Time: O(N² · rounds) Space: O(N)