# Identify a Target Word with Repeated Minimax Guesses A hidden target is guaranteed to be one of the supplied words. You may repeatedly submit any word from the complete supplied list to an oracle. The oracle returns the number of positions whose characters match the hidden target. Continue until the oracle returns the full word length, which identifies the target. The source preserves this repeated-oracle process but not an exact strategy for choosing probes. The deterministic minimax and balance objective below is an explicit practice contract, not a claim about the original interview's required heuristic. ~~~python def identify_word( words: list[str], oracle_scores: list[int] ) -> list[list[object]]: ... ~~~ `oracle_scores[i]` is the response the literal oracle simulator returns when `words[i]` is guessed. It must describe exactly one valid hidden target: exactly one element equals the common word length, and every score must equal the positional-match score between its word and that target. The score vector keeps this console exercise JSON-only; the required transcript must still follow the selection process below rather than returning the target directly. Start with every word as a possible target. Before each oracle call: 1. If exactly one target candidate remains, guess that word. 2. Otherwise, consider every word in the complete supplied list as a possible probe, including words already eliminated as targets. 3. For each probe, partition the current target candidates by the score that probe would receive against them. Rank probes by this tuple, from smallest to largest: - the largest bucket size, which is the minimax objective; - the sum of squared bucket sizes, an exact entropy-style balance proxy under a uniform target assumption; - `0` if the probe is still a target candidate and `1` otherwise; and - the probe string in ordinary lexicographic order. 4. Query the simulator only for the selected probe and append `[probe, returned_score]` to the transcript. 5. If the returned score is the word length, stop. Otherwise, retain exactly the candidates that would produce that score and repeat. Return the complete transcript, including the final successful guess. The rules above always make progress: when several candidates remain, guessing any one candidate separates that word's full-length score from every other distinct word, so the best worst-case bucket is smaller than the current candidate count. ## Constraints and Error Rules - `1 <= len(words) <= 250` - `1 <= len(words[i]) <= 20` - Words are unique lowercase ASCII strings of one common length. - `oracle_scores` is a list with exactly one score per word. - Every score is an integer from `0` through the common word length; Boolean values do not count as integers. - The full score vector must be consistent with exactly one supplied target as defined above. - Malformed inputs or an inconsistent simulator raise `ValueError` before building the transcript. - Inputs and the nested-list output are JSON-marshalable and compared exactly. - Do not mutate either input. ## Example ~~~text Input: words = ["aaaa", "aaab", "aabb"] oracle_scores = [3, 4, 3] Output: [["aaaa", 3], ["aaab", 4]] ~~~ On the first round, probes `"aaaa"` and `"aabb"` both split the three candidates into three single-item buckets, so the final lexicographic tie-break selects `"aaaa"`. Its score leaves only `"aaab"`, which is then guessed to finish. ## Hints - Use one positional scoring function for simulator validation, hypothetical partitions, and candidate filtering. - Bucket counts are sufficient; the partitions do not need to store copied word lists. - Precomputing all pairwise scores costs `O(n^2)` memory but avoids rescanning characters in every round. - With precomputed scores, a direct implementation takes `O(n^2 * L)` preprocessing time and at most `O(n^3)` integer-bucket work across all rounds for these practice bounds.