Identify a Target Word with Repeated Minimax Guesses

Problem Statement

You are tasked with designing an engine to solve a word guessing game. You are given a dictionary of valid 5-letter words. When you guess a word, the system returns a 'score' representing the relationship between your guess and the secret word.

Each position in the guess is assigned a state:

• 2: The character is in the correct position (Green).
• 1: The character exists in the word but in a different position (Yellow).
• 0: The character does not exist in the word (Grey).

Your goal is to write a function get_best_guess(possible_words, dictionary) that returns the next optimal word to guess based on a minimax strategy. The strategy aims to minimize the maximum size of the candidate pool remaining after any potential feedback.

Function Signature

def get_best_guess(possible_words, dictionary):
    # possible_words: list of words consistent with all previous feedback
    # dictionary: full list of all valid words that can be guessed
    pass

Scoring Logic

Given a guess and a secret, generate a 5-tuple representing the feedback. For duplicate letters in the guess, prioritize '2's, then '1's, then '0's based on their count in the secret word.

Example

• Secret: APPLE, Guess: PAPER
• Feedback: (1, 2, 1, 0, 1)
• Logic: 'P' (idx 0) is in 'APPLE' (1), 'A' (idx 1) is index 0 (2), 'P' (idx 2) is in 'APPLE' (1), 'E' (idx 3) not present (0), 'R' (idx 4) not present (0).

Constraints

• dictionary size up to 10,000 words.
• possible_words will reduce over time.
• Time limit per guess: 2 seconds.