Implement Wordle-style word guessing solver

Implement a program to solve a Wordle-style word guessing game. The game has a hidden target word of fixed length L (e.g., 5) drawn from a known dictionary. After each guess, you receive per-character feedback: Correct (right letter, right position), Present (letter exists but different position), or Absent (letter not in the word). Requirements: (1) Keep guessing until the word is solved or a maximum attempt limit is reached; (2) Design data structures and an algorithm to maintain constraints and prune the candidate set after each feedback; (3) Correctly handle repeated letters and seemingly conflicting feedback (e.g., one instance Present while another is Absent); (4) Propose and implement a strategy to choose the next guess (e.g., frequency-based heuristic or information-gain approximation) and justify it; (5) Provide an interface solve(dictionary, feedback_api, max_attempts) -> (final_guess, num_attempts) where feedback_api(guess) returns the feedback for each position; (6) Analyze time and space complexity; (7) Include unit tests and demonstrate a sample run.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Implement Wordle-style word guessing solver

Implement a solver for a Wordle-style word-guessing game.\n\nA hidden target word of fixed length L is drawn from a known dictionary of equal-length lowercase words. For any guess you can derive per-character feedback:\n- Correct (2) — right letter, right position\n- Present (1) — letter is in the word but in a different position\n- Absent (0) — letter not in the word\n\nImplement solve(dictionary, target, max_attempts) returning (final_guess, num_attempts):\n1. Repeatedly guess until the word is solved or max_attempts is reached.\n2. After each guess, prune the candidate set to every word that would produce the same feedback against the guess.\n3. Handle repeated letters correctly — the classic case where one instance of a letter is Present while a duplicate is Absent. Use a two-pass count: mark exact matches first, then consume remaining letter counts for misplaced letters.\n4. Choose the next guess with a letter-frequency heuristic (favor the candidate whose distinct letters cover the most remaining candidates), with a deterministic lexicographic tie-break.\n\nfinal_guess is the solved word if found within the limit, otherwise the last (best) guess; num_attempts is the number of guesses made. An empty dictionary returns ('', 0).

Constraints

• All words in dictionary share the same length L.
• Words are lowercase a-z.
• target is the hidden word; for a solvable game it lies in dictionary.
• 1 <= max_attempts; an empty dictionary returns ('', 0).
• Repeated letters must be scored with exact Wordle semantics (two-pass count).

Examples

Example 1

Input: (['crane', 'slate', 'trace', 'blink', 'ghost', 'lucky'], 'ghost', 6)
Output: ('ghost', 2)

Explanation: Solver narrows to GHOST within the attempt limit.

Example 2

Input: (['allee', 'apple', 'ample', 'amble', 'eagle', 'ladle'], 'apple', 6)
Output: ('apple', 2)

Explanation: Target APPLE has duplicate P/L; repeated-letter scoring still converges.

Hints

1. Write the feedback/scoring function first. Use TWO passes: pass 1 marks Correct (==2) positions and tallies the remaining (unmatched) letters of the target; pass 2 marks Present (==1) only while a remaining count for that letter is left. This is what makes 'one copy Present, another Absent' come out right.
2. Pruning is the key insight: after guessing G and seeing feedback F, the target must be SOME word W in the candidate set for which score(G, W) == F. Filter the candidates to exactly those words — no other constraint bookkeeping is needed.
3. For next-guess selection, count how many candidates contain each distinct letter, then pick the candidate maximizing the sum of those counts over its distinct letters. Break ties deterministically (e.g. lexicographically) so the run is reproducible.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Implement a program to solve a Wordle-style word guessing game. The game has a hidden target word of fixed length L (e.g., 5) drawn from a known dictionary. After each guess, you receive per-character feedback: Correct (right letter, right position), Present (letter exists but different position), or Absent (letter not in the word). Requirements: ( 1) Keep guessing until the word is solved or a maximum attempt limit is reached; ( 2) Design data structures and an algorithm to maintain constraints and prune the candidate set after each feedback; ( 3) Correctly handle repeated letters and seemingly conflicting feedback (e.g., one instance Present while another is Absent); ( 4) Propose and imple...

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.