Implement a Word Guessing Game
Company: Shopify
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a four-letter word guessing game.
You are given:
- A dictionary containing valid four-letter English words.
- A target word selected from that dictionary.
The player may submit guesses until either:
- The target word is guessed correctly, or
- The player has used 5 valid guesses.
Requirements:
1. Each guess must be exactly four letters and must exist in the provided dictionary.
2. If a guess is invalid, reject it immediately.
- Do not return a hint.
- Do not count it as one of the 5 attempts.
3. If the guess is valid, return whether the guess is correct. If it is not correct, return a hint string of length 4.
4. The hint uses the following symbols:
- `1`: the character is correct and in the correct position.
- `0`: the character exists in the target word but is in a different position.
- `-`: the character does not exist in the target word, or all occurrences of that character have already been matched.
5. If duplicate letters are involved, use Wordle-style matching:
- First mark exact matches with `1`.
- Then mark misplaced matches with `0` only if there is an unmatched occurrence of that letter remaining in the target word.
Example:
```text
Dictionary: {"able", "bell", "boss", "cast", "cash", "knot", "note"}
Target: "cast"
```
Guess:
```text
cash
```
Hint:
```text
111-
```
Explanation: `c`, `a`, and `s` are correct and in the correct positions. `h` is not in the target.
Guess:
```text
salt
```
Hint:
```text
01-1
```
Explanation: `s` exists in the target but is in the wrong position, `a` and `t` are correct, and `l` is not in the target.
Design and implement a clean API for this game. In an AI-assisted pair-programming setting, you may also be asked to read an existing generated implementation, identify bugs or inefficiencies, and improve it.
Quick Answer: This question evaluates a developer's proficiency in string processing, input validation, state management, Wordle-style matching semantics (including duplicate-letter handling), and API design for game logic and edge cases.
Write a function that simulates a four-letter word guessing game. You are given a dictionary of allowed words, a target word from that dictionary, and a list of guesses in the order they were made. A guess is valid only if it is a string of exactly 4 letters and appears in the dictionary. Invalid guesses must return the response 'INVALID', must not produce a hint, and must not count toward the 5 allowed valid attempts. For a valid guess, if it matches the target, return 'CORRECT' for that guess and stop the game. Otherwise, return a 4-character hint using Wordle-style matching: first mark exact matches with '1', then mark misplaced matches with '0' only if an unmatched occurrence of that letter still remains in the target, and use '-' for all other positions. Stop processing guesses as soon as the player guesses the target or uses 5 valid guesses. Return a tuple (won, attempts_used, results), where won is a boolean, attempts_used is the number of valid guesses consumed, and results is the list of responses for each processed guess.
Constraints
- 1 <= len(dictionary_words) <= 100000
- 0 <= len(guesses) <= 100000
- Each dictionary word and the target consists of exactly 4 lowercase English letters
- The target is guaranteed to appear in dictionary_words
- Only valid guesses count toward the 5-attempt limit
Examples
Input: (["code", "coda", "play"], "code", [1234, "coda", "code"])
Expected Output: (True, 2, ['INVALID', '111-', 'CORRECT'])
Explanation: 1234 is not a string, so it is invalid and does not use an attempt. 'coda' matches the first three positions exactly, giving '111-'. 'code' is then guessed correctly on the second valid attempt.
Input: (["bend", "ebnx", "xend", "ally"], "bend", ["ebnx", "xend", "bend"])
Expected Output: (True, 3, ['001-', '-111', 'CORRECT'])
Explanation: 'ebnx' has 'e' and 'b' misplaced, 'n' exact, and 'x' absent, so the hint is '001-'. 'xend' has only the first letter wrong, giving '-111'. The third valid guess is correct.
Hints
- Use a set for the dictionary so you can validate guesses in O(1) average time.
- To handle duplicate letters correctly, build the hint in two passes: exact matches first, then misplaced matches using counts of the remaining unmatched target letters.