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.
Overview: 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.
Community answers
Answer by jbakker
In the currently posted answer in the Solution tab, it uses two loops to build the hint:
def build_hint(guess, target_word):
hint = ['-'] * 4
remaining = {}
# First pass: mark exact matches.
for i in range(4):
if guess[i] == target_word[i]:
hint[i] = '1'
else:
ch = target_word[i]
remaining[ch] = remaining.get(ch, 0) + 1
# Second pass: mark misplaced matches using only unmatched target letters.
for i in range(4):
if hint[i] != '-':
continue
ch = guess[i]
if remaining.get(ch, 0) > 0:
hint[i] = '0'
remaining[ch] -= 1
return ''.join(hint)
It can be done more succinctly, in one loop, and easier to read:
hint = ""
for index, letter in enumerate(valid_guess):
if letter == target[index]:
hint += '1'
elif letter in target:
hint += '0'
else:
hint += '-'