# LeetCode 843: Guess the Word

## Problem Restatement

We are given a list of unique strings `words`.

Each word has length `6`.

One word from the list is chosen as the secret word.

We can call:

```python
master.guess(word)
```

This returns:

| Return value | Meaning |
|---|---|
| `-1` | The guessed word is not in the word list |
| `0` to `6` | Number of positions where the guessed word matches the secret word |

We must find the secret word within at most `10` guesses. This is an interactive problem, so the function does not return the secret word. It calls `master.guess` until the secret is found.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `words` and helper object `master` |
| Output | No direct return value |
| Goal | Call `master.guess` with the secret word |
| Word length | Always `6` |
| Guess limit | At most `10` guesses |
| Feedback | Exact position match count |

Function shape:

```python
class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        ...
```

## Examples

Suppose:

```python
secret = "acckzz"
words = ["acckzz", "ccbazz", "eiowzz", "abcczz"]
```

If we guess:

```python
"ccbazz"
```

Compare it with the secret:

```python
secret: acckzz
guess:  ccbazz
```

Matching positions are:

| Index | Secret | Guess | Match |
|---:|---|---|---|
| `0` | `a` | `c` | No |
| `1` | `c` | `c` | Yes |
| `2` | `c` | `b` | No |
| `3` | `k` | `a` | No |
| `4` | `z` | `z` | Yes |
| `5` | `z` | `z` | Yes |

So:

```python
master.guess("ccbazz") == 3
```

This tells us that the secret must be one of the remaining words that has exactly `3` matching positions with `"ccbazz"`.

## First Thought: Random Guess and Filter

A simple strategy is:

1. Pick any word from the current candidate list.
2. Call `master.guess(word)`.
3. Suppose the result is `matches`.
4. Keep only words that have exactly `matches` matching positions with the guessed word.
5. Repeat.

This works because the secret must be consistent with every feedback result.

```python
class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        def match(a: str, b: str) -> int:
            return sum(x == y for x, y in zip(a, b))

        candidates = words[:]

        for _ in range(10):
            guess = candidates[0]
            score = master.guess(guess)

            if score == 6:
                return

            candidates = [
                word
                for word in candidates
                if match(word, guess) == score
            ]
```

This filtering idea is the core of the solution.

But choosing the first candidate can be weak. We want guesses that reduce the candidate list quickly.

## Key Insight

Every guess partitions the candidate list into groups by match count.

For a guess word, each remaining candidate would produce a score from `0` to `6`.

A good guess has no very large group after partitioning, because no matter what score comes back, the remaining candidate list becomes small.

So we can choose the word with the best worst-case split.

For each possible guess:

1. Count how many candidates give score `0`, score `1`, ..., score `6`.
2. Let the largest bucket size be the worst case.
3. Pick the guess with the smallest worst-case bucket.

This is a minimax-style heuristic.

## Algorithm

Use a helper function:

```python
match(a, b)
```

which returns the number of equal characters at the same positions.

Then repeat up to `10` times:

1. Choose a guess from the current candidate list.
2. Use minimax bucket scoring to choose a strong guess.
3. Call `master.guess(guess)`.
4. If the result is `6`, the secret is found.
5. Otherwise, filter candidates to only words with the same match count against the guess.

## Walkthrough

Suppose the current candidates are:

```python
["acckzz", "ccbazz", "eiowzz", "abcczz"]
```

Guess:

```python
"ccbazz"
```

The result is:

```python
3
```

Now we keep only words that have exactly `3` matches with `"ccbazz"`.

Compare:

| Word | Matches with `"ccbazz"` |
|---|---:|
| `"acckzz"` | `3` |
| `"ccbazz"` | `6` |
| `"eiowzz"` | `2` |
| `"abcczz"` | `3` |

The new candidates are:

```python
["acckzz", "abcczz"]
```

The secret must be one of these.

If we later guess `"acckzz"` and get `6`, the secret is found.

## Correctness

After each guess, `master.guess(guess)` returns the number of exact position matches between the guess and the secret.

Any word that does not have this same match count against the guess cannot be the secret, because it would have produced different feedback.

Any word that does have the same match count remains possible, because it is still consistent with all feedback seen so far.

Therefore, the filtering step never removes the true secret and removes only impossible candidates.

If the algorithm receives score `6`, the guessed word matches the secret at all six positions. Since all words have length `6`, the guessed word is the secret.

The minimax selection affects efficiency, not validity. The correctness comes from always guessing a word from the candidate list and filtering by exact feedback consistency.

## Complexity

Let:

```python
n = len(words)
```

Each word has fixed length `6`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(10 * n^2)` | Each round may compare candidate pairs to choose a guess |
| Space | `O(n)` | Store the current candidate list and buckets |

Since word length is fixed at `6`, each match check is constant time.

## Implementation

```python
from collections import Counter

class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        def match(a: str, b: str) -> int:
            count = 0

            for x, y in zip(a, b):
                if x == y:
                    count += 1

            return count

        def choose_guess(candidates: list[str]) -> str:
            best_word = candidates[0]
            best_worst_group = len(candidates)

            for guess in candidates:
                buckets = Counter()

                for word in candidates:
                    if word != guess:
                        buckets[match(guess, word)] += 1

                worst_group = max(buckets.values(), default=0)

                if worst_group < best_worst_group:
                    best_worst_group = worst_group
                    best_word = guess

            return best_word

        candidates = words[:]

        for _ in range(10):
            guess = choose_guess(candidates)
            score = master.guess(guess)

            if score == 6:
                return

            candidates = [
                word
                for word in candidates
                if match(word, guess) == score
            ]
```

## Code Explanation

The `match` helper counts exact-position matches:

```python
def match(a: str, b: str) -> int:
```

For example:

```python
match("ccbazz", "acckzz") == 3
```

The `choose_guess` helper selects the candidate with the smallest worst-case bucket:

```python
def choose_guess(candidates: list[str]) -> str:
```

For each guess, it groups all candidates by the score they would return:

```python
buckets[match(guess, word)] += 1
```

Then it measures the worst remaining group:

```python
worst_group = max(buckets.values(), default=0)
```

The smallest worst group is preferred.

After guessing:

```python
score = master.guess(guess)
```

a score of `6` means the secret has been found:

```python
if score == 6:
    return
```

Otherwise, filter to candidates consistent with the feedback:

```python
candidates = [
    word
    for word in candidates
    if match(word, guess) == score
]
```

## Testing

Interactive LeetCode problems cannot be tested with a normal return value, but we can create a local `Master` mock.

```python
class Master:
    def __init__(self, secret: str, words: list[str]):
        self.secret = secret
        self.words = set(words)
        self.calls = 0
        self.found = False

    def guess(self, word: str) -> int:
        self.calls += 1

        if word not in self.words:
            return -1

        score = sum(a == b for a, b in zip(word, self.secret))

        if score == 6:
            self.found = True

        return score

def run_tests():
    words = ["acckzz", "ccbazz", "eiowzz", "abcczz"]
    master = Master("acckzz", words)

    Solution().findSecretWord(words, master)

    assert master.found is True
    assert master.calls <= 10

    words = [
        "abcdef",
        "abqdef",
        "zzzzzz",
        "abcxyz",
        "axcyef",
        "mnopqr",
    ]
    master = Master("abqdef", words)

    Solution().findSecretWord(words, master)

    assert master.found is True
    assert master.calls <= 10

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Small known secret | Confirms feedback filtering finds the target |
| Similar candidate words | Confirms minimax choice still keeps the secret |
| `calls <= 10` | Confirms interactive guess limit is respected |