Peter Norvig Jotto: April 2020 Wordle: Jan 2022 Evil/Anti: Nov 2022
\n",
"\n",
"# Wordle, Evil Wordle, Antiwordle, and Jotto\n",
"\n",
"[**Wordle**](https://www.nytimes.com/games/wordle/index.html) is Josh Wardle's [tremendously popular](https://www.nytimes.com/2022/01/03/technology/wordle-word-game-creator.html) word game in which a **guesser** tries to guess a secret **target** word (chosen from a **word list** of allowable words) in as few guesses as possible. Each guess must be one of the words on the list, and the **reply** to each guess consists of 5 bits (actually [trits](https://en.wiktionary.org/wiki/trit#English)) of information, one for each of the 5 word spots:\n",
" - *Green* if the guess letter is in the word and in the correct spot.\n",
" - *Yellow* if the guess letter is in the word but in the wrong spot.\n",
" - *Miss* if the letter is not in the word in any spot.\n",
"\n",
"Wordle uses a list of 12,971 allowable guess words, but only 2,309 of them can be target words. (I think the idea is to follow [Postel's law](https://en.wikipedia.org/wiki/Robustness_principle): \"be conservative in what you send, be liberal in what you accept\".) In this notebook, we'll assume we're only dealing with the 2,309 target words. Historically, Wordle is a refinement of **Jotto**, and has in turn inspired variants inclusding **Evil Wordle** and **Antiwordle**, all of which we will cover in this notebook.\n",
"\n",
"First off, import some modules and define the basic types `Word`, `Score`, and `Reply`, and the colors that make up the reply:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from typing import List, Tuple, Dict, Union, Counter, Callable, Iterable\n",
"from dataclasses import dataclass\n",
"from statistics import mean, median, stdev\n",
"from collections import defaultdict\n",
"from functools import lru_cache\n",
"from pathlib import Path\n",
"from math import log2\n",
"import random \n",
"import matplotlib.pyplot as plt\n",
"\n",
"Word = str # A word is a string of five different letters\n",
"Score = int # A score is the number of guesses it took to get the target word\n",
"Reply = str # A reply is a str of 5 characters, e.g. 'G...Y'\n",
"\n",
"Green, Yellow, Miss = 'GY.'\n",
"Correct = 5 * Green # The reply for the correct guess\n",
"\n",
"random.seed('for reproducibility')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now read in the word list:"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"! [ -e wordle-small.txt ] || curl -O https://norvig.com/ngrams/wordle-small.txt\n",
"\n",
"wordlist = Path('wordle-small.txt').read_text().split()\n",
"\n",
"assert len(wordlist) == 2309"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Replies\n",
"\n",
"The rules for Wordle replies, outlined above, contain an ambiguity. Let's clear things up.\n",
"\n",
"Assume the guess is `'NINNY'` and the target is `'ANNEX'`. A strict reading of the rules would say that the reply should be `'Y.GY.'`–one of the three `'N'`s is in the right spot and thus is green, and the other two should be yellow because they are \"in the word but in the wrong spot.\" But the actual (unstated) rules are that Wordle matches the greens first, and then goes left-to-right with the yellows, and only gives you as many non-misses as there are letters in the target to support them. In this example, there are two `'N'`s in the target, so after the one green, there will only be one more yellow `'N'`, and it will be in the leftmost available spot. The actual reply is `'Y.G..'`.\n",
"\n",
"In general, how many possible replies are there? There are 3 responses at each of five positions, and 35 = 243, but five of those replies are impossible: you can't have four Greens and one Yellow, because if four letters of the guess are in the right place then the fifth must be either in the right place or a miss. \n",
"\n",
"Below is the definition of `reply_for` and some tests. Note that `reply_for` is not symmetric; `reply_for(A, B)` is always a permutation of `reply_for(B, A)`, but they are usually not equal. Since the computation of a reply is somewhat complex, we cache the results.\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"@lru_cache(None)\n",
"def reply_for(guess: Word, target: Word) -> Reply: \n",
" \"The five-character reply for this guess on this target.\"\n",
" # We'll start by having each element of the reply be either Green or Miss ...\n",
" reply = [Green if guess[i] == target[i] else Miss for i in range(5)]\n",
" # ... then we'll change the elements that should be yellow\n",
" counts = Counter(target[i] for i in range(5) if guess[i] != target[i])\n",
" for i in range(5):\n",
" if reply[i] == Miss and counts[guess[i]] > 0:\n",
" counts[guess[i]] -= 1\n",
" reply[i] = Yellow\n",
" return ''.join(reply)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"assert reply_for('NINNY', 'ANNEX') == 'Y.G..'; assert reply_for('ANNEX', 'NINNY') == '.YG..'\n",
"assert reply_for('HELLO', 'WORLD') == '...GY'; assert reply_for('WORLD', 'HELLO') == '.Y.G.'\n",
"assert reply_for('HELLO', 'ABYSS') == '.....'; assert reply_for('ABYSS', 'HELLO') == '.....'\n",
"assert reply_for('EPEES', 'GEESE') == 'Y.GYY'; assert reply_for('GEESE', 'EPEES') == '.YGYY'\n",
"assert reply_for('WHEEE', 'PEEVE') == '..GYG'; assert reply_for('PEEVE', 'WHEEE') == '.YG.G'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Consistent Target Words\n",
"\n",
"A key concept in Wordle is the idea of **consistent target words**. If I guess `'NINNY'` and the reply is `'Y.G..'`, then the target word could be `'ANNEX'`, but it could also be `'ANNUL'` or `'CANON'`. We say these three words are **consistent** with the guess/reply pair. If we next guess `'ENNUI'` and get the reply `'YGG..'`, then `'ANNEX'` is the only consistent target. When there is a single consistent target left, the guesser can always get it on the next guess. In general, given a word list, I can always determine the list of consistent targets from a sequence of guess/reply pairs. Once I know the consistent words, the guess/reply pairs themselves provide no additional useful information. "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"def consistent_targets(targets, guess, reply) -> List[Word]: \n",
" \"\"\"All the words in `targets` that give this `reply` to this `guess`.\"\"\"\n",
" return [target for target in targets if reply_for(guess, target) == reply]\n",
"\n",
"assert consistent_targets(wordlist, 'NINNY', 'Y.G..') == ['ANNEX', 'ANNUL', 'CANON']\n",
"assert consistent_targets(consistent_targets(wordlist, 'NINNY', 'Y.G..'), 'ENNUI', 'YGG..') == ['ANNEX']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Playing Wordle\n",
"\n",
"The function `play` will play a game of Wordle and return the score (the number of guesses). The arguments are:\n",
"- `guesser`: a `callable` (e.g., a function) that should return the guess to make. The guesser is passed two arguments: \n",
" - The **reply** to the previous guess.\n",
" - A list of **consistent target words**. (A word is **consistent** if it\n",
" gives the same replies to all the guesses made so far as the replies that were actually received.)\n",
"- `wordlist`: The list of allowable words.\n",
"- `target`: The target word. If none is given, the target word is chosen at random from the wordlist.\n",
"- `verbose`: Unless false, print a message for each guess.\n",
"\n",
"Two corner cases: \n",
"1. If the guesser improperly guesses a non-word, the reply is `'unknown'`. \n",
"2. To prevent an infinite loop with a bad guesser, the worst score you can get is the number of words in the wordlist plus 1."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"def play(guesser, wordlist=wordlist, target=None, verbose=True) -> Score:\n",
" \"\"\"The number of guesses it take for `guesser` to guess the Jotto word,\n",
" which is given by `target` or selected from the words in `wordlist`?\"\"\"\n",
" target = target or random.choice(wordlist) # Choose a random target if none was given\n",
" targets = wordlist # The targets that are consistent with all guess/reply pairs\n",
" reply = None # For the first guess, there is no previous reply\n",
" N = len(wordlist)\n",
" for turn in range(1, N + 1):\n",
" guess = guesser(reply, targets)\n",
" reply = reply_for(guess, target) if guess in wordlist else 'unknown'\n",
" targets = consistent_targets(targets, guess, reply)\n",
" if verbose: \n",
" print(f'Guess {turn}: {guess}, Reply: {reply}; Remaining targets: {len(targets)}')\n",
" if reply == Correct: \n",
" return turn\n",
" return N + 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To play a game, we will need a guesser. Here are two simple ones:\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"def human_guesser(reply, targets) -> Word: \n",
" \"\"\"Ask a human to make a guess.\"\"\"\n",
" return input(f'Reply was {reply}. Your guess? ')\n",
"\n",
"def random_guesser(reply, targets) -> Word: \n",
" \"\"\"Choose a guess at random from the consistent targets.\"\"\"\n",
" return random.choice(targets)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Sample Wordle Games\n",
"\n",
"Here is the `random_guesser` in action:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: VALUE, Reply: .....; Remaining targets: 313\n",
"Guess 2: NOTCH, Reply: .Y...; Remaining targets: 21\n",
"Guess 3: PROXY, Reply: YGG..; Remaining targets: 1\n",
"Guess 4: DROOP, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(random_guesser)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: SLAIN, Reply: ....G; Remaining targets: 25\n",
"Guess 2: TOKEN, Reply: ....G; Remaining targets: 1\n",
"Guess 3: CHURN, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(random_guesser)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: SMOKE, Reply: ..Y.Y; Remaining targets: 64\n",
"Guess 2: VOWEL, Reply: .Y.YY; Remaining targets: 3\n",
"Guess 3: FELON, Reply: .GGY.; Remaining targets: 2\n",
"Guess 4: CELLO, Reply: .GGGG; Remaining targets: 1\n",
"Guess 5: HELLO, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"5"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(random_guesser, target='HELLO')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Partitioning Target Words\n",
"\n",
"We can think of a guess as **partitioning** the consistent targets into different **branches** of a tree, each branch corresponding to a different reply:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"Partition = Dict[Reply, List[str]]\n",
"\n",
"def partition(guess, targets) -> Partition:\n",
" \"\"\"A guess partition targets by the possible replies to guess: {reply: [word, ...]}.\"\"\"\n",
" branches = defaultdict(list)\n",
" for target in targets:\n",
" branches[reply_for(guess, target)].append(target)\n",
" return branches"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A partition for the full wordlist would be too big to look at, so let's pick out a few words (every 100th one, so that's 24 words), and partition them by two different guesses. First, the few words partitioned by `'ROAST'`:"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(list,\n",
" {'..G..': ['ABACK', 'QUACK'],\n",
" 'YYY..': ['ARBOR'],\n",
" 'Y...Y': ['BIRTH', 'TREND'],\n",
" '.....': ['BULLY', 'CUMIN'],\n",
" '..GG.': ['CLASP', 'PHASE'],\n",
" 'YY...': ['DROOL', 'HUMOR'],\n",
" '..Y..': ['FANCY', 'NINJA'],\n",
" 'Y.G..': ['FRANK'],\n",
" 'Y.G.Y': ['GRATE'],\n",
" 'Y.Y.Y': ['LATER'],\n",
" '.YYY.': ['MASON'],\n",
" 'GGGGG': ['ROAST'],\n",
" '..GY.': ['SHALE'],\n",
" '...Y.': ['SMELL'],\n",
" '..GYY': ['STAMP'],\n",
" '..Y.Y': ['TAKEN'],\n",
" 'Y.Y..': ['VIRAL'],\n",
" '..Y.G': ['YACHT']})"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"few = wordlist[::100]\n",
"\n",
"partition('ROAST', few)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"No matter what the reply to `'ROAST'` is, we will be left with no more than 2 remaining possible targets, so we will always be able to win in no more than 3 total guesses. Now, partition by `'NINJA'`:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(list,\n",
" {'....Y': ['ABACK',\n",
" 'ARBOR',\n",
" 'CLASP',\n",
" 'GRATE',\n",
" 'LATER',\n",
" 'PHASE',\n",
" 'QUACK',\n",
" 'ROAST',\n",
" 'SHALE',\n",
" 'STAMP',\n",
" 'YACHT'],\n",
" '.G...': ['BIRTH'],\n",
" '.....': ['BULLY', 'DROOL', 'HUMOR', 'SMELL'],\n",
" 'YY...': ['CUMIN'],\n",
" '..G.Y': ['FANCY'],\n",
" 'Y...Y': ['FRANK', 'MASON', 'TAKEN'],\n",
" 'GGGGG': ['NINJA'],\n",
" 'Y....': ['TREND'],\n",
" '.G..Y': ['VIRAL']})"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"partition('NINJA', few)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Almost half the time we get a reply of `'....Y'`, and there are 11 possible target words remaining. That suggests that `'ROAST'` is a better guess and that a good strategy is: **guess a word that partitions the possible remaining targets into small branches.**\n",
"\n",
"To do this we only need to know the *size* of each branch, not the list of words therein, so we could use `partition_counts`:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [],
"source": [
"def partition_counts(guess, targets) -> List[int]: \n",
" \"The sizes of the branches of a partition of targets by guess.\"\n",
" counter = Counter(reply_for(guess, target) for target in targets)\n",
" return sorted(counter.values())"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"assert partition_counts('ROAST', few) == [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]\n",
"assert partition_counts('NINJA', few) == [1, 1, 1, 1, 1, 1, 3, 4, 11]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Metrics for Minimizing Partitions\n",
"\n",
"We want partitions with **small branches**, but what exactly does that mean? Ideally, we want the partition that minimizes the average number of additional guesses it will take to finish the game (and possibly also that minimizes the number of times that we more than 6 guesses). However, just looking at a single partition (without looking ahead further) can't tell us what we want to know, so instead we can minimize one of the following proxy metrics:\n",
"\n",
"- **Maximum**: choose the partition that minimizes the size of the largest branch.\n",
"\n",
"- **Expectation**: In probability theory, the expectation (also known as expected value) is the weighted average of a random variable. Here it means the sum, over all branches, of the probability of ending up in the branch multiplied by the size of the branch. We are assuming that every target is equally likely, so the probability of a branch is proportional to the number of targets in it.\n",
"\n",
"- **Negative Entropy**: In information theory, entropy is the weighted average amount of \"information\" measured in bits. The calculation is the same as expectation except that we count the base 2 logarithm of the branch sizes, not the branches sizes themselves. You can think of the base 2 logarithm as the number of times that you need to cut a branch in half to get it down to one word. We want to maximize entropy, or minimize *negative* entropy.\n",
"\n",
"The maximum is just the builtin `max` function; here are the other two metrics:"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"def expectation(counts: List[int]) -> float:\n",
" \"The expected value of the counts.\"\n",
" N = sum(counts)\n",
" def P(x): return x / N\n",
" return sum(P(x) * x for x in counts)\n",
"\n",
"def neg_entropy(counts: List[int]) -> float: \n",
" \"\"\"The negation of the entropy of the counts.\"\"\"\n",
" N = sum(counts)\n",
" def P(x): return x / N\n",
" return sum(P(x) * log2(P(x)) for x in counts)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Caching Best Guesses: Guess Trees\n",
"\n",
"Going through every word in the wordlist to decide which one makes the best partition takes some time. I would prefer to do that computation just once and cache it, rather than have to repeat the computation in every new game. I will cache the best guesses in a structure called a **guess tree**: a tree that has branches for every possible path the game might take, with the best guess for each situation precomputed. Some people call this a **policy**: a guideline that tells you what to do in any situation. A guess tree is either:\n",
"- An **interior node**, which has a guess and a dict of branches, `Node(guess, {reply: subtree, ...})`, where each subtree covers all the target words that are consistent with the corresponding reply.\n",
"- A **leaf word**, indicating the sole remaining consistent target word. Every word in the word list appears as a leaf in exactly one place in the tree."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"@dataclass \n",
"class Node:\n",
" \"\"\"A node in a guess tree stores the best guess, the number of targets covered, and a branch for every reply.\"\"\"\n",
" guess: Word\n",
" size: int\n",
" branches: Dict[Reply, 'Tree']\n",
"\n",
"Tree = Union[Node, Word] # A Tree is either an interior Node or a leaf Word"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function `minimizing_tree(metric, targets)` builds a guess tree that covers all the targets and that, at every node, guesses a word that minimizes the `metric` applied to the `partition_counts` of the guess."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [],
"source": [
"def minimizing_tree(metric, targets) -> Tree:\n",
" \"\"\"Make a tree that picks guesses that minimize metric(partition_counts(guess, targets)).\"\"\"\n",
" if len(targets) == 1:\n",
" return targets[0]\n",
" else:\n",
" guess = min(targets, key=lambda guess: metric(partition_counts(guess, targets))) \n",
" branches = partition(guess, targets)\n",
" return Node(guess, len(targets), \n",
" {reply: minimizing_tree(metric, branches[reply]) \n",
" for reply in branches})"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is a minimizing tree that covers the 24 `few` words. The tree says that the first guess, `\"ROAST\"`, covers 24 target words, and for 12 replies there is only one word left, but for the first 6 replies a second guess is required. Either that second guess will be right, or we will need a third guess.\n",
"\n",
"if the reply is `0` the next guess is `\"would\"`. If, say, the reply to `\"would\"` is 4, then there is only one other word left, the leaf word `'cloud'`. If the reply is 5, that means `\"would\"` was correct. I won't go through the other branches of the tree."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"assert (minimizing_tree(max, few) == \n",
" Node(\"ROAST\", 24,\n",
" {'..G..': Node(\"ABACK\", 2, {'GGGGG': 'ABACK', '..GGG': 'QUACK'}), \n",
" 'Y...Y': Node(\"BIRTH\", 2, {'GGGGG': 'BIRTH', '..YY.': 'TREND'}), \n",
" '.....': Node(\"BULLY\", 2, {'GGGGG': 'BULLY', '.G...': 'CUMIN'}), \n",
" '..GG.': Node(\"CLASP\", 2, {'GGGGG': 'CLASP', '..GGY': 'PHASE'}), \n",
" 'YY...': Node(\"DROOL\", 2, {'GGGGG': 'DROOL', '.Y.G.': 'HUMOR'}), \n",
" '..Y..': Node(\"FANCY\", 2, {'GGGGG': 'FANCY', '.YG..': 'NINJA'}), \n",
" 'YYY..': 'ARBOR', \n",
" 'Y.G..': 'FRANK', \n",
" 'Y.G.Y': 'GRATE', \n",
" 'Y.Y.Y': 'LATER', \n",
" '.YYY.': 'MASON', \n",
" 'GGGGG': 'ROAST', \n",
" '..GY.': 'SHALE', \n",
" '...Y.': 'SMELL', \n",
" '..GYY': 'STAMP', \n",
" '..Y.Y': 'TAKEN', \n",
" 'Y.Y..': 'VIRAL', \n",
" '..Y.G': 'YACHT'}))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Turning a Tree into a Guesser\n",
"\n",
"A tree is not a guesser, but we can easily make a guesser from a tree. A `TreeGuesser` works as follows:\n",
"- When *initialized*, it takes a tree as input, and stores the tree under the `.root` attribute.\n",
"- When *called*, it sets the `.tree` attribute as follows:\n",
" - For the first turn in a game (when the reply is `None`), it resets `.tree` to `.root`.\n",
" - On subsequent turns, it updates `.tree` to be the branch corresponding to the reply.\n",
"- When *called*, it then returns the guess for the current tree: either the `.guess` attribute or the leaf word. "
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [],
"source": [
"class TreeGuesser:\n",
" \"\"\"Given a guess tree, use it to create a callable Guesser that can play Wordle.\"\"\"\n",
" def __init__(self, tree): self.root = tree\n",
" \n",
" def __call__(self, reply, targets) -> Word:\n",
" \"\"\"If reply is `None`, start a new game; otherwise follow the branch for the `reply`.\n",
" Then return the current leaf or interior node guess. (Ignore `targets`.)\"\"\"\n",
" self.tree = self.root if reply is None else self.tree.branches[reply]\n",
" return self.tree.guess if isinstance(self.tree, Node) else self.tree"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here we build a tree that minimizes the maximum branch size (over the full wordlist) and make a guesser out of it:"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 24.3 s, sys: 596 ms, total: 24.9 s\n",
"Wall time: 26.2 s\n"
]
}
],
"source": [
"%time guesser = TreeGuesser(minimizing_tree(max, wordlist))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Sample Games with the Minimizing Guesser\n"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: ARISE, Reply: ..Y..; Remaining targets: 107\n",
"Guess 2: UNTIL, Reply: ..GY.; Remaining targets: 10\n",
"Guess 3: DITCH, Reply: .GG.Y; Remaining targets: 1\n",
"Guess 4: PITHY, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(guesser)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: ARISE, Reply: ....Y; Remaining targets: 120\n",
"Guess 2: TOWEL, Reply: .GYG.; Remaining targets: 3\n",
"Guess 3: WOKEN, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(guesser)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: ARISE, Reply: ....Y; Remaining targets: 120\n",
"Guess 2: TOWEL, Reply: .Y.YY; Remaining targets: 5\n",
"Guess 3: CELLO, Reply: .GGGG; Remaining targets: 1\n",
"Guess 4: HELLO, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(guesser, target='HELLO')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Inconsistent Guesses and \"Hard Mode\"\n",
"\n",
"So far, we have always guessed a **consistent** word. That seems reasonable; why waste a guess on a word that could not possibly be the target? But it turns out that in some cases it ***is*** a good strategy to guess such a word.\n",
"\n",
"Suppose the entire word list consisted of these nine words:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [],
"source": [
"ails = ['BAILS', 'FAILS', 'HAILS', 'NAILS', 'PAILS', 'RAILS', 'SAILS', 'TAILS', 'WAILS']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we guessed any one of the nine words, there would be a 1/9 chance of being correct, and a 8/9 chance of getting the reply `'.GGGG'`, which adds no new information, and leaves us with 8 similar words to choose from. Overall, we'd expect to take 5 guesses on average, with 9 in the worst case. Not a good performance. \n",
"\n",
"On the other hand, we could make an inconsistent guess. This sacrifices the 1/9 chance of being correct on the first guess, but gives us more new information for subsequent guesses. For example, `'BERTH'` is a good first guess:"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(list,\n",
" {'G....': ['BAILS'],\n",
" '.....': ['FAILS', 'NAILS', 'PAILS', 'SAILS', 'WAILS'],\n",
" '....Y': ['HAILS'],\n",
" '..Y..': ['RAILS'],\n",
" '...Y.': ['TAILS']})"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"partition('BERTH', ails)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"After `'BERTH'`, we have a 4/9 chance of being correct on the second guess, and a 5/9 chance of having just 5 remaining words. The 5 can be handled with another inconsistent guess:"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"defaultdict(list,\n",
" {'Y.Y..': ['FAILS'],\n",
" 'Y.Y.Y': ['NAILS'],\n",
" 'YYY..': ['PAILS'],\n",
" 'G.Y..': ['SAILS'],\n",
" 'Y.YY.': ['WAILS']})"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"partition('SPAWN', ['FAILS', 'NAILS', 'PAILS', 'SAILS', 'WAILS'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Wordle has an option to play in **hard mode**, where only consistent guesses are allowed. Why is that called \"hard mode\"? One reason is that it can be a little bit hard for a human without access to a computer to verify that a guess is consistent. But more importantly, it is hard to win the game in hard mode if you get stuck in a situation like the `ails` list, where there are many targets remaining, but you are forced to make guesses that give no new information.\n",
"\n",
"To allow for inconsistent guesses, I will redefine `minimizing_tree` so that it is passed both the list of remaining consistent target words and the complete word list. It also takes a flag, `inconsistent`. When this flag is true, any word in the wordlist can be considered as a guess; when false, only consistent targets are considered, as before. (Note: when there are 3 or fewer target words left there is no use considering inconsistent guesses, since they cannot improve the average score over a consistent guess. Also, when there are many targets, the odds are one of them will be as good as any inconsistent guess. The value of *many* was empirically chosen as `inconsistent_max = 125`.)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [],
"source": [
"def minimizing_tree(metric, targets, wordlist=wordlist, inconsistent=False) -> Tree:\n",
" \"\"\"Make a tree that picks guesses that minimize metric(partition_counts(guess, targets)).\"\"\"\n",
" if len(targets) == 1:\n",
" return targets[0]\n",
" else:\n",
" guesses = wordlist if (inconsistent and (3 < len(targets) <= inconsistent_max)) else targets\n",
" guess = min(guesses, key=lambda guess: metric(partition_counts(guess, targets))) \n",
" branches = partition(guess, targets)\n",
" return Node(guess, len(targets), \n",
" {reply: minimizing_tree(metric, branches[reply], wordlist, inconsistent) \n",
" for reply in branches})\n",
" \n",
"inconsistent_max = 125"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [],
"source": [
"assert (minimizing_tree(max, ails, inconsistent=True) == \n",
" Node(\"BERTH\", 9,\n",
" {'.....': Node(\"SPAWN\", 5,\n",
" {'G.Y..': 'SAILS', \n",
" 'Y.Y..': 'FAILS', \n",
" 'Y.Y.Y': 'NAILS', \n",
" 'Y.YY.': 'WAILS', \n",
" 'YYY..': 'PAILS'}), \n",
" '....Y': 'HAILS', \n",
" '...Y.': 'TAILS', \n",
" '..Y..': 'RAILS', \n",
" 'G....': 'BAILS'}))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Evaluating and Reporting on Guessers\n",
"\n",
"I'll introduce three functions that together will evaluate a guesser and produce a report:\n",
"\n",
"- `report_minimizing_tree` builds a minimizing tree, gets its tree scores, and calls `report`.\n",
"- `report` takes a list of scores and reports the following statistics:\n",
" - The median, mean, standard deviation, and worst case number of guesses, and total number of scores.\n",
" - The cumulative percentages guessed correctly (e.g., `\"≤5:11%\"` means 11% of the targets took 5 or fewer guesses).\n",
" - A histogram of scores.\n",
"- `tree_scores` takes a guesser and returns a list of *all* the scores it would make for *all* its targets. For each subtree branch in the tree there are three cases:\n",
" - If the subtree is a leaf word that is the same as the node's guess, we're done; it took one guess.\n",
" - If the subtree is a leaf word that is not the guess, it took two guesses: one for the incorrect guess and one for the leaf word.\n",
" - If the subtree is a Node, add one to each of the scores from the subtree and yield those scores."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"def report_minimizing_tree(metric, targets=wordlist, wordlist=wordlist, inconsistent=False):\n",
" \"\"\"Build a minimizing tree and report on its scores.\"\"\"\n",
" print(f\"minimizing the {metric.__name__} of partition sizes over {len(targets):,d}\",\n",
" f\"targets; inconsistent guesses\", (\"allowed\" if inconsistent else \"prohibited\"))\n",
" tree = minimizing_tree(metric, targets, wordlist, inconsistent)\n",
" print(f'first guess: \"{tree.guess}\"')\n",
" report(tree_scores(tree))\n",
"\n",
"def report(scores: Iterable[Score]) -> None:\n",
" \"\"\"Report statistics and a histogram for these scores.\"\"\"\n",
" scores = list(scores)\n",
" ctr = Counter(scores)\n",
" bins = range(1, histogram_bins + 2)\n",
" scale = 100 / len(scores)\n",
" weights = [scale * ctr[score] for score in ctr]\n",
" plt.hist(list(ctr), weights=weights, align='left', rwidth=0.9, bins=bins)\n",
" plt.xticks(bins[:-1])\n",
" plt.xlabel('Number of guesses'); plt.ylabel('% of scores')\n",
" def cumulative_pct(g) -> str: \n",
" \"\"\"What percent of games requires no more than g guesses?\"\"\"\n",
" percent = scale * sum(ctr[i] for i in range(1, g + 1))\n",
" return f'≤{g}:{percent:.{1 if 99 < percent < 100 else 0}f}%'\n",
" print(f'median: {median(scores):.0f} guesses, mean: {mean(scores):.2f}',\n",
" f'± {stdev(scores):.2f}, worst: {max(scores)}, best: {min(scores)}\\n'\n",
" 'cumulative:', ', '.join(map(cumulative_pct, range(2, 11))))\n",
" \n",
"def tree_scores(node: Node) -> Iterable[Score]:\n",
" \"\"\"All the scores for playing all the target words in the tree under `node`.\"\"\"\n",
" for subtree in node.branches.values():\n",
" if isinstance(subtree, Word):\n",
" yield 1 if subtree == node.guess else 2\n",
" else:\n",
" yield from (score + 1 for score in tree_scores(subtree))\n",
" \n",
"histogram_bins = 10 # The number of bins in the histogram created by `report` "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here are two reports for the 9-word `ails` list, with consistent guesses prohibited and allowed:"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"minimizing the max of partition sizes over 9 targets; inconsistent guesses prohibited\n",
"first guess: \"BAILS\"\n",
"median: 5 guesses, mean: 5.00 ± 2.74, worst: 9, best: 1\n",
"cumulative: ≤2:22%, ≤3:33%, ≤4:44%, ≤5:56%, ≤6:67%, ≤7:78%, ≤8:89%, ≤9:100%, ≤10:100%\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAATu0lEQVR4nO3de7hldV3H8ffHGVBADJUDKZijRpiRCoyIYqSAhkKAdyjMRy2ylItd0S6W3TTLEJ+iCAR6IIy45CUekbhUlg3OIMLgSBQicXOOoaCQwMS3P9aaOhxnzmwb1toz83u/nuc8e+919tnf75rLZ6/zW3v9fqkqJEnteNS0G5Akjcvgl6TGGPyS1BiDX5IaY/BLUmMWT7uBSey44461ZMmSabchSZuVFStWfLWqZuZv3yyCf8mSJSxfvnzabUjSZiXJl9e13aEeSWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqzGZx5e7GWHLi345a7+b3HtJc7Rb3udXaLe7z/NpbAo/4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNGSz4k3w4yeokK+dse0KSS5Pc2N8+fqj6kqR1G/KI/0zg4HnbTgQuq6rdgMv6x5KkEQ0W/FX1D8Bd8zYfDpzV3z8LOGKo+pKkdRt7jH/nqroDoL/daX1PTHJMkuVJls/Ozo7WoCRt6TbZk7tVdWpVLa2qpTMzM9NuR5K2GGMH/1eSPAmgv109cn1Jat7Ywf8x4I39/TcCHx25viQ1b8iPc54LfAbYPcmtSd4CvBd4aZIbgZf2jyVJI1o81AtX1VHr+daBQ9WUJG3YJntyV5I0DINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjZlK8Cd5R5Lrk6xMcm6Sx0yjD0lq0ejBn2QX4DhgaVXtASwCjhy7D0lq1bSGehYD2yRZDGwL3D6lPiSpOaMHf1XdBvwBcAtwB3B3VX1q/vOSHJNkeZLls7OzY7cpSVusaQz1PB44HHga8GRguyRHz39eVZ1aVUuraunMzMzYbUrSFmsaQz0HAV+qqtmqehC4EHjhFPqQpCZNI/hvAfZNsm2SAAcCq6bQhyQ1aRpj/MuA84Grgev6Hk4duw9JatXiaRStqncD755GbUlqnVfuSlJjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhqzweBP8tok2/f3fzXJhUn2Gr41SdIQJjni/7Wq+kaSFwE/ApwFnDJsW5KkoUwS/P/d3x4CnFJVHwW2Hq4lSdKQJgn+25L8GfA64OIkj57w5yRJm6BJAvx1wCXAwVX1deAJwC8O2ZQkaTgbDP6qug9YDbyo37QGuHHIpiRJw5nkUz3vBn4ZeGe/aSvg7CGbkiQNZ5KhnlcChwH3AlTV7cD2QzYlSRrOJMH/QFUVUABJthu2JUnSkCYJ/vP6T/XskOSngL8D/nzYtiRJQ1lw6cV+MfS/Ap4J3APsDvx6VV06Qm+SpAEsGPxVVUn+pqr2Bgx7SdoCTDLU8y9Jnjd4J5KkUSx4xN97CfDWJDfTfbIndL8MPHvIxiRJw5gk+F8+eBeSpNFMcuXul4EdgB/tv3bot0mSNkOTXLl7PHAOsFP/dXaSY4duTJI0jEmGet4CPL+q7gVI8j7gM8CHhmxMkjSMST7VE/5vTn76+xmmHUnS0CY54j8DWJbkov7xEcDpg3UkSRrUJCd3PwC8CbgL+Brwpqo6aWOKJtkhyflJvphkVZIXbMzrSZImt8Ej/iT7AtdX1dX94+2TPL+qlm1E3Q8Cn6yq1yTZGth2I15LkvQdmGSM/xTgm3Me38tGLLae5HHA/vTDRVX1QL+ylyRpBBOd3O2nZQagqh5isnMD6/N0YBY4I8nnkpy2rqmekxyTZHmS5bOzsxtRTpI01yTBf1OS45Js1X8dD9y0ETUXA3sBp1TVnnS/QZw4/0lVdWpVLa2qpTMzMxtRTpI01yTB/1bghcBtwK3A84FjNqLmrcCtc84RnE/3RiBJGsEGh2yqajVw5CNVsKruTPIfSXavqhuAA4EvPFKvL0la2CRTNvx+ksf1wzyXJflqkqM3su6xwDlJrgWeC/zuRr6eJGlCkwz1vKyq7gEOpRum+T7gFzemaFVd04/fP7uqjqiqr23M60mSJjdJ8G/V374COLeq7hqwH0nSwCb5WObHk3wR+C/gZ5PMAN8ati1J0lAmmbLhROAFwNKqehC4Dzh86MYkScOY6EKsuWPw/fTM9w7WkSRpUJOM8UuStiDrDf4k+/W3jx6vHUnS0BY64j+5v/3MGI1Iksax0Bj/g0nOAHZJcvL8b1bVccO1JUkaykLBfyhwEHAAsGKcdiRJQ1tv8FfVV4GPJFlVVZ8fsSdJ0oAm+VTPfya5KMnqJF9JckGSXQfvTJI0iEmC/wzgY8CTgV2Aj/fbJEmboUmCf6eqOqOq1vRfZwKujCJJm6lJgn82ydFJFvVfRwP/OXRjkqRhTBL8bwZeB9wJ3AG8pt8mSdoMTbIC1y3AYSP0IkkagXP1SFJjDH5JaozBL0mNmTj4k+yb5PIk/5TkiAF7kiQNaL0nd5N8d1XdOWfTz9Gd5A3wz8DfDNuaJGkIC32q50+TrADeX1XfAr4O/BjwEHDPCL1Jkgaw3qGeqjoCuAb4RJI3ACfQhf62wBHDtyZJGsKCY/xV9XHgR4AdgAuBG6rq5KqaHaE3SdIAFlp68bAknwYuB1YCRwKvTHJukmeM1aAk6ZG10Bj/bwMvALYBLq6qfYCfS7Ib8Dt0bwSSpM3MQsF/N124bwOsXruxqm7E0JekzdZCY/yvpDuRu4bu0zySpC3AhpZe/NBQhZMsApYDt1XVoUPVkSQ93DSnbDgeWDXF+pLUpKkEf79m7yHAadOoL0ktm9YR/0nAL9FdELZOSY5JsjzJ8tlZLxuQpEfK6MGf5FBgdVWtWOh5VXVqVS2tqqUzMy7xK0mPlGkc8e8HHJbkZuAjwAFJzp5CH5LUpNGDv6reWVW7VtUSuusBLq+qo8fuQ5Ja5UIsktSYDS62PqSquhK4cpo9SFJrPOKXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSY0YP/iRPSXJFklVJrk9y/Ng9SFLLFk+h5hrg56vq6iTbAyuSXFpVX5hCL5LUnNGP+Kvqjqq6ur//DWAVsMvYfUhSq6Y6xp9kCbAnsGyafUhSS6YW/EkeC1wAnFBV96zj+8ckWZ5k+ezs7PgNStIWairBn2QrutA/p6ouXNdzqurUqlpaVUtnZmbGbVCStmDT+FRPgNOBVVX1gbHrS1LrpnHEvx/wBuCAJNf0X6+YQh+S1KTRP85ZVZ8GMnZdSVLHK3clqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhozleBPcnCSG5L8W5ITp9GDJLVq9OBPsgj4Y+DlwLOAo5I8a+w+JKlV0zji3wf4t6q6qaoeAD4CHD6FPiSpSamqcQsmrwEOrqqf7B+/AXh+Vb193vOOAY7pH+4O3DBqo7Aj8NWRa067dov73GrtFve5xdpPraqZ+RsXj9wEQNax7dvefarqVODU4dtZtyTLq2ppS7Vb3OdWa7e4zy3Xnm8aQz23Ak+Z83hX4PYp9CFJTZpG8H8W2C3J05JsDRwJfGwKfUhSk0Yf6qmqNUneDlwCLAI+XFXXj93HBKY2zDTF2i3uc6u1W9znlms/zOgndyVJ0+WVu5LUGINfkhpj8M+T5MNJVidZOXLdpyS5IsmqJNcnOX7E2o9JclWSz/e1f3Os2n39RUk+l+QTY9bta9+c5Lok1yRZPmLdHZKcn+SL/d/5C0aqu3u/r2u/7klywhi1+/rv6P+NrUxybpLHjFT3+L7m9UPv77oyJMkTklya5Mb+9vFD9rAhBv+3OxM4eAp11wA/X1XfD+wLvG3EqSzuBw6oqucAzwUOTrLvSLUBjgdWjVhvvpdU1XNH/oz1B4FPVtUzgecw0v5X1Q39vj4X2Bu4D7hojNpJdgGOA5ZW1R50H+44coS6ewA/RTdrwHOAQ5PsNmDJM/n2DDkRuKyqdgMu6x9PjcE/T1X9A3DXFOreUVVX9/e/QRcEu4xUu6rqm/3DrfqvUc76J9kVOAQ4bYx6m4IkjwP2B04HqKoHqurrU2jlQODfq+rLI9ZcDGyTZDGwLeNcw/P9wL9U1X1VtQb4e+CVQxVbT4YcDpzV3z8LOGKo+pMw+DdBSZYAewLLRqy5KMk1wGrg0qoaq/ZJwC8BD41Ub74CPpVkRT9NyBieDswCZ/RDXKcl2W6k2nMdCZw7VrGqug34A+AW4A7g7qr61AilVwL7J3likm2BV/Dwi0jHsHNV3QHdQR6w08j1H8bg38QkeSxwAXBCVd0zVt2q+u/+1/9dgX36X48HleRQYHVVrRi61gL2q6q96GaLfVuS/UeouRjYCzilqvYE7mXkX/37iycPA/56xJqPpzvyfRrwZGC7JEcPXbeqVgHvAy4FPgl8nm5otVkG/yYkyVZ0oX9OVV04jR76IYcrGec8x37AYUluppul9YAkZ49Q939V1e397Wq6se59Rih7K3DrnN+qzqd7IxjTy4Grq+orI9Y8CPhSVc1W1YPAhcALxyhcVadX1V5VtT/dMMyNY9Sd4ytJngTQ364euf7DGPybiCShG/NdVVUfGLn2TJId+vvb0P0H/eLQdavqnVW1a1UtoRt2uLyqBj8CXCvJdkm2X3sfeBndsMCgqupO4D+S7N5vOhD4wtB15zmKEYd5ercA+ybZtv/3fiAjndROslN/+z3Aqxh/3z8GvLG//0bgoyPXf5hpzM65SUtyLvBiYMcktwLvrqrTRyi9H/AG4Lp+rB3gXVV18Qi1nwSc1S+S8yjgvKoa/aOVU7AzcFGXQSwG/rKqPjlS7WOBc/ohl5uAN41Ul36c+6XAT49VE6CqliU5H7iabqjlc4w3jcEFSZ4IPAi8raq+NlShdWUI8F7gvCRvoXsDfO1Q9SfhlA2S1BiHeiSpMQa/JDXG4Jekxhj8ktQYg1+SGmPwa+qSVJI/nPP4F5L8xiP02mcmec0j8VobqPPafpbNK4auJW0sg1+bgvuBVyXZcdqNzNVf1zCptwA/W1UvGaof6ZFi8GtTsIbuQp53zP/G/CP2JN/sb1+c5O+TnJfkX5O8N8mP9+sKXJfkGXNe5qAk/9g/79D+5xcleX+Szya5NslPz3ndK5L8JXDdOvo5qn/9lUne12/7deBFwJ8mef+85z8qyZ/088B/IsnFa/cn3VoAO/b3lya5sr+/XT+n+2f7SdwO77f/QL9/1/Q979Y/92/TraWwMsnr++fu3f/5rEhyyZzpAo5L8oX+5z/y//i70hbAK3e1qfhj4Nokv/8d/Mxz6KbcvYvu6tfTqmqfdIvYHAuc0D9vCfDDwDOAK5J8L/ATdLNDPi/Jo4F/SrJ2psh9gD2q6ktziyV5Mt1kX3sDX6Ob1fOIqnpPkgOAX6iq+Yu5vKqv/4N0MzKuAj68gf36FbrpK97cT6VxVZK/A94KfLCq1l7xu4hupsnbq+qQvsfv6ud8+hBweFXN9m8GvwO8mW4yuKdV1f1rp+lQezzi1yahn4n0L+gW6pjUZ/t1DO4H/h1YG9zX0YXtWudV1UNVdSPdG8Qz6ebl+Yl+eoxlwBOBtYtzXDU/9HvPA67sJxlbA5xDN6/+Ql4E/HVf/05gknMALwNO7Hu7EngM8D3AZ4B3Jfll4KlV9V/9vh6U5H1Jfqiq7gZ2B/YALu1f41fpZl0FuJZuqoijaXyGypZ5xK9NyUl087icMWfbGvoDlH5ir63nfO/+OfcfmvP4IR7+b3v+vCQFBDi2qi6Z+40kL6abJnldsoH+v9Of+d99owv3uT/z6qq6Yd7zVyVZRrdwzSVJfrKqLk+yN92R/+/1v7VcBFxfVetazvEQujerw4BfS/ID/ZuYGuIRvzYZVXUXcB7didK1bqYbWoFuLvet/h8v/dp+rP0ZdIug3ABcAvxMPyxCku/LhhdDWQb8cJId+xO/R9Gt5rSQTwOv7uvvTDd511o383/79uo52y8Bju3f6EiyZ3/7dOCmqjqZbrbHZ/fDT/dV1dl0i5zs1e/fTPp1fJNs1Z8feBTwlKq6gm7xmx2Ax26gf22BPOLXpuYPgbfPefznwEeTXEW3Vun6jsYXcgNdQO8MvLWqvpXkNLrhoKv7gJ1lA8vhVdUdSd5JN1wT4OKq2tD0uhfQTT+8EvhXujePu/vv/SZwepJ38fDV1n6L7refa/vebgYOBV4PHJ3kQeBO4D10w0/vT/IQ3cyTP1NVD/QnkE9O8l10/89P6uuf3W8L8EdTWvJRU+bsnNLAkjy2qr6Zblrgq+hW/bpz2n2pXR7xS8P7RP8Jmq2B3zL0NW0e8UtSYzy5K0mNMfglqTEGvyQ1xuCXpMYY/JLUmP8B09F+hV0IunwAAAAASUVORK5CYII=\n",
"text/plain": [
"
"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"%time report_minimizing_tree(neg_entropy, inconsistent=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The random guesser is also a consistent guesser. Here is a report on it (each run will give slightly different results):"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"median: 4 guesses, mean: 4.09 ± 1.04, worst: 9, best: 2\n",
"cumulative: ≤2:4%, ≤3:29%, ≤4:69%, ≤5:92%, ≤6:98%, ≤7:99.7%, ≤8:99.9%, ≤9:100%, ≤10:100%\n",
"CPU times: user 1.92 s, sys: 34.5 ms, total: 1.96 s\n",
"Wall time: 1.96 s\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAW+UlEQVR4nO3de7xdZX3n8c/XEAUBG5BDJgJtLKVoS0uAY6TFocjFIjBcVFqYQvOqtMGOILT2Ep3WSy+vgSpqcVqcyC0dEIcKFERHTAPU0qGBEwwhNNC0NDpAyDmIyG1EQr7zx3pSDycn5+yErLVPeL7v12u/9lpr77V/z+by3es8a63nkW0iIqIer+p3AyIiolsJ/oiIyiT4IyIqk+CPiKhMgj8iojI79LsBvdhjjz08e/bsfjcjImK7smzZssdtD4zdvl0E/+zZsxkaGup3MyIitiuSvjXe9nT1RERUJsEfEVGZBH9ERGUS/BERlUnwR0RUpvXglzRN0jcl3VzWd5e0WNLq8rxb222IiIgf6uKI/zxg1aj1BcAS2/sBS8p6RER0pNXgl7Q3cDxw6ajNJwGLyvIi4OQ22xARES/V9hH/Z4DfAzaM2jbT9lqA8rzneDtKmi9pSNLQyMhIy82MiKhHa3fuSjoBGLa9TNIRW7q/7YXAQoDBwcHMFrOdmL3gK53WW3PB8Z3Wi3glaHPIhsOAEyUdB+wIvE7SVcA6SbNsr5U0CxhusQ0RETFGa109tj9ke2/bs4HTgFttnwHcBMwrb5sH3NhWGyIiYlP9uI7/AuAYSauBY8p6RER0pJPROW3fDtxelr8DHNVF3YiI2FTu3I2IqEyCPyKiMgn+iIjKJPgjIiqT4I+IqEyCPyKiMgn+iIjKJPgjIiqT4I+IqEyCPyKiMgn+iIjKJPgjIiqT4I+IqEyCPyKiMgn+iIjKJPgjIiqT4I+IqExrwS9pR0l3SbpX0v2SPl62f0zSI5KWl8dxbbUhIiI21ebUi88DR9p+RtJ04A5J/7u89mnbn2yxdkREbEZrwW/bwDNldXp5uK16ERHRm1b7+CVNk7QcGAYW215aXjpH0gpJl0vabTP7zpc0JGloZGSkzWZGRFSl1eC3/aLtOcDewFxJBwCXAPsCc4C1wEWb2Xeh7UHbgwMDA202MyKiKp1c1WP7SeB24Fjb68oPwgbg88DcLtoQERGNNq/qGZA0oyzvBBwNPCBp1qi3nQKsbKsNERGxqTav6pkFLJI0jeYH5lrbN0v6n5Lm0JzoXQOc3WIbIiJijDav6lkBHDTO9jPbqhkREZPLnbsREZVJ8EdEVCbBHxFRmQR/RERlEvwREZVJ8EdEVCbBHxFRmQR/RERlEvwREZVJ8EdEVCbBHxFRmQR/RERlEvwREZVJ8EdEVCbBHxFRmQR/RERlEvwREZVpc87dHSXdJeleSfdL+njZvrukxZJWl+fd2mpDRERsqs0j/ueBI20fCMwBjpV0KLAAWGJ7P2BJWY+IiI60FvxuPFNWp5eHgZOARWX7IuDkttoQERGbarWPX9I0ScuBYWCx7aXATNtrAcrznpvZd76kIUlDIyMjbTYzIqIqrQa/7RdtzwH2BuZKOmAL9l1oe9D24MDAQGttjIioTSdX9dh+ErgdOBZYJ2kWQHke7qINERHRaPOqngFJM8ryTsDRwAPATcC88rZ5wI1ttSEiIja1Q4ufPQtYJGkazQ/MtbZvlnQncK2ks4BvA6e22IaIiBijteC3vQI4aJzt3wGOaqtuRERMLHfuRkRUJsEfEVGZBH9ERGUS/BERlUnwR0RUJsEfEVGZBH9ERGUS/BERlUnwR0RUJsEfEVGZBH9ERGUS/BERlUnwR0RUJsEfEVGZBH9ERGUmDX5Jp0ratSz/gaTrJR3cftMiIqINvRzx/6HtpyW9DfhFYBFwSbvNioiItvQS/C+W5+OBS2zfCLx6sp0k7SPpNkmrJN0v6byy/WOSHpG0vDyO2/rmR0TElupl6sVHJP0PmsnSL5T0Gnr7wVgPfND2PaWraJmkxeW1T9v+5NY1OXoxe8FXOqu15oLjO6sVES9fLwH+S8AtwLG2nwR2B353sp1sr7V9T1l+GlgF7LX1TY2IiG1h0uC3/RwwDLytbFoPrN6SIpJm00y8vrRsOkfSCkmXS9ptM/vMlzQkaWhkZGRLykVExAR6uarno8DvAx8qm6YDV/VaQNIuwHXA+bafojkxvC8wB1gLXDTefrYX2h60PTgwMNBruYiImEQvXT2nACcCzwLYfhTYtZcPlzSdJvSvtn192X+d7RdtbwA+D8zdmoZHRMTW6SX4f2DbgAEk7dzLB0sScBmwyvanRm2fNeptpwAre29uRES8XL1c1XNtuapnhqTfAN5Lc6Q+mcOAM4H7JC0v2z4MnC5pDs0PyRrg7C1sc0REvAwTBn85av9fwJuAp4D9gY/YXjzRfgC27wA0zktf3Yp2RkTENjJh8Nu2pL+xfQgwadhHRMTU10sf/z9KekvrLYmIiE700sf/duB9ktbQXNkjmj8GfrbNhkVERDt6Cf53tt6KiG2gy2EqIENVxParlzt3vwXMAP5Tecwo2yIiYjvUy5275wFXA3uWx1WSzm27YRER0Y5eunrOAt5q+1kASRcCdwKfbbNhERHRjl6u6hE/HJOfsjze9fkREbEd6OWI/wpgqaQbyvrJNEMxRETEdmjS4Lf9KUm30wzLLODXbH+z7YZFREQ7Jg1+SYcC92+cVEXSrpLeanvpJLtGRMQU1Esf/yXAM6PWnyWTrUdEbLd6OrlbhmUGoIyj38u5gYiImIJ6Cf6HJH1A0vTyOA94qO2GRUREO3oJ/vcBPw88AjwMvBWY32ajIiKiPb1c1TMMnNZBWyIiogO9DNnwZ5JeV7p5lkh6XNIZXTQuIiK2vV66et5h+yngBJqunp8EfneynSTtI+k2Sask3V/ODSBpd0mLJa0uz7u9rG8QERFbpJfgn16ejwOusf1Ej5+9Hvig7TcDhwLvl/RTwAJgie39gCVlPSIiOtJL8H9Z0gPAILBE0gDw/cl2sr12401ftp8GVgF7AScBi8rbFtEMARERER3pZTz+BcDPAYO2XwCeownvnkmaDRwELAVm2l5bPnstzVDP4+0zX9KQpKGRkZEtKRcRERPo5Ygf29+1/WJZftb2Y70WkLQLcB1wfjlX0BPbC20P2h4cGBjodbeIiJhET8G/tSRNpwn9q21fXzavkzSrvD4LGG6zDRER8VKbDX5Jh5Xn12zNB0sSzfDNq2x/atRLNwHzyvI84Mat+fyIiNg6Ex3xX1ye79zKzz4MOBM4UtLy8jgOuAA4RtJq4JiyHhERHZnozt0XJF0B7CXp4rEv2v7ARB9s+w42P1PXUb03MSIitqWJgv8E4GjgSGBZN82JiIi2bTb4bT8OfFHSKtv3dtimiIhoUS9X9XxH0g2ShiWtk3SdpL1bb1lERLSil+C/guZKnDfQ3Hn75bItIiK2Q70E/562r7C9vjyuBHJHVUTEdqqX4B+RdIakaeVxBvCdthsWERHt6CX43wv8EvAYsBZ4T9kWERHboV5m4Po2cGIHbYmIiA60OlZPRERMPQn+iIjKJPgjIirTc/BLOlTSrZL+QdLJLbYpIiJatNmTu5L+w5gJV36b5iSvgP8D/E27TYuIiDZMdFXP5yQtAz5h+/vAk8B/BjYAPc+kFRERU8tmu3psnwwsB26WdCZwPk3ov5ZMkB4Rsd2asI/f9peBXwRmANcDD9q+2HZmP4+I2E5NNPXiiZLuAG4FVgKnAadIukbSvl01MCIitq2Jjvj/hOZo/93AhbaftP3bwEeAP53sgyVdXoZyXjlq28ckPTJmKsaIiOjQRCd3v0dzlL8TMLxxo+3VZftkrgT+O/BXY7Z/2vYnt6yZERGxrUx0xH8KzYnc9TRX82wR298AntjKdkVEREsmuqrncduftf0529vy8s1zJK0oXUG7be5NkuZLGpI0NDKSc8kREdtK10M2XALsC8yhGeL5os290fZC24O2BwcGMu9LRMS20mnw215n+0XbG4DPA3O7rB8RER0Hv6RZo1ZPoblMNCIiOjTpRCxbS9I1wBHAHpIeBj4KHCFpDmBgDXB2W/UjImJ8rQW/7dPH2XxZW/UiIqI3GY8/IqIyCf6IiMok+CMiKpPgj4ioTII/IqIyCf6IiMok+CMiKpPgj4ioTII/IqIyCf6IiMok+CMiKpPgj4ioTII/IqIyCf6IiMok+CMiKpPgj4ioTII/IqIyrQW/pMslDUtaOWrb7pIWS1pdnndrq35ERIyvzSP+K4Fjx2xbACyxvR+wpKxHRESHWgt+298Anhiz+SRgUVleBJzcVv2IiBhf1338M22vBSjPe27ujZLmSxqSNDQyMtJZAyMiXumm7Mld2wttD9oeHBgY6HdzIiJeMboO/nWSZgGU5+GO60dEVK/r4L8JmFeW5wE3dlw/IqJ6bV7OeQ1wJ7C/pIclnQVcABwjaTVwTFmPiIgO7dDWB9s+fTMvHdVWzYiImNyUPbkbERHtSPBHRFQmwR8RUZkEf0REZRL8ERGVSfBHRFQmwR8RUZkEf0REZRL8ERGVSfBHRFQmwR8RUZkEf0REZRL8ERGVSfBHRFQmwR8RUZkEf0REZVqbiCWiJrMXfKXTemsuOL7TevHK0pfgl7QGeBp4EVhve7Af7YiIqFE/j/jfbvvxPtaPiKhS+vgjIirTr+A38HVJyyTNH+8NkuZLGpI0NDIy0nHzIiJeufoV/IfZPhh4J/B+SYePfYPthbYHbQ8ODAx038KIiFeovgS/7UfL8zBwAzC3H+2IiKhR58EvaWdJu25cBt4BrOy6HRERterHVT0zgRskbaz/Bdtf60M7IiKq1Hnw234IOLDruhER0cjlnBERlcmQDS3KbfwRMRXliD8iojIJ/oiIyiT4IyIqk+CPiKhMgj8iojIJ/oiIyiT4IyIqk+CPiKhMgj8iojK5czdiO9flHeK5O/yVIUf8ERGVSfBHRFQmwR8RUZkEf0REZRL8ERGV6UvwSzpW0oOS/kXSgn60ISKiVp1fzilpGvAXwDHAw8Ddkm6y/U9dtyUitl4mGtp+9eM6/rnAv5S5d5H0ReAkIMEfET3Jj87LI9vdFpTeAxxr+9fL+pnAW22fM+Z984H5ZXV/4MFOGwp7AI93XLPftWv8zrXWrvE711j7x2wPjN3YjyN+jbNtk18f2wuBhe03Z3yShmwP1lS7xu9ca+0av3PNtcfqx8ndh4F9Rq3vDTzah3ZERFSpH8F/N7CfpDdKejVwGnBTH9oREVGlzrt6bK+XdA5wCzANuNz2/V23owd962bqY+0av3OttWv8zjXXfonOT+5GRER/5c7diIjKJPgjIiqT4B9D0uWShiWt7LjuPpJuk7RK0v2Szuuw9o6S7pJ0b6n98a5ql/rTJH1T0s1d1i2110i6T9JySUMd1p0h6UuSHij/zn+uo7r7l++68fGUpPO7qF3q/1b5b2ylpGsk7dhR3fNKzfvb/r7jZYik3SUtlrS6PO/WZhsmk+Df1JXAsX2oux74oO03A4cC75f0Ux3Vfh440vaBwBzgWEmHdlQb4DxgVYf1xnq77TkdX2P958DXbL8JOJCOvr/tB8t3nQMcAjwH3NBFbUl7AR8ABm0fQHNxx2kd1D0A+A2aUQMOBE6QtF+LJa9k0wxZACyxvR+wpKz3TYJ/DNvfAJ7oQ921tu8py0/TBMFeHdW27WfK6vTy6OSsv6S9geOBS7uoNxVIeh1wOHAZgO0f2H6yD005CvhX29/qsOYOwE6SdgBeSzf38LwZ+Efbz9leD/wdcEpbxTaTIScBi8ryIuDktur3IsE/BUmaDRwELO2w5jRJy4FhYLHtrmp/Bvg9YENH9cYy8HVJy8owIV34cWAEuKJ0cV0qaeeOao92GnBNV8VsPwJ8Evg2sBb4nu2vd1B6JXC4pNdLei1wHC+9ibQLM22vheYgD9iz4/ovkeCfYiTtAlwHnG/7qa7q2n6x/Pm/NzC3/HncKkknAMO2l7VdawKH2T4YeCdN99rhHdTcATgYuMT2QcCzdPynf7l58kTgrzusuRvNke8bgTcAO0s6o+26tlcBFwKLga8B99J0rVYrwT+FSJpOE/pX276+H20oXQ630815jsOAEyWtAb4IHCnpqg7q/jvbj5bnYZq+7rkdlH0YeHjUX1Vfovkh6NI7gXtsr+uw5tHAv9kesf0CcD3w810Utn2Z7YNtH07TDbO6i7qjrJM0C6A8D3dc/yUS/FOEJNH0+a6y/amOaw9ImlGWd6L5H/SBtuva/pDtvW3Ppul2uNV260eAG0naWdKuG5eBd9B0C7TK9mPA/5W0f9l0FN0PS346HXbzFN8GDpX02vLf+1F0dFJb0p7l+UeBd9H9d78JmFeW5wE3dlz/JfoxOueUJuka4AhgD0kPAx+1fVkHpQ8DzgTuK33tAB+2/dUOas8CFpVJcl4FXGu780sr+2AmcEOTQewAfMH21zqqfS5wdelyeQj4tY7qUvq5jwHO7qomgO2lkr4E3EPT1fJNuhvG4DpJrwdeAN5v+7ttFRovQ4ALgGslnUXzA3hqW/V7kSEbIiIqk66eiIjKJPgjIiqT4I+IqEyCPyKiMgn+iIjKJPij7yRZ0kWj1n9H0se20WdfKek92+KzJqlzahll87a2a0W8XAn+mAqeB94laY9+N2S0cl9Dr84C/ovtt7fVnohtJcEfU8F6mht5fmvsC2OP2CU9U56PkPR3kq6V9M+SLpD0K2Vegfsk7TvqY46W9PflfSeU/adJ+oSkuyWtkHT2qM+9TdIXgPvGac/p5fNXSrqwbPsI8Dbgc5I+Meb9r5L0l2Uc+JslfXXj91EzF8AeZXlQ0u1leecypvvdZRC3k8r2ny7fb3lp837lvV9RM5fCSkm/XN57SPnns0zSLaOGC/iApH8q+39xK/5dxStA7tyNqeIvgBWS/mwL9jmQZsjdJ2jufr3U9lw1k9icC5xf3jcb+AVgX+A2ST8B/CrN6JBvkfQa4B8kbRwpci5wgO1/G11M0htoBvs6BPguzaieJ9v+I0lHAr9je+xkLu8q9X+GZkTGVcDlk3yv/0ozfMV7y1Aad0n6W+B9wJ/b3njH7zSakSYftX18aeOPlDGfPgucZHuk/Bj8KfBemsHg3mj7+Y3DdER9csQfU0IZifSvaCbq6NXdZR6D54F/BTYG9300YbvRtbY32F5N8wPxJppxeX61DI+xFHg9sHFyjrvGhn7xFuD2MsjYeuBqmnH1J/I24K9L/ceAXs4BvANYUNp2O7Aj8KPAncCHJf0+8GO2/1/5rkdLulDSf7T9PWB/4ABgcfmMP6AZdRVgBc1QEWdQ+QiVNcsRf0wln6EZx+WKUdvWUw5QysBerx712vOjljeMWt/AS//bHjsuiQEB59q+ZfQLko6gGSZ5PJqk/Vu6z79/N5pwH73Pu20/OOb9qyQtpZm45hZJv277VkmH0Bz5/7fyV8sNwP22x5vO8XiaH6sTgT+U9NPlRywqkiP+mDJsPwFcS3OidKM1NF0r0IzlPn0rPvrU0te+L80kKA8CtwC/WbpFkPSTmnwylKXAL0jao5z4PZ1mNqeJ3AG8u9SfSTN410Zr+OF3e/eo7bcA55YfOiQdVJ5/HHjI9sU0oz3+bOl+es72VTSTnBxcvt+Ayjy+kqaX8wOvAvaxfRvN5DczgF0maX+8AuWIP6aai4BzRq1/HrhR0l00c5Vu7mh8Ig/SBPRM4H22vy/pUpruoHtKwI4wyXR4ttdK+hBNd42Ar9qebHjd62iGH14J/DPNj8f3ymsfBy6T9GFeOtvaH9P89bOitG0NcALwy8AZkl4AHgP+iKb76ROSNtCMPPmbtn9QTiBfLOlHaP4//0ypf1XZJuDTfZryMfoso3NGtEzSLrafUTMs8F00s3491u92Rb1yxB/RvpvLFTSvBv44oR/9liP+iIjK5ORuRERlEvwREZVJ8EdEVCbBHxFRmQR/RERl/j8zz7YmhwAvgwAAAABJRU5ErkJggg==\n",
"text/plain": [
"
"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"%time report(play(random_guesser, target=target, verbose=False) for target in wordlist)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The random guesser strategy might have seemed hopelessly naive, but it is actually a pretty decent strategy, with mean number of guesses only about 15% worse than the best minimizing tree, and the same median number of guesses, 4. However, it does lose the game (by scoring more than 6) about 2% of the time."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Reports on Inconsistent Wordle Guessers\n",
"Now we'll report on trees with inconsistent guesses allowed. This will take double or triple as much time for each run."
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"minimizing the max of partition sizes over 2,309 targets; inconsistent guesses allowed\n",
"first guess: \"ARISE\"\n",
"median: 4 guesses, mean: 3.64 ± 0.66, worst: 6, best: 1\n",
"cumulative: ≤2:2%, ≤3:42%, ≤4:93%, ≤5:99.5%, ≤6:100%, ≤7:100%, ≤8:100%, ≤9:100%, ≤10:100%\n",
"CPU times: user 6.48 s, sys: 141 ms, total: 6.62 s\n",
"Wall time: 6.78 s\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAU4UlEQVR4nO3de7RfZX3n8fdHiIKIBSTJRJHGOhRtmXKLiIWxyMWiMIAXFGewWZWW2ipC79GpbW2na2KdOhZXx04KQmaBWCpQEBkxDdCOHQsERC4NNC2NDBJIBBWRFol854+9o4cQcn5A9j4Jz/u11ln7cn57f5/N5fPb59l7PztVhSSpHc+Z6QZIksZl8EtSYwx+SWqMwS9JjTH4Jakx2890Ayax++671/z582e6GZK0Tbnhhhu+XlWzN16/TQT//PnzWbFixUw3Q5K2KUm+uqn1dvVIUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjBn1yN8lq4NvA94D1VbUgyW7AnwPzgdXA26rqG0O2Q+OZv+hzo9ZbvfiYUetJzwZjnPG/rqr2q6oF/fIiYHlV7QUs75clSSOZia6e44Gl/fxS4IQZaIMkNWvo4C/gC0luSHJqv25uVa0B6KdzNrVhklOTrEiyYt26dQM3U5LaMfTonIdU1T1J5gDLktw+6YZVtQRYArBgwQLfCC9JW8igZ/xVdU8/XQtcAhwE3JdkHkA/XTtkGyRJjzdY8CfZKcnOG+aB1wO3ApcBC/uPLQQuHaoNkqQnGrKrZy5wSZINdT5VVZ9Pcj1wYZJTgLuAEwdsgyRpI4MFf1XdCey7ifX3A0cMVVeStHk+uStJjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqzODBn2S7JF9Ocnm/vFuSZUlW9dNdh26DJOkHxjjjPx1YOWV5EbC8qvYClvfLkqSRDBr8SfYAjgHOmrL6eGBpP78UOGHINkiSHm/oM/6PAb8BPDZl3dyqWgPQT+dsasMkpyZZkWTFunXrBm6mJLVj+6F2nORYYG1V3ZDksKe6fVUtAZYALFiwoLZs65795i/63Gi1Vi8+ZrRakp65wYIfOAQ4LskbgR2AFyY5D7gvybyqWpNkHrB2wDZIkjYyWFdPVb2/qvaoqvnAScBVVXUycBmwsP/YQuDSodogSXqimbiPfzFwVJJVwFH9siRpJEN29XxfVV0DXNPP3w8cMUZdSdIT+eSuJDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqzLTBn+TEJDv387+V5OIkBwzfNEnSECY54/9gVX07yaHATwNLgU8M2yxJ0lAmCf7v9dNjgE9U1aXAc4drkiRpSJME/9eS/E/gbcAVSZ434XaSpK3QJAH+NuBK4Oiq+iawG/DrQzZKkjScaYO/qh4G1gKH9qvWA6uGbJQkaTiT3NXzO8BvAu/vV80CzhuyUZKk4UzS1fMm4DjgOwBVdQ+w85CNkiQNZ5Lg/25VFVAASXYatkmSpCFNEvwX9nf17JLk54G/Av5suo2S7JDkuiRfSXJbkg/163dLsizJqn666zM7BEnSU7H95n6ZJMCfA68AHgT2Bn67qpZNsO9HgMOr6qEks4AvJvnfwJuB5VW1OMkiYBHdNQRJ0gg2G/xVVUn+sqoOBCYJ+8dtCzzUL87qfwo4HjisX78UuAaDX5JGM0lXz98ledXT2XmS7ZLcRHc76LKquhaYW1VrAPrpnKezb0nS07PZM/7e64B3J1lNd2dP6E7of2K6Davqe8B+SXYBLkmyz6QNS3IqcCrAnnvuOelmkqRpTBL8b3imRarqm0muAY4G7ksyr6rWJJlH99fAprZZAiwBWLBgQT3TNkiSOpM8uftVYBfgP/Q/u/TrNivJ7P5MnyQ7AkcCtwOXAQv7jy0ELn06DZckPT2TPLl7OnA+XV/8HOC8JKdNsO95wNVJbgaup+vjvxxYDByVZBVwVL8sSRrJJF09pwCvrqrvACT5MPAl4OOb26iqbgb238T6+4EjnnpTJUlbwiR39YQfjMlPP59hmiNJGtokZ/znANcmuaRfPgE4e7AWSZIGNW3wV9VH+ztyDqU70//Zqvry0A2TJA1j2uBPcjBwW1Xd2C/vnOTV/cNYkqRtzCR9/J/gB0MvQPcQly9bl6Rt1EQXd/txdwCoqseY7NqAJGkrNEnw35nkfUlm9T+nA3cO3TBJ0jAmCf53Az8JfA24G3g1/Rg6kqRtzyR39awFThqhLZKkEUwyZMMfJnlh382zPMnXk5w8RuMkSVveJF09r6+qB4Fj6bp6fhT49UFbJUkazCTBP6ufvhG4oKoeGLA9kqSBTXJb5meT3A78C/BLSWYD/zpssyRJQ5lkPP5FwGuABVX1KPAw3XtzJUnboIkexKqqb0yZ/w7d07uSpG3QJH38kqRnkScN/iSH9NPnjdccSdLQNnfGf2Y//dIYDZEkjWNzffyPJjkHeEmSMzf+ZVW9b7hmSZKGsrngPxY4EjgcuGGc5kiShvakwV9VXwc+nWRlVX1lxDZJkgY0yV099ye5JMnaJPcluSjJHoO3TJI0iEmC/xzgMuDFwEuAz/brJEnboEmCf05VnVNV6/ufc4HZA7dLkjSQSYJ/XZKTk2zX/5wM3D90wyRJw5gk+N8FvA24F1gDvLVfJ0naBk3yBq67gONGaIskaQSO1SNJjTH4JakxBr8kNWbi4E9ycJKrkvxtkhMGbJMkaUBPenE3yb+pqnunrPoVuou8Af4v8JfDNk2SNITNnfH/aZIPJtmhX/4m8B+BtwMPTrfjJC9NcnWSlUluS3J6v363JMuSrOqnuz7Tg5AkTe5Jg7+qTgBuAi5P8k7gDOAx4PnACRPsez3wq1X1SuBg4D1JfgxYBCyvqr2A5f2yJGkkm+3jr6rPAj8N7AJcDNxRVWdW1brpdlxVa6rqxn7+28BKurF+jgeW9h9bymRfIpKkLWRzr148LskXgauAW4GTgDcluSDJy59KkSTzgf2Ba4G5VbUGui8HYM6TbHNqkhVJVqxbN+33jCRpQpt7cve/AK8BdgSuqKqDgF9JshfwB3RfBNNK8gLgIuCMqnowyUQNq6olwBKABQsW1EQbSZKmtbng/xZduO8IrN2wsqpWMXnoz6IL/fOr6uJ+9X1J5lXVmiTzpu5bkjS8zfXxv4nuQu56urt5npJ0p/ZnAyur6qNTfnUZsLCfXwhc+lT3LUl6+qZ79eLHn8G+DwHeCdyS5KZ+3QeAxcCFSU4B7gJOfAY1JElP0bSjcz5dVfVFuoe9NuWIoepKkjbPsXokqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjRks+JN8MsnaJLdOWbdbkmVJVvXTXYeqL0natCHP+M8Fjt5o3SJgeVXtBSzvlyVJIxos+Kvqb4AHNlp9PLC0n18KnDBUfUnSpo3dxz+3qtYA9NM5T/bBJKcmWZFkxbp160ZroCQ92221F3eraklVLaiqBbNnz57p5kjSs8bYwX9fknkA/XTtyPUlqXljB/9lwMJ+fiFw6cj1Jal5Q97OeQHwJWDvJHcnOQVYDByVZBVwVL8sSRrR9kPtuKre8SS/OmKompKk6W21F3clScMw+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjBruPXxrb/EWfG7Xe6sXHjFpP2lI845ekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5Ia4zt3B+Q7YCVtjTzjl6TGGPyS1BiDX5IaY/BLUmNmJPiTHJ3kjiT/mGTRTLRBklo1+l09SbYD/gQ4CrgbuD7JZVX192O3RdpSvINL25KZOOM/CPjHqrqzqr4LfBo4fgbaIUlNSlWNWzB5K3B0Vf1cv/xO4NVV9d6NPncqcGq/uDdwx6gNhd2Br49cc6Zrt3jMrdZu8ZhbrP3DVTV745Uz8QBXNrHuCd8+VbUEWDJ8czYtyYqqWtBS7RaPudXaLR5zy7U3NhNdPXcDL52yvAdwzwy0Q5KaNBPBfz2wV5KXJXkucBJw2Qy0Q5KaNHpXT1WtT/Je4EpgO+CTVXXb2O2YwIx1M81g7RaPudXaLR5zy7UfZ/SLu5KkmeWTu5LUGINfkhpj8G8kySeTrE1y68h1X5rk6iQrk9yW5PQRa++Q5LokX+lrf2is2n397ZJ8OcnlY9bta69OckuSm5KsGLHuLkk+k+T2/t/5a0aqu3d/rBt+Hkxyxhi1+/q/3P83dmuSC5LsMFLd0/uatw19vJvKkCS7JVmWZFU/3XXINkzH4H+ic4GjZ6DueuBXq+qVwMHAe5L82Ei1HwEOr6p9gf2Ao5McPFJtgNOBlSPW29jrqmq/ke+x/mPg81X1CmBfRjr+qrqjP9b9gAOBh4FLxqid5CXA+4AFVbUP3c0dJ41Qdx/g5+lGDdgXODbJXgOWPJcnZsgiYHlV7QUs75dnjMG/kar6G+CBGai7pqpu7Oe/TRcELxmpdlXVQ/3irP5nlKv+SfYAjgHOGqPe1iDJC4HXAmcDVNV3q+qbM9CUI4B/qqqvjlhze2DHJNsDz2ecZ3heCfxdVT1cVeuBvwbeNFSxJ8mQ44Gl/fxS4ISh6k/C4N8KJZkP7A9cO2LN7ZLcBKwFllXVWLU/BvwG8NhI9TZWwBeS3NAPEzKGHwHWAef0XVxnJdlppNpTnQRcMFaxqvoa8N+Au4A1wLeq6gsjlL4VeG2SFyV5PvBGHv8Q6RjmVtUa6E7ygDkj138cg38rk+QFwEXAGVX14Fh1q+p7/Z//ewAH9X8eDyrJscDaqrph6FqbcUhVHQC8ga577bUj1NweOAD4RFXtD3yHkf/07x+ePA74ixFr7kp35vsy4MXATklOHrpuVa0EPgwsAz4PfIWua7VZBv9WJMksutA/v6ounok29F0O1zDOdY5DgOOSrKYbpfXwJOeNUPf7quqefrqWrq/7oBHK3g3cPeWvqs/QfRGM6Q3AjVV134g1jwT+uarWVdWjwMXAT45RuKrOrqoDquq1dN0wq8aoO8V9SeYB9NO1I9d/HIN/K5EkdH2+K6vqoyPXnp1kl35+R7r/QW8fum5Vvb+q9qiq+XTdDldV1eBngBsk2SnJzhvmgdfTdQsMqqruBf5fkr37VUcAY7+P4h2M2M3Tuws4OMnz+//ej2Cki9pJ5vTTPYE3M/6xXwYs7OcXApeOXP9xZmJ0zq1akguAw4Ddk9wN/E5VnT1C6UOAdwK39H3tAB+oqitGqD0PWNq/JOc5wIVVNfqtlTNgLnBJl0FsD3yqqj4/Uu3TgPP7Lpc7gZ8dqS59P/dRwC+MVROgqq5N8hngRrquli8z3jAGFyV5EfAo8J6q+sZQhTaVIcBi4MIkp9B9AZ44VP1JOGSDJDXGrh5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JpxSSrJH01Z/rUkv7uF9n1ukrduiX1NU+fEfpTNq4euJT1TBr+2Bo8Ab06y+0w3ZKr+uYZJnQL8UlW9bqj2SFuKwa+twXq6B3l+eeNfbHzGnuShfnpYkr9OcmGSf0iyOMl/6t8rcEuSl0/ZzZFJ/k//uWP77bdL8pEk1ye5OckvTNnv1Uk+Bdyyifa8o9//rUk+3K/7beBQ4E+TfGSjzz8nyf/ox4G/PMkVG44n3bsAdu/nFyS5pp/fqR/T/fp+ELfj+/U/3h/fTX2b9+o/+7l071K4Ncnb+88e2P/zuSHJlVOGC3hfkr/vt//00/h3pWcBn9zV1uJPgJuT/OFT2GZfuiF3H6B7+vWsqjoo3UtsTgPO6D83H/gp4OXA1Un+LfAzdKNDvirJ84C/TbJhpMiDgH2q6p+nFkvyYrrBvg4EvkE3qucJVfV7SQ4Hfq2qNn6Zy5v7+v+ObkTGlcAnpzmu/0w3fMW7+qE0rkvyV8C7gT+uqg1P/G5HN9LkPVV1TN/GH+rHfPo4cHxVreu/DP4AeBfdYHAvq6pHNgzTofZ4xq+tQj8S6f+ie1HHpK7v32PwCPBPwIbgvoUubDe4sKoeq6pVdF8Qr6Abl+dn+uExrgVeBGx4Ocd1G4d+71XANf0gY+uB8+nG1d+cQ4G/6OvfC0xyDeD1wKK+bdcAOwB7Al8CPpDkN4Efrqp/6Y/1yCQfTvLvq+pbwN7APsCyfh+/RTfqKsDNdENFnEzjI1S2zDN+bU0+RjeOyzlT1q2nP0HpB/Z67pTfPTJl/rEpy4/x+P+2Nx6XpIAAp1XVlVN/keQwumGSNyXTtP+pbvP9Y6ML96nbvKWq7tjo8yuTXEv34pork/xcVV2V5EC6M///2v/VcglwW1Vt6nWOx9B9WR0HfDDJj/dfYmqIZ/zaalTVA8CFdBdKN1hN17UC3Vjus57Grk/s+9pfTvcSlDuAK4Ff7LtFSPKjmf5lKNcCP5Vk9/7C7zvo3ua0OV8E3tLXn0s3eNcGq/nBsb1lyvorgdP6LzqS7N9PfwS4s6rOpBvt8Sf67qeHq+o8upecHNAf3+z07/FNMqu/PvAc4KVVdTXdy292AV4wTfv1LOQZv7Y2fwS8d8rynwGXJrmO7l2lT3Y2vjl30AX0XODdVfWvSc6i6w66sQ/YdUzzOryqWpPk/XTdNQGuqKrphte9iG744VuBf6D78vhW/7sPAWcn+QCPf9va79P99XNz37bVwLHA24GTkzwK3Av8Hl3300eSPEY38uQvVtV3+wvIZyb5Ibr/zz/W1z+vXxfgv8/QKx81wxydUxpYkhdU1UPphgW+ju6tX/fOdLvULs/4peFd3t9B81zg9w19zTTP+CWpMV7claTGGPyS1BiDX5IaY/BLUmMMfklqzP8HFQXAQ5UGh+0AAAAASUVORK5CYII=\n",
"text/plain": [
"
"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"%time report_minimizing_tree(neg_entropy, inconsistent=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Mission accomplished!** With inconsistent guesses allowed, all three metrics solve every target word in 6 guesses or less. \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Best and Worst First Guesses\n",
"\n",
"Below we create a table of the best and worst first guesses (that is, the guesses that score the highest and lowest according to each of the three metrics):"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [],
"source": [
"import pandas as pd\n",
"\n",
"def first_guesses(targets) -> pd.DataFrame: \n",
" \"\"\"A data frame of words and scores on the 3 metrics, sorted best to worst on each metric.\"\"\"\n",
" metrics = (max, expectation, neg_entropy)\n",
" data = [sorted((metric(partition_counts(g, targets)), g) for g in wordlist)\n",
" for metric in metrics]\n",
" def reformat(row):\n",
" (val1, word1), (val2, word2), (val3, word3) = row\n",
" return [word1, val1, word2, round(val2, 2), word3, round(val3, 3)]\n",
" return pd.DataFrame(map(reformat, zip(*data)), \n",
" columns='max_word max_score exp_word exp_score ent_word ent_score'.split())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The best and worst first guesses for Wordle:"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"
\n",
"\n",
"
\n",
" \n",
"
\n",
"
\n",
"
max_word
\n",
"
max_score
\n",
"
exp_word
\n",
"
exp_score
\n",
"
ent_word
\n",
"
ent_score
\n",
"
\n",
" \n",
" \n",
"
\n",
"
0
\n",
"
ARISE
\n",
"
167
\n",
"
RAISE
\n",
"
60.74
\n",
"
RAISE
\n",
"
-5.878
\n",
"
\n",
"
\n",
"
1
\n",
"
RAISE
\n",
"
167
\n",
"
ARISE
\n",
"
63.47
\n",
"
SLATE
\n",
"
-5.856
\n",
"
\n",
"
\n",
"
2
\n",
"
ALONE
\n",
"
182
\n",
"
IRATE
\n",
"
63.49
\n",
"
CRATE
\n",
"
-5.835
\n",
"
\n",
"
\n",
"
3
\n",
"
AROSE
\n",
"
182
\n",
"
AROSE
\n",
"
65.76
\n",
"
IRATE
\n",
"
-5.833
\n",
"
\n",
"
\n",
"
4
\n",
"
RATIO
\n",
"
190
\n",
"
ALTER
\n",
"
69.83
\n",
"
TRACE
\n",
"
-5.830
\n",
"
\n",
"
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
\n",
"
\n",
"
2304
\n",
"
CIVIC
\n",
"
1247
\n",
"
PUPPY
\n",
"
775.34
\n",
"
FIZZY
\n",
"
-2.506
\n",
"
\n",
"
\n",
"
2305
\n",
"
PUPPY
\n",
"
1283
\n",
"
MAMMA
\n",
"
776.30
\n",
"
MUMMY
\n",
"
-2.480
\n",
"
\n",
"
\n",
"
2306
\n",
"
MUMMY
\n",
"
1321
\n",
"
VIVID
\n",
"
812.76
\n",
"
MAMMA
\n",
"
-2.398
\n",
"
\n",
"
\n",
"
2307
\n",
"
VIVID
\n",
"
1324
\n",
"
MUMMY
\n",
"
817.96
\n",
"
JAZZY
\n",
"
-2.309
\n",
"
\n",
"
\n",
"
2308
\n",
"
FUZZY
\n",
"
1349
\n",
"
FUZZY
\n",
"
854.18
\n",
"
FUZZY
\n",
"
-2.304
\n",
"
\n",
" \n",
"
\n",
"
2309 rows × 6 columns
\n",
"
"
],
"text/plain": [
" max_word max_score exp_word exp_score ent_word ent_score\n",
"0 ARISE 167 RAISE 60.74 RAISE -5.878\n",
"1 RAISE 167 ARISE 63.47 SLATE -5.856\n",
"2 ALONE 182 IRATE 63.49 CRATE -5.835\n",
"3 AROSE 182 AROSE 65.76 IRATE -5.833\n",
"4 RATIO 190 ALTER 69.83 TRACE -5.830\n",
"... ... ... ... ... ... ...\n",
"2304 CIVIC 1247 PUPPY 775.34 FIZZY -2.506\n",
"2305 PUPPY 1283 MAMMA 776.30 MUMMY -2.480\n",
"2306 MUMMY 1321 VIVID 812.76 MAMMA -2.398\n",
"2307 VIVID 1324 MUMMY 817.96 JAZZY -2.309\n",
"2308 FUZZY 1349 FUZZY 854.18 FUZZY -2.304\n",
"\n",
"[2309 rows x 6 columns]"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"df = first_guesses(wordlist)\n",
"df"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The top guesses are `\"RAISE\"` and its anagram `\"ARISE\"`. The letters `'A'`, `'R'`, and `'E'` are the most common in the top guesses. The three metrics agree that `'FUZZY'` is the worst first guess.\n",
"\n",
"Here are the top 20 words for each metric:"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"
\n",
"\n",
"
\n",
" \n",
"
\n",
"
\n",
"
max_word
\n",
"
max_score
\n",
"
exp_word
\n",
"
exp_score
\n",
"
ent_word
\n",
"
ent_score
\n",
"
\n",
" \n",
" \n",
"
\n",
"
0
\n",
"
ARISE
\n",
"
167
\n",
"
RAISE
\n",
"
60.74
\n",
"
RAISE
\n",
"
-5.878
\n",
"
\n",
"
\n",
"
1
\n",
"
RAISE
\n",
"
167
\n",
"
ARISE
\n",
"
63.47
\n",
"
SLATE
\n",
"
-5.856
\n",
"
\n",
"
\n",
"
2
\n",
"
ALONE
\n",
"
182
\n",
"
IRATE
\n",
"
63.49
\n",
"
CRATE
\n",
"
-5.835
\n",
"
\n",
"
\n",
"
3
\n",
"
AROSE
\n",
"
182
\n",
"
AROSE
\n",
"
65.76
\n",
"
IRATE
\n",
"
-5.833
\n",
"
\n",
"
\n",
"
4
\n",
"
RATIO
\n",
"
190
\n",
"
ALTER
\n",
"
69.83
\n",
"
TRACE
\n",
"
-5.830
\n",
"
\n",
"
\n",
"
5
\n",
"
ATONE
\n",
"
191
\n",
"
SANER
\n",
"
70.02
\n",
"
ARISE
\n",
"
-5.821
\n",
"
\n",
"
\n",
"
6
\n",
"
IRATE
\n",
"
193
\n",
"
LATER
\n",
"
70.03
\n",
"
STARE
\n",
"
-5.807
\n",
"
\n",
"
\n",
"
7
\n",
"
AISLE
\n",
"
196
\n",
"
SNARE
\n",
"
71.02
\n",
"
SNARE
\n",
"
-5.769
\n",
"
\n",
"
\n",
"
8
\n",
"
ALERT
\n",
"
196
\n",
"
STARE
\n",
"
71.05
\n",
"
AROSE
\n",
"
-5.768
\n",
"
\n",
"
\n",
"
9
\n",
"
ALTER
\n",
"
196
\n",
"
SLATE
\n",
"
71.28
\n",
"
LEAST
\n",
"
-5.752
\n",
"
\n",
"
\n",
"
10
\n",
"
LATER
\n",
"
196
\n",
"
ALERT
\n",
"
71.51
\n",
"
ALERT
\n",
"
-5.744
\n",
"
\n",
"
\n",
"
11
\n",
"
TEARY
\n",
"
198
\n",
"
CRATE
\n",
"
72.81
\n",
"
CRANE
\n",
"
-5.741
\n",
"
\n",
"
\n",
"
12
\n",
"
LEANT
\n",
"
207
\n",
"
TRACE
\n",
"
73.95
\n",
"
STALE
\n",
"
-5.738
\n",
"
\n",
"
\n",
"
13
\n",
"
LEARN
\n",
"
212
\n",
"
STALE
\n",
"
75.33
\n",
"
SANER
\n",
"
-5.734
\n",
"
\n",
"
\n",
"
14
\n",
"
RENAL
\n",
"
212
\n",
"
AISLE
\n",
"
76.09
\n",
"
ALTER
\n",
"
-5.713
\n",
"
\n",
"
\n",
"
15
\n",
"
EARLY
\n",
"
215
\n",
"
LEARN
\n",
"
76.72
\n",
"
LATER
\n",
"
-5.707
\n",
"
\n",
"
\n",
"
16
\n",
"
LAYER
\n",
"
215
\n",
"
LEANT
\n",
"
77.09
\n",
"
REACT
\n",
"
-5.697
\n",
"
\n",
"
\n",
"
17
\n",
"
LOSER
\n",
"
215
\n",
"
ALONE
\n",
"
77.16
\n",
"
TRADE
\n",
"
-5.684
\n",
"
\n",
"
\n",
"
18
\n",
"
RELAY
\n",
"
215
\n",
"
LEAST
\n",
"
77.97
\n",
"
LEANT
\n",
"
-5.684
\n",
"
\n",
"
\n",
"
19
\n",
"
CANOE
\n",
"
216
\n",
"
CRANE
\n",
"
78.69
\n",
"
LEARN
\n",
"
-5.652
\n",
"
\n",
" \n",
"
\n",
"
"
],
"text/plain": [
" max_word max_score exp_word exp_score ent_word ent_score\n",
"0 ARISE 167 RAISE 60.74 RAISE -5.878\n",
"1 RAISE 167 ARISE 63.47 SLATE -5.856\n",
"2 ALONE 182 IRATE 63.49 CRATE -5.835\n",
"3 AROSE 182 AROSE 65.76 IRATE -5.833\n",
"4 RATIO 190 ALTER 69.83 TRACE -5.830\n",
"5 ATONE 191 SANER 70.02 ARISE -5.821\n",
"6 IRATE 193 LATER 70.03 STARE -5.807\n",
"7 AISLE 196 SNARE 71.02 SNARE -5.769\n",
"8 ALERT 196 STARE 71.05 AROSE -5.768\n",
"9 ALTER 196 SLATE 71.28 LEAST -5.752\n",
"10 LATER 196 ALERT 71.51 ALERT -5.744\n",
"11 TEARY 198 CRATE 72.81 CRANE -5.741\n",
"12 LEANT 207 TRACE 73.95 STALE -5.738\n",
"13 LEARN 212 STALE 75.33 SANER -5.734\n",
"14 RENAL 212 AISLE 76.09 ALTER -5.713\n",
"15 EARLY 215 LEARN 76.72 LATER -5.707\n",
"16 LAYER 215 LEANT 77.09 REACT -5.697\n",
"17 LOSER 215 ALONE 77.16 TRADE -5.684\n",
"18 RELAY 215 LEAST 77.97 LEANT -5.684\n",
"19 CANOE 216 CRANE 78.69 LEARN -5.652"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"df[:20]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see below that partitioning with the guess`'RAISE'` will leave us with no more than 167 words in any branch, while `'FUZZY'` is likely to leave us with a branch of 1349 words, and about 80% of the time will leave us with a branch of 228 words or more."
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({1: 28,\n",
" 2: 13,\n",
" 3: 5,\n",
" 4: 10,\n",
" 5: 8,\n",
" 6: 4,\n",
" 7: 3,\n",
" 8: 4,\n",
" 9: 4,\n",
" 10: 2,\n",
" 12: 3,\n",
" 13: 2,\n",
" 14: 1,\n",
" 15: 2,\n",
" 17: 3,\n",
" 18: 2,\n",
" 19: 1,\n",
" 20: 4,\n",
" 21: 2,\n",
" 22: 1,\n",
" 23: 2,\n",
" 24: 1,\n",
" 25: 1,\n",
" 26: 4,\n",
" 28: 2,\n",
" 29: 1,\n",
" 34: 2,\n",
" 35: 1,\n",
" 40: 1,\n",
" 41: 2,\n",
" 43: 1,\n",
" 51: 1,\n",
" 61: 1,\n",
" 69: 1,\n",
" 77: 1,\n",
" 80: 1,\n",
" 91: 2,\n",
" 102: 1,\n",
" 103: 1,\n",
" 107: 1,\n",
" 120: 1,\n",
" 167: 1})"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Counter(partition_counts('RAISE', wordlist))"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Counter({1: 12,\n",
" 2: 2,\n",
" 3: 1,\n",
" 4: 2,\n",
" 5: 2,\n",
" 6: 1,\n",
" 7: 1,\n",
" 8: 1,\n",
" 10: 2,\n",
" 16: 1,\n",
" 20: 1,\n",
" 45: 1,\n",
" 51: 2,\n",
" 84: 1,\n",
" 122: 1,\n",
" 228: 1,\n",
" 265: 1,\n",
" 1349: 1})"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Counter(partition_counts('FUZZY', wordlist))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Evil Wordle\n",
"\n",
"The [**Evil Wordle**](https://swag.github.io/evil-wordle/) variant says it works like this: *\"There's no [target] word set by default. Every time you guess, I look at all possible 5-letter words that would fit all your guesses, and choose the match pattern [reply] that results in the most possible words. My goal is to maximize the amount of guesses it takes to find the word.\"*\n",
"\n",
"To play against Evil Wordle, minimizing the max branch size is a good strategy. We know the guess tree that minimizes max has a few branches that require 6 guesses. If the Evil Replier did look-ahead, perhaps they could get to one of those branches. But we know that the Evil Replier greedily picks the branch with the \"most possible words.\" So I will define `evil` to follow branches through a guess tree and produce the (guess, reply) pairs along the way. For a given tree, there is only one possible game (assuming the Evil Replier breaks ties the same way each time)."
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [],
"source": [
"def evil(tree) -> List[Tuple[Word, Reply]]:\n",
" \"\"\"Given a guess tree, determine what happens when the Evil Replier always picks a maximum-sized branch.\n",
" The result is a list of (guess, reply) tuples.\"\"\"\n",
" if isinstance(tree, Word):\n",
" return [(tree, Correct)]\n",
" else:\n",
" def size(reply): \n",
" branch = tree.branches[reply]\n",
" return 0 if reply == Correct else 1 if isinstance(branch, Word) else branch.size\n",
" reply = max(tree.branches, key=size)\n",
" return [(tree.guess, reply)] + evil(tree.branches[reply])"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[('ARISE', '.....'),\n",
" ('BLOND', '.....'),\n",
" ('DUMPY', '.YYY.'),\n",
" ('CHUMP', '.GGGG'),\n",
" ('THUMP', 'GGGGG')]"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"evil(minimizing_tree(max, wordlist, inconsistent=True))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that the one possible game consists of 5 guesses. That raises two questions:\n",
"- Would it be possible for a smarter Guesser to create a different tree (perhaps minimizing something other than max) that only requires 4 guesses? **No.** I know that because (a) when there are two words left in a branch, it will always take two guesses to defeat the Evil Replier, and (b) I previously tried all two-word guess pairs to see which resulted in the smallest branches, and every pair had branches with multiple words.\n",
"- Would it be possible for a smarter Evil Replier to force a game with 6 guesses? **Maybe.** We know the minimizing-max guess tree has 11 out of 2,309 leaves that require 6 guesses. If the Evil Replier did look-ahead instead of acting greedily, could it get to one of those? I think it is unlikely, but I would need to do a minimax search to prove it one way or the other.\n",
"\n",
"Alas, this is all moot, because a little experimenting shows that [**Evil Wordle**](https://swag.github.io/evil-wordle/) is using a word list that contains multiple words that are not in the 2,309 word list. I suspect it is using Wordle's 12,971–word list."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Antiwordle\n",
"\n",
"The Wordle variant [**Antiwordle**](https://www.antiwordle.com/) invites you to *\"Avoid guessing the hidden word in as many tries as possible. Sounds easy, but there's a catch!*\" The catch is that only consistent guesses are allowed. We can solve Antiwordle by minimizing the entropy (not negative entropy!) of branch sizes. That is, we want big branches."
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"minimizing the entropy of partition sizes over 2,309 targets; inconsistent guesses prohibited\n",
"first guess: \"FUZZY\"\n",
"median: 6 guesses, mean: 5.75 ± 1.61, worst: 11, best: 1\n",
"cumulative: ≤2:1%, ≤3:8%, ≤4:23%, ≤5:44%, ≤6:68%, ≤7:87%, ≤8:96%, ≤9:99%, ≤10:99.7%\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAUoklEQVR4nO3de/RddXnn8fdHwBvQghIY5NJYhqLWKbeIWByLl7FoGC4qFmZAVqVFW0BobaeRaaut0zWx1ktxdeig3GaBOFRgQGGJFKGOXRYIiBAaKS2NDBBIKCoIFY0888feaX/8yOUQsvdJ8n2/1jrrnLPP5Xl2Lp+zz/fs/d2pKiRJ7XjOtBuQJI3L4Jekxhj8ktQYg1+SGmPwS1Jjtpx2A5PYYYcdau7cudNuQ5I2KTfffPNDVTVn9vJNIvjnzp3LokWLpt2GJG1Sknx7dcsHG+pJsluS65IsSXJHklP75R9Kcl+SW/vLW4fqQZL0dENu8a8E3l9VtyTZFrg5yTX9Y5+oqj8ZsLYkaQ0GC/6qWgYs628/mmQJsMtQ9SRJkxllr54kc4F9gRv6RScnuS3JOUm2X8NrTkyyKMmiFStWjNGmJDVh8OBPsg1wCXBaVT0CnAnsAexD943gY6t7XVWdVVXzqmrenDlP+1FakrSeBg3+JFvRhf6FVXUpQFU9WFU/rqongU8DBwzZgyTpqYbcqyfA2cCSqvr4jOU7z3jakcDioXqQJD3dkHv1HAQcB9ye5NZ+2enAMUn2AQpYCrxnwB4kSbMMuVfP14Cs5qGrhqopSVq3TeLIXWljN3fBlaPWW7pw/qj1tHlxkjZJaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktSYLafdgLShzF1w5aj1li6cP2o9aUNxi1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhozWPAn2S3JdUmWJLkjyan98hcluSbJXf319kP1IEl6uiG3+FcC76+qlwMHAicleQWwALi2qvYEru3vS5JGMljwV9Wyqrqlv/0osATYBTgcOL9/2vnAEUP1IEl6ulHG+JPMBfYFbgB2qqpl0H04ADuO0YMkqTN48CfZBrgEOK2qHnkGrzsxyaIki1asWDFcg5LUmEGDP8lWdKF/YVVd2i9+MMnO/eM7A8tX99qqOquq5lXVvDlz5gzZpiQ1Zci9egKcDSypqo/PeOgK4Pj+9vHA5UP1IEl6uiFPxHIQcBxwe5Jb+2WnAwuBi5OcANwDHDVgD5KkWQYL/qr6GpA1PPzGoepKktbOI3clqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWrMkAdwSRrB3AVXjlZr6cL5o9XScNzil6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjVln8Cc5Ksm2/e3fTXJpkv2Gb02SNIRJtvh/r6oeTfJa4BeB84Ezh21LkjSUSYL/x/31fODMqroceO5wLUmShjRJ8N+X5H8C7wSuSvK8CV8nSdoITRLg7wSuBg6pqu8CLwJ+e10vSnJOkuVJFs9Y9qEk9yW5tb+8dX0blyStn3UGf1U9DiwHXtsvWgncNcF7nwccsprln6iqffrLVZM2KknaMCbZq+eDwO8AH+gXbQVcsK7XVdVXgYefVXeSpA1uywmecySwL3ALQFXdv2r3zvV0cpJ3AYuA91fVd1b3pCQnAicC7L777s+inMY0d8GVo9ZbunD+qPWkzcEkY/w/rKoCCiDJ1s+i3pnAHsA+wDLgY2t6YlWdVVXzqmrenDlznkVJSdJMkwT/xf1ePdsl+VXgL4FPr0+xqnqwqn5cVU/273HA+ryPJGn9rXWoJ0mA/w28DHgE2Av4/aq6Zn2KJdm5qpb1d48EFq/t+ZKkDW+twV9VleT/VNX+wDMK+yQXAQcDOyS5F/ggcHCSfeiGjZYC71mPniVJz8IkP+7+TZJXVdVNz+SNq+qY1Sw++5m8hyRpw5sk+F8PvDfJUuAxIHRfBn5uyMYkScOYJPjfMngXkqTRTHLk7reB7YD/2F+265dJkjZBkxy5eypwIbBjf7kgySlDNyZJGsYkQz0nAK+uqscAknwE+DrwqSEbkyQNY5IDuMK/zslPfzvDtCNJGtokW/znAjckuay/fwTulilJm6x1Bn9VfTzJ9XTTMgf45ar6xtCNSZKGsc7gT3IgcEdV3dLf3zbJq6vqhsG7kyRtcJOM8Z8JfH/G/cfwZOuStMma6MfdflpmAPqZNSf5bUCStBGaJPjvTvK+JFv1l1OBu4duTJI0jEmC/73AzwP3AfcCr6Y/M5YkadMzyV49y4GjR+hFkjSCSaZs+OMkP9EP81yb5KEkx47RnCRpw5tkqOfNVfUIcCjdUM/PAL89aFeSpMFMEvxb9ddvBS6qqocH7EeSNLBJdsv8QpJvAf8M/HqSOcAPhm1LkjSUSebjXwC8BphXVT8CHgcOH7oxSdIwJjoQq6q+M+P2Y3RH70qSNkGTjPFLkjYjawz+JAf1188brx1J0tDWtsV/Rn/99TEakSSNY21j/D9Kci6wS5IzZj9YVe8bri1J0lDWFvyHAm8C3gDcPE47kqShrTH4q+oh4HNJllTVN0fsSZI0oEn26vmnJJclWZ7kwSSXJNl18M4kSYOYJPjPBa4AXgLsAnyhXyZJ2gRNEvw7VtW5VbWyv5wHzBm4L0nSQCYJ/hVJjk2yRX85FvinoRuTJA1jkuB/N/BO4AFgGfCOfpkkaRM0yRm47gEOG6EXSdIInKtHkhpj8EtSYwYL/iTn9Pv+L56x7EVJrklyV3+9/VD1JUmrN3HwJzkwyVeS/HWSIyZ4yXnAIbOWLQCurao9gWv7+5KkEa1tWuZ/M2vRb9L9yHsI8OF1vXFVfRWYfX7ew4Hz+9vnA0dM2qgkacNY2149f57kZuCjVfUD4LvAfwKeBB5Zz3o7VdUygKpalmTHNT0xyYnAiQC77777epaTJM22xi3+qjoCuBX4YpLjgNPoQv+FjLClXlVnVdW8qpo3Z44HCkvShrLWMf6q+gLwi8B2wKXAnVV1RlWtWM96DybZGaC/Xr6e7yNJWk9rG+M/LMnXgK8Ai4GjgSOTXJRkj/WsdwVwfH/7eODy9XwfSdJ6WtsY/38DXgO8ALiqqg4AfjPJnsAf0X0QrFGSi4CDgR2S3At8EFgIXJzkBOAe4KhnvQaSpGdkbcH/PbpwfwEzhmSq6i7WEfr9845Zw0NvfCYNSpI2rLWN8R9J90PuSrq9eSRJm4F1nXrxUyP2IkkagXP1SFJjDH5JaozBL0mNWeeJWCRpdeYuuHLUeksXzh+13ubMLX5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1BiDX5IaY/BLUmMMfklqjMEvSY0x+CWpMQa/JDXG4Jekxmw57QY0jLkLrhyt1tKF80erJenZc4tfkhpj8EtSYwx+SWqMwS9JjTH4JakxU9mrJ8lS4FHgx8DKqpo3jT4kqUXT3J3z9VX10BTrS1KTHOqRpMZMK/gL+HKSm5OcuLonJDkxyaIki1asWDFye5K0+ZpW8B9UVfsBbwFOSvK62U+oqrOqal5VzZszZ874HUrSZmoqwV9V9/fXy4HLgAOm0YcktWj04E+ydZJtV90G3gwsHrsPSWrVNPbq2Qm4LMmq+p+tqi9NoQ9JatLowV9VdwN7j11XktRxd05JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhpj8EtSYwx+SWqMwS9JjTH4Jakx0zz1oiStl7kLrhy13tKF80etNzS3+CWpMQa/JDXG4Jekxhj8ktQYg1+SGmPwS1JjDH5JaozBL0mNMfglqTEGvyQ1xuCXpMYY/JLUGINfkhrj7JwDcgZBafOzOfy/dotfkhpj8EtSYwx+SWqMwS9JjTH4JakxBr8kNcbgl6TGGPyS1JipBH+SQ5LcmeTvkyyYRg+S1KrRgz/JFsCfAW8BXgEck+QVY/chSa2axpQNBwB/X1V3AyT5HHA48LdDFNscDq+WpA0pVTVuweQdwCFV9Sv9/eOAV1fVybOedyJwYn93L+DOURuFHYCHRq457dotrnOrtVtc5xZr/1RVzZm9cBpb/FnNsqd9+lTVWcBZw7ezekkWVdW8lmq3uM6t1m5xnVuuPds0fty9F9htxv1dgfun0IckNWkawX8TsGeSlyZ5LnA0cMUU+pCkJo0+1FNVK5OcDFwNbAGcU1V3jN3HBKY2zDTF2i2uc6u1W1znlms/xeg/7kqSpssjdyWpMQa/JDXG4J8lyTlJlidZPHLd3ZJcl2RJkjuSnDpi7ecnuTHJN/vafzBW7b7+Fkm+keSLY9btay9NcnuSW5MsGrHudkk+n+Rb/d/5a0aqu1e/rqsujyQ5bYzaff3f6P+NLU5yUZLnj1T31L7mHUOv7+oyJMmLklyT5K7+evshe1gXg//pzgMOmULdlcD7q+rlwIHASSNOZfEE8Iaq2hvYBzgkyYEj1QY4FVgyYr3ZXl9V+4y8j/WfAl+qqpcBezPS+lfVnf267gPsDzwOXDZG7SS7AO8D5lXVK+l27jh6hLqvBH6VbtaAvYFDk+w5YMnzeHqGLACurao9gWv7+1Nj8M9SVV8FHp5C3WVVdUt/+1G6INhlpNpVVd/v727VX0b51T/JrsB84DNj1NsYJPkJ4HXA2QBV9cOq+u4UWnkj8A9V9e0Ra24JvCDJlsALGecYnpcDf1NVj1fVSuCvgCOHKraGDDkcOL+/fT5wxFD1J2Hwb4SSzAX2BW4YseYWSW4FlgPXVNVYtT8J/BfgyZHqzVbAl5Pc3E8TMoafBlYA5/ZDXJ9JsvVItWc6GrhorGJVdR/wJ8A9wDLge1X15RFKLwZel+TFSV4IvJWnHkQ6hp2qahl0G3nAjiPXfwqDfyOTZBvgEuC0qnpkrLpV9eP+6/+uwAH91+NBJTkUWF5VNw9day0Oqqr96GaLPSnJ60aouSWwH3BmVe0LPMbIX/37gycPA/5ixJrb0235vhR4CbB1kmOHrltVS4CPANcAXwK+STe02iyDfyOSZCu60L+wqi6dRg/9kMP1jPM7x0HAYUmWAp8D3pDkghHq/ouqur+/Xk431n3ACGXvBe6d8a3q83QfBGN6C3BLVT04Ys03Af9YVSuq6kfApcDPj1G4qs6uqv2q6nV0wzB3jVF3hgeT7AzQXy8fuf5TGPwbiSShG/NdUlUfH7n2nCTb9bdfQPcf9FtD162qD1TVrlU1l27Y4StVNfgW4CpJtk6y7arbwJvphgUGVVUPAP8vyV79ojcy0LTka3EMIw7z9O4BDkzywv7f+xsZ6UftJDv217sDb2P8db8COL6/fTxw+cj1n2Ias3Nu1JJcBBwM7JDkXuCDVXX2CKUPAo4Dbu/H2gFOr6qrRqi9M3B+f5Kc5wAXV9Xou1ZOwU7AZV0GsSXw2ar60ki1TwEu7Idc7gZ+eaS69OPc/wF4z1g1AarqhiSfB26hG2r5BuNNY3BJkhcDPwJOqqrvDFVodRkCLAQuTnIC3QfgUUPVn4RTNkhSYxzqkaTGGPyS1BiDX5IaY/BLUmMMfklqjMGvqUtSST424/5vJfnQBnrv85K8Y0O81zrqHNXPsnnd0LWkZ8vg18bgCeBtSXaYdiMz9cc1TOoE4Ner6vVD9SNtKAa/NgYr6Q7k+Y3ZD8zeYk/y/f764CR/leTiJH+XZGGS/9yfV+D2JHvMeJs3Jfm//fMO7V+/RZKPJrkpyW1J3jPjfa9L8lng9tX0c0z//ouTfKRf9vvAa4E/T/LRWc9/TpL/0c8D/8UkV61an3TnAtihvz0vyfX97a37Od1v6idxO7xf/rP9+t3a97xn/9wr051LYXGSX+qfu3//53NzkqtnTBfwviR/27/+c+vxd6XNgEfuamPxZ8BtSf74Gbxmb7opdx+mO/r1M1V1QLqT2JwCnNY/by7wC8AewHVJ/i3wLrrZIV+V5HnAXydZNVPkAcArq+ofZxZL8hK6yb72B75DN6vnEVX1h0neAPxWVc0+mcvb+vr/jm5GxiXAOetYr/9KN33Fu/upNG5M8pfAe4E/rapVR/xuQTfT5P1VNb/v8Sf7OZ8+BRxeVSv6D4M/At5NNxncS6vqiVXTdKg9bvFro9DPRPq/6E7UMamb+vMYPAH8A7AquG+nC9tVLq6qJ6vqLroPiJfRzcvzrn56jBuAFwOrTs5x4+zQ770KuL6fZGwlcCHdvPpr81rgL/r6DwCT/AbwZmBB39v1wPOB3YGvA6cn+R3gp6rqn/t1fVOSjyT591X1PWAv4JXANf17/C7drKsAt9FNFXEsjc9Q2TK3+LUx+STdPC7nzli2kn4DpZ/Y67kzHntixu0nZ9x/kqf+2549L0kBAU6pqqtnPpDkYLppklcn6+j/mb7mX9aNLtxnvubtVXXnrOcvSXID3Ylrrk7yK1X1lST70235//f+W8tlwB1VtbrTOc6n+7A6DPi9JD/bf4ipIW7xa6NRVQ8DF9P9ULrKUrqhFejmct9qPd76qH6sfQ+6k6DcCVwN/Fo/LEKSn8m6T4ZyA/ALSXbof/g9hu5sTmvzNeDtff2d6CbvWmUp/7pub5+x/GrglP6DjiT79tc/DdxdVWfQzfb4c/3w0+NVdQHdSU7269dvTvrz+CbZqv994DnAblV1Hd3Jb7YDtllH/9oMucWvjc3HgJNn3P80cHmSG+nOVbqmrfG1uZMuoHcC3ltVP0jyGbrhoFv6gF3BOk6HV1XLknyAbrgmwFVVta7pdS+hm354MfB3dB8e3+sf+wPg7CSn89SzrX2Y7tvPbX1vS4FDgV8Cjk3yI+AB4A/php8+muRJupknf62qftj/gHxGkp+k+3/+yb7+Bf2yAJ+Y0ikfNWXOzikNLMk2VfX9dNMC30h31q8Hpt2X2uUWvzS8L/Z70DwX+LChr2lzi1+SGuOPu5LUGINfkhpj8EtSYwx+SWqMwS9Jjfn/QP2jVv1fYrkAAAAASUVORK5CYII=\n",
"text/plain": [
"
"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"def entropy(counts: List[int]) -> float: return -neg_entropy(counts)\n",
"\n",
"report_minimizing_tree(entropy, inconsistent=False)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that, as expected, the \"worst\" word, `'FUZZY'` is the first guess. Overall, we do pretty well, surviving up to 11 guesses a few times, with a median of 6."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Jotto\n",
"\n",
"[Jotto](https://en.wikipedia.org/wiki/Jotto) is a venerable word game (invented in 1955) that is quite similar to Wordle. The difference is that the reply in Jotto is an integer from 0 to 5 giving the number of matching letters, with no indication of which letter(s) are correct nor whether they are in the right position or not. There are several variants of Jotto; here are four key questions and my answers:\n",
"\n",
"- How many letters can each word have? **Five**.\n",
"- Does a guess have to be a word in the word list? **Yes.**\n",
"- Can a word have repeated letters, like the \"E\" in \"ELECT\"? **No. Every word must have 5 distinct letters.**\n",
"- What if the reply is \"5\", but the guess is not the target? **Not allowed.** *(E.g., only one of the anagrams APERS/PARES/PARSE/PEARS/REAPS/SPARE/SPEAR is allowed in the word list.)*\n",
"\n",
"We can make a Jotto word list by:\n",
"- Starting with a list of words. (We'll use the Wordle word list.)\n",
"- Discarding the ones that don't have 5 distinct letters.\n",
"- Putting the rest into a dict of anagrams keyed by the set of letters.\n",
"- Keeping only one word for each anagram."
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [],
"source": [
"def jotto_allowable(wordlist) -> List[Word]:\n",
" \"\"\"Build a list of allowable Jotto words from an iterable of words.\"\"\"\n",
" anagrams = {frozenset(w): w for w in wordlist if len(set(w)) == 5 == len(w)}\n",
" return sorted(anagrams.values())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The right thing to do now would be to refactor the code to allow for the injection of a different `reply_for` function, and a different `wordlist`, so that either game could be played at any time.\n",
"\n",
"However, I'm going to take a shortcut: I'm going to require the programmer to call `setup_game` with the name of the game they want, `'jotto'` or `'wordle'`. This will set global variables accordingly. Notice we mutate `wordlist` rather than rebinding it, because it has already been assigned as a default parameter value in various functions, and we don't want to require the caller to explicitly override those defaults."
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [],
"source": [
"wordle_reply_for = reply_for # Save the original Wordle reply_for function\n",
"wordle_wordlist = list(wordlist) # Save a copy of the original Wordle wordlist, which will be mutated\n",
"\n",
"def jotto_reply_for(guess, target) -> Reply: \n",
" \"The number of letters in common between the target and guess\"\n",
" return len(set(target).intersection(guess))\n",
"\n",
"def setup_game(game: str) -> None:\n",
" \"Redefine global variables to allow play of either 'jotto' or 'wordle'.\"\n",
" global histogram_bins, reply_for, Correct\n",
" table = {'wordle': (10, wordle_reply_for, 5 * 'G', wordle_wordlist),\n",
" 'jotto': (16, jotto_reply_for, 5, jotto_allowable(wordle_wordlist))}\n",
" histogram_bins, reply_for, Correct, wordlist[:] = table[game]"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: ZONAL, Reply: 1; Remaining targets: 612\n",
"Guess 2: ZESTY, Reply: 1; Remaining targets: 288\n",
"Guess 3: FREAK, Reply: 2; Remaining targets: 83\n",
"Guess 4: HOMER, Reply: 2; Remaining targets: 35\n",
"Guess 5: PLIER, Reply: 1; Remaining targets: 12\n",
"Guess 6: BEACH, Reply: 2; Remaining targets: 6\n",
"Guess 7: HARDY, Reply: 5; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"7"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"setup_game('jotto')\n",
"play(random_guesser)"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: PROUD, Reply: 1; Remaining targets: 594\n",
"Guess 2: QUASI, Reply: 1; Remaining targets: 307\n",
"Guess 3: FIEND, Reply: 0; Remaining targets: 41\n",
"Guess 4: CHART, Reply: 3; Remaining targets: 11\n",
"Guess 5: CRAZY, Reply: 2; Remaining targets: 5\n",
"Guess 6: MOCHA, Reply: 4; Remaining targets: 2\n",
"Guess 7: CHAMP, Reply: 3; Remaining targets: 1\n",
"Guess 8: HAVOC, Reply: 5; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"play(random_guesser)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Below we show that we can switch back to Wordle, and then back to Jotto again, and things still function properly:"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: ANGLE, Reply: .....; Remaining targets: 309\n",
"Guess 2: WISPY, Reply: .GG.G; Remaining targets: 4\n",
"Guess 3: RISKY, Reply: GGGGG; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"setup_game ('wordle')\n",
"play(random_guesser)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Guess 1: SHARK, Reply: 1; Remaining targets: 577\n",
"Guess 2: TWANG, Reply: 1; Remaining targets: 250\n",
"Guess 3: BRINY, Reply: 2; Remaining targets: 69\n",
"Guess 4: GIVER, Reply: 1; Remaining targets: 26\n",
"Guess 5: HYMEN, Reply: 2; Remaining targets: 7\n",
"Guess 6: MOURN, Reply: 0; Remaining targets: 3\n",
"Guess 7: PITHY, Reply: 5; Remaining targets: 1\n"
]
},
{
"data": {
"text/plain": [
"7"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"setup_game('jotto')\n",
"play(random_guesser)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Reports on Consistent Jotto Guessers\n",
"\n",
"As with Wordle, we'll give reports on the Jotto guessers for various metrics, and for the random guesser:"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"minimizing the max of partition sizes over 1,391 targets; inconsistent guesses prohibited\n",
"first guess: \"DRAPE\"\n",
"median: 6 guesses, mean: 6.31 ± 1.43, worst: 16, best: 1\n",
"cumulative: ≤2:0%, ≤3:2%, ≤4:7%, ≤5:24%, ≤6:58%, ≤7:88%, ≤8:95%, ≤9:97%, ≤10:99%\n",
"CPU times: user 1.4 s, sys: 13.2 ms, total: 1.41 s\n",
"Wall time: 1.42 s\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEGCAYAAABiq/5QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAXf0lEQVR4nO3df7xcdX3n8dfbEJRfCkigEXBjWbS2bAWMSItSBbUIPvihYmXVsisWtaJQq2vU1h91fSxo/bH6aLEoIFsQSwUEkS0iQtWuBgNCCI0WxahgIPEn/qho4LN/nJN6Dbk3c2fmzE1yXs/HYx4zc2bmcz5z79z3nPudM9+TqkKS1B8PmusGJEmTZfBLUs8Y/JLUMwa/JPWMwS9JPbPNXDcwiN12260WLVo0121I0hblhhtu+G5VLdhw+RYR/IsWLWLZsmVz3YYkbVGSfHNjyx3qkaSeMfglqWcMfknqGYNfknrG4JeknjH4JalnDH5J6hmDX5J6xuCXpJ7ZIr65qy3XoiWfHLnGqtOPGkMnktZzi1+Sesbgl6SeMfglqWcMfknqGYNfknrG4JeknjH4JalnDH5J6hmDX5J6xuCXpJ4x+CWpZwx+SeoZg1+Sesbgl6SeMfglqWcMfknqmc4OxJLkIcBngQe36/lYVb05ya7APwCLgFXA86rqB131oa2HB3WRxqPLLf57gcOq6nHA/sARSQ4GlgDXVNW+wDXtdUnShHQW/NX4SXt1fnsq4BjgvHb5ecCxXfUgSXqgTsf4k8xLchOwBri6qpYCe1TVaoD2fPdpHntykmVJlq1du7bLNiWpVzoN/qq6r6r2B/YCDkqy3ywee1ZVLa6qxQsWLOisR0nqm4ns1VNVPwSuA44A7k6yEKA9XzOJHiRJjc6CP8mCJDu3l7cDngZ8BbgcOLG924nAZV31IEl6oM525wQWAuclmUfzBnNRVV2R5AvARUlOAr4FHN9hD5KkDXQW/FW1HDhgI8u/Bxze1XolSTPzm7uS1DMGvyT1jMEvST1j8EtSzxj8ktQzBr8k9YzBL0k9Y/BLUs8Y/JLUMwa/JPWMwS9JPWPwS1LPGPyS1DMGvyT1jMEvST1j8EtSzxj8ktQzBr8k9YzBL0k9Y/BLUs8Y/JLUMwa/JPVMZ8GfZO8k1yZZmeTWJKe2y9+S5M4kN7WnI7vqQZL0QNt0WHsd8OdVdWOSnYAbklzd3vaeqvrrDtctSZpGZ8FfVauB1e3lHydZCezZ1fokSYOZyBh/kkXAAcDSdtEpSZYnOSfJLtM85uQky5IsW7t27STalKRe6Dz4k+wIXAycVlX3AGcC+wD70/xH8K6NPa6qzqqqxVW1eMGCBV23KUm90WnwJ5lPE/oXVNUlAFV1d1XdV1X3Ax8EDuqyB0nSr+tyr54AZwMrq+rdU5YvnHK344AVXfUgSXqgLvfqOQR4EXBLkpvaZW8ATkiyP1DAKuClHfYgSdpAl3v1fB7IRm66sqt1SpI2zW/uSlLPGPyS1DMGvyT1jMEvST1j8EtSzxj8ktQzBr8k9YzBL0k9Y/BLUs8Y/JLUMwa/JPWMwS9JPWPwS1LPGPyS1DMGvyT1zCaDP8nxSXZqL/9FkkuSHNh9a5KkLgyyxf+XVfXjJE8C/hA4j+aA6ZKkLdAgwX9fe34UcGZVXQZs211LkqQuDRL8dyb5O+B5wJVJHjzg4yRJm6FBAvx5wFXAEVX1Q2BX4LVdNiVJ6s4mg7+qfgasAZ7ULloH3NZlU5Kk7gyyV8+bgdcBr28XzQfO77IpSVJ3BhnqOQ44GvgpQFV9B9hpUw9KsneSa5OsTHJrklPb5bsmuTrJbe35LqM8AUnS7AwS/L+oqgIKIMkOA9ZeB/x5VT0WOBh4RZLfBpYA11TVvsA17XVJ0oQMEvwXtXv17JzkT4BPAx/c1IOqanVV3dhe/jGwEtgTOIbmuwC058cO0bckaUjbzHRjkgD/APwWcA/wGOBNVXX1bFaSZBFwALAU2KOqVkPz5pBk92keczJwMsAjH/nI2axOkjSDGYO/qirJx6vq8cCswn69JDsCFwOnVdU9zXvJplXVWcBZAIsXL65h1i1JeqBBhnq+mOQJwxRPMp8m9C+oqkvaxXcnWdjevpBmV1FJ0oQMEvxPpQn/rydZnuSWJMs39aB2mOhsYGVVvXvKTZcDJ7aXTwQum23TkqThzTjU03rmkLUPAV4E3JLkpnbZG4DTaT4wPgn4FnD8kPUlSUPYZPBX1TeTPA54crvoc1V18wCP+zww3YD+4YO3KEkap0G+uXsqcAGwe3s6P8kru25MktSNQYZ6TgKeWFU/BUhyBvAF4P1dNiZJ6sYgH+6GX83JT3t5sH0yJUmbnUG2+M8Flia5tL1+LM3eOpKkLdAgH+6+O8l1NNMyB/jvVfXlrhuTJHVjk8Gf5GDg1vXz7iTZKckTq2pp591JksZukDH+M4GfTLn+UzzYuiRtsQb6cLedlhmAqrqfwT4bkCRthgYJ/tuTvCrJ/PZ0KnB7141JkroxSPC/DPh94E7gDuCJtNMlS5K2PIPs1bMGeP4EepEkTcAgUza8I8lD22Gea5J8N8kLJ9GcJGn8BhnqeUZV3QM8i2ao59HAazvtSpLUmUGCf357fiRwYVV9v8N+JEkdG2S3zE8k+Qrw78CfJlkA/LzbtiRJXRnkw90l7Yyc91TVfUl+BhzTfWuaK4uWfHLkGqtOP2oMnUjqwkBfxKqqH0y5/FOab+9KkrZAg4zxS5K2ItMGf5JD2vMHT64dSVLXZtrif197/oVJNCJJmoyZxvh/meRcYM8k79vwxqp6VXdtSZK6MlPwPwt4GnAYcMNk2pEkdW3a4K+q7wIfTbKyqm6ebeEk59C8eaypqv3aZW8B/gRY297tDVV15ay7liQNbZC9er6X5NIka5LcneTiJHsN8LgPA0dsZPl7qmr/9mToS9KEDRL85wKXA48A9gQ+0S6bUVV9FnB6B0nazAwS/LtX1blVta49fRhYMMI6T0myPMk5SXaZ7k5JTk6yLMmytWvXTnc3SdIsDRL8a5O8MMm89vRC4HtDru9MYB9gf2A18K7p7lhVZ1XV4qpavGDBKO8zkqSpBgn+FwPPA+6iCevntstmrarurqr72uP2fhA4aJg6kqThDTJJ27eAo8exsiQLq2p1e/U4YMU46kqSBjfQJG3DSHIh8BRgtyR3AG8GnpJkf6CAVcBLu1q/JGnjOgv+qjphI4vP7mp9kqTBODunJPXMwMGf5OAkn0nyL0mO7bAnSVKHph3qSfIbVXXXlEWvpvmQN8D/Az7ebWuSpC7MNMb/gSQ3AO+sqp8DPwT+K3A/cM8EepMkdWDaoZ6qOha4CbgiyYuA02hCf3vg2O5bkyR1YcYx/qr6BPCHwM7AJcBXq+p9VeUcCpK0hZrp0ItHJ/k88BmaL1o9HzguyYVJ9plUg5Kk8ZppjP9/Ar8HbAdcWVUHAa9Osi/wdpo3AknSFmam4P8RTbhvB6xZv7CqbsPQl6Qt1kxj/MfRfJC7jmZvHknSVmBTh158/wR7kSRNgFM2SFLPGPyS1DMGvyT1jMEvST1j8EtSzxj8ktQzBr8k9YzBL0k9Y/BLUs8Y/JLUMwa/JPVMZ8Gf5Jwka5KsmLJs1yRXJ7mtPd+lq/VLkjauyy3+DwNHbLBsCXBNVe0LXNNelyRNUGfBX1WfBb6/weJjgPPay+fhsXslaeImPca/R1WtBmjPd5/w+iWp9zbbD3eTnJxkWZJla9d6bHdJGpdJB//dSRYCtOdrprtjVZ1VVYuravGCBQsm1qAkbe0mHfyXAye2l08ELpvw+iWp97rcnfNC4AvAY5LckeQk4HTg6UluA57eXpckTdC0x9wdVVWdMM1Nh3e1TknSpm22H+5Kkrph8EtSzxj8ktQzBr8k9YzBL0k9Y/BLUs8Y/JLUMwa/JPWMwS9JPWPwS1LPGPyS1DOdzdUjbc4WLfnkyDVWnX7UGDqRJs8tfknqGYNfknrG4JeknjH4JalnDH5J6hmDX5J6xuCXpJ4x+CWpZwx+SeoZg1+SesYpG7YSTkEgaVBzEvxJVgE/Bu4D1lXV4rnoQ5L6aC63+J9aVd+dw/VLUi85xi9JPTNXwV/Ap5LckOTkjd0hyclJliVZtnbt2gm3J0lbr7kK/kOq6kDgmcArkhy64R2q6qyqWlxVixcsWDD5DiVpKzUnwV9V32nP1wCXAgfNRR+S1EcTD/4kOyTZaf1l4BnAikn3IUl9NRd79ewBXJpk/fo/UlX/NAd9SFIvTTz4q+p24HGTXq8kqeHunJLUMwa/JPWMwS9JPWPwS1LPGPyS1DMGvyT1jMEvST1j8EtSzxj8ktQzBr8k9YzBL0k9Y/BLUs/M5TF3pa3CoiWfHEudVacfNZY60qa4xS9JPWPwS1LPONQzRxwekDRX3OKXpJ4x+CWpZxzqkTYjDgFqEtzil6SeMfglqWcc6pG2YuMYOnLYaOszJ1v8SY5I8tUkX0uyZC56kKS+mvgWf5J5wN8ATwfuAL6U5PKq+tdJ9zJbfvCmPhvnfw/+JzK35mKo5yDga1V1O0CSjwLHAJ0Evy8waeu2ub4hbc4biqmqsRedcYXJc4Ejquol7fUXAU+sqlM2uN/JwMnt1ccAX+2wrd2A71pri6817nrW2jpqjbve5lprY/5TVS3YcOFcbPFnI8se8O5TVWcBZ3XfDiRZVlWLrbVl1xp3PWttHbXGXW9zrTUbc/Hh7h3A3lOu7wV8Zw76kKRemovg/xKwb5JHJdkWeD5w+Rz0IUm9NPGhnqpal+QU4CpgHnBOVd066T42MM4hJWvNXa1x17PW1lFr3PU211oDm/iHu5KkueWUDZLUMwa/JPVMr4M/yTlJ1iRZMWKdvZNcm2RlkluTnDpivYckuT7JzW29t45Yb16SLye5YpQ6ba1VSW5JclOSZSPW2jnJx5J8pf3Z/d6QdR7T9rP+dE+S00bo68/an/uKJBcmecgItU5t69w6TE8be40m2TXJ1Ulua893GaHW8W1v9ycZeLfCaWq9s/1dLk9yaZKdR6j1trbOTUk+leQRw9aacttrklSS3QapNUNvb0ly55TX25Gj9Jbkle0UNrcmecegvY2kqnp7Ag4FDgRWjFhnIXBge3kn4N+A3x6hXoAd28vzgaXAwSPUezXwEeCKMfzMVgG7jennfx7wkvbytsDOY6g5D7iL5osrwzx+T+AbwHbt9YuA/zZkrf2AFcD2NDtSfBrYd5Y1HvAaBd4BLGkvLwHOGKHWY2m+IHkdsHjEvp4BbNNePmPEvh465fKrgA8MW6tdvjfNDiXfnM3rd5re3gK8ZojXw8ZqPbV9XTy4vb77MK+12Z56vcVfVZ8Fvj+GOqur6sb28o+BlTQBMmy9qqqftFfnt6ehPoVPshdwFPChYfvpQpKH0vwhnA1QVb+oqh+OofThwNer6psj1NgG2C7JNjShPez3TB4LfLGqflZV64B/Bo6bTYFpXqPH0Lxp0p4fO2ytqlpZVbP+Vvw0tT7VPk+AL9J8R2fYWvdMuboDA77+Z/ibfg/wPwatM0C9WZum1suB06vq3vY+a8axrk3pdfB3Icki4ACarfRR6sxLchOwBri6qoat916aF/z9o/QzRQGfSnJDO63GsH4TWAuc2w5DfSjJDmPo7/nAhcM+uKruBP4a+BawGvhRVX1qyHIrgEOTPDzJ9sCR/PqXF4e1R1WtbvtdDew+hprj9mLg/45SIMnbk3wbeAHwphHqHA3cWVU3j9LPBk5ph6LOGXSobRqPBp6cZGmSf07yhHE1OBODf4yS7AhcDJy2wRbLrFXVfVW1P81W00FJ9huin2cBa6rqhlF62cAhVXUg8EzgFUkOHbLONjT/9p5ZVQcAP6UZthha+4XAo4F/HKHGLjRb1I8CHgHskOSFw9SqqpU0Qx5XA/8E3Aysm/FBW4Ekb6R5nheMUqeq3lhVe7d1TtnU/afpZXvgjYzwxrERZwL7APvTbBy8a4Ra2wC7AAcDrwUuSrKxaW3GyuAfkyTzaUL/gqq6ZFx12+GP64Ajhnj4IcDRSVYBHwUOS3L+iP18pz1fA1xKM9vqMO4A7pjyn8zHaN4IRvFM4MaqunuEGk8DvlFVa6vql8AlwO8PW6yqzq6qA6vqUJp/828bobf17k6yEKA9n8jwwCCSnAg8C3hBtYPWY/AR4DlDPnYfmjfxm9u/g72AG5P8xrDNVNXd7YbZ/cAHGf5vAJq/g0va4d3raf4zH/jD52EZ/GPQvkOfDaysqnePod6C9XtEJNmOJoy+Mts6VfX6qtqrqhbRDIF8pqqG2npte9khyU7rL9N8mDfUHlFVdRfw7SSPaRcdzuhTc5/ACMM8rW8BByfZvv29Hk7zmc1Qkuzenj8SePYY+oNmipMT28snApeNoebIkhwBvA44uqp+NmKtfadcPZohXv8AVXVLVe1eVYvav4M7aHbEuGuE3hZOuXocQ/4NtD4OHNbWfTTNTg5dztbZmMQnyJvrieaPcDXwS5oXxElD1nkSzdj3cuCm9nTkCH39LvDltt4K4E1jeK5PYcS9emjG5W9uT7cCbxyx3v7AsvZ5fhzYZYRa2wPfAx42hp/VW2mCZgXw97R7XAxZ63M0b2g3A4cP8fgHvEaBhwPX0Pz3cA2w6wi1jmsv3wvcDVw1Qq2vAd+e8jcw6J44G6t1cfvzXw58Athz2Fob3L6K2e3Vs7He/h64pe3tcmDhCLW2Bc5vn+uNwGGjvn4HOTllgyT1jEM9ktQzBr8k9YzBL0k9Y/BLUs8Y/JLUMwa/5lw7Y+K7plx/TZK3jKn2h5M8dxy1NrGe49PMMHpt1+uSRmXwa3NwL/Ds2UyXOwlJ5s3i7icBf1pVT+2qH2lcDH5tDtbRHHv0zza8YcMt9iQ/ac+f0k5qdVGSf0tyepIXpDmOwS1J9plS5mlJPtfe71nt4+e188d/qZ1s66VT6l6b5CM0X9LZsJ8T2vorkpzRLnsTzZf4PpDknRvc/0FJ/rada/2KJFeufz5pjm2wW3t5cZLr2ss7tJN/famdwO6YdvnvtM/vprbnfdv7fjLNsRtWJPmj9r6Pb38+NyS5asoUD69K8q/t4z86xO9KW4GJH2xdmsbfAMszuwNRPI5m6uPvA7cDH6qqg9IcCOeVwGnt/RYBf0Azb8u1Sf4z8Mc0M28+IcmDgX9Jsn4WzoOA/arqG1NXluZgIGcAjwd+QDNL6bFV9VdJDqOZo33Dg9M8u13/f6GZRXMlcM4mntcbaabXeHE7dcf1ST4NvAz431V1QTsh3TyaGT+/U1VHtT0+rJ036v3AMVW1tn0zeDvNjJlLgEdV1b0Z8EAp2vq4xa/NQjWzmf4fmoNuDOpL1RwL4V7g68D64L6FJmzXu6iq7q+q22jeIH6LZp6hP04z9fVSmmkQ1s8Pc/2God96AnBdNRO4rZ99clOzkz4J+Md2/XcBg3wG8AxgSdvbdcBDgEcCXwDekOR1NAea+ff2uT4tyRlJnlxVP6I5sMp+wNVtjb/gV3PjLwcuSDPj6FY/U6g2zi1+bU7eSzNfyblTlq2j3UBpJ03bdspt9065fP+U6/fz66/tDeclKZqjnL2yqq6aekOSp9BMEb0xw0yXO9Nj/uO50YT71Mc8px54gJSVSZbSHFjnqiQvqarPJHk8zZb//2r/a7kUuLWqNnYoy6No3qyOBv4yye/Urw6eop5wi1+bjar6Ps2hDk+asngVzdAKNPPkzx+i9PHtWPs+NBPNfZXmMHwvb4dFSPLobPpAMEuBP0iyW/vB7wk0R9WayeeB57Tr34Nmsrz1VvGr5zZ12uGrgFe2b3QkOaA9/03g9qp6H83kYL/bDj/9rKrOpzmAzIHt81uQ9hjGSea3nw88CNi7qq6lOTjPzsCOm+hfWyG3+LW5eRe/ftCNDwKXJbmeZibK6bbGZ/JVmoDeA3hZVf08yYdohoNubAN2LZs4hGFVrU7yeprhmgBXVtWmpkS+mGZq5xU0x2JeCvyove2twNlJ3sCvH7HtbTT//Sxve1tFM8f9HwEvTPJLmuMK/xXN8NM7k9xPM+vjy6vqF+0HyO9L8jCav/P3tus/v10W4D01nsNdagvj7JxSx5LsWFU/SfJw4Hqao5gNPR+8NCq3+KXuXdHuQbMt8DZDX3PNLX5J6hk/3JWknjH4JalnDH5J6hmDX5J6xuCXpJ75/4XWrbpng59yAAAAAElFTkSuQmCC\n",
"text/plain": [
"
"
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"%time report_minimizing_tree(neg_entropy, inconsistent=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Jotto and Wordle Evaluation Summary\n",
"\n",
"Here is a summary of the reports on both games:\n",
"\n",
"|
Algorithm|JOTTO Inonsistent Prohibited Mean (Max)|JOTTO Inconsistent Allowed Mean (Max)|WORDLE Inconsistent Prohibited Mean (Max)|WORDLE Inconsistent Allowed Mean (Max)||\n",
"|--|--|--|--|--|--|\n",
"|minimize max |6.31 (16)|6.38 (9)| 3.68 (8) | 3.64 (6) | \n",
"|minimize expectation|6.11 (14)|6.13 (9)| 3.62 (8) | 3.55 (6) | \n",
"|minimize neg_entropy|6.31 (15)|6.18 (9)| 3.60 (8) | 3.52 (6) |\n",
"|random guesser |6.59 (13)| | 4.09 (9) | |\n",
"\n",
"\n",
"One surprising thing: allowing inconsistent guesses in Jotto does *not* improve the mean score with eiither the max or expectation metric. However, it does uniformly improve the worst score.\n",
"\n",
"\n",
"# Jotto Best and Worst First Guesses\n",
"\n",
"Here are the best and worst first guesses for Jotto:"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"
\n",
"\n",
"
\n",
" \n",
"
\n",
"
\n",
"
max_word
\n",
"
max_score
\n",
"
exp_word
\n",
"
exp_score
\n",
"
ent_word
\n",
"
ent_score
\n",
"
\n",
" \n",
" \n",
"
\n",
"
0
\n",
"
DRAPE
\n",
"
497
\n",
"
SOUTH
\n",
"
400.50
\n",
"
STARE
\n",
"
-1.971
\n",
"
\n",
"
\n",
"
1
\n",
"
DREAM
\n",
"
497
\n",
"
DEBAR
\n",
"
401.43
\n",
"
CEDAR
\n",
"
-1.964
\n",
"
\n",
"
\n",
"
2
\n",
"
TRASH
\n",
"
497
\n",
"
CRAVE
\n",
"
401.94
\n",
"
DEBAR
\n",
"
-1.961
\n",
"
\n",
"
\n",
"
3
\n",
"
DEBAR
\n",
"
499
\n",
"
STARE
\n",
"
402.56
\n",
"
SPEAR
\n",
"
-1.958
\n",
"
\n",
"
\n",
"
4
\n",
"
DECAL
\n",
"
499
\n",
"
CEDAR
\n",
"
402.94
\n",
"
REACH
\n",
"
-1.958
\n",
"
\n",
"
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
...
\n",
"
\n",
"
\n",
"
1386
\n",
"
QUAIL
\n",
"
740
\n",
"
AVOID
\n",
"
534.45
\n",
"
QUASI
\n",
"
-1.600
\n",
"
\n",
"
\n",
"
1387
\n",
"
QUAKE
\n",
"
740
\n",
"
QUAKE
\n",
"
534.54
\n",
"
JUICY
\n",
"
-1.587
\n",
"
\n",
"
\n",
"
1388
\n",
"
AVOID
\n",
"
745
\n",
"
QUASI
\n",
"
538.90
\n",
"
JUMPY
\n",
"
-1.564
\n",
"
\n",
"
\n",
"
1389
\n",
"
AUDIO
\n",
"
761
\n",
"
AUDIO
\n",
"
595.22
\n",
"
AXIOM
\n",
"
-1.500
\n",
"
\n",
"
\n",
"
1390
\n",
"
AXIOM
\n",
"
827
\n",
"
AXIOM
\n",
"
599.56
\n",
"
AUDIO
\n",
"
-1.460
\n",
"
\n",
" \n",
"
\n",
"
1391 rows × 6 columns
\n",
"
"
],
"text/plain": [
" max_word max_score exp_word exp_score ent_word ent_score\n",
"0 DRAPE 497 SOUTH 400.50 STARE -1.971\n",
"1 DREAM 497 DEBAR 401.43 CEDAR -1.964\n",
"2 TRASH 497 CRAVE 401.94 DEBAR -1.961\n",
"3 DEBAR 499 STARE 402.56 SPEAR -1.958\n",
"4 DECAL 499 CEDAR 402.94 REACH -1.958\n",
"... ... ... ... ... ... ...\n",
"1386 QUAIL 740 AVOID 534.45 QUASI -1.600\n",
"1387 QUAKE 740 QUAKE 534.54 JUICY -1.587\n",
"1388 AVOID 745 QUASI 538.90 JUMPY -1.564\n",
"1389 AUDIO 761 AUDIO 595.22 AXIOM -1.500\n",
"1390 AXIOM 827 AXIOM 599.56 AUDIO -1.460\n",
"\n",
"[1391 rows x 6 columns]"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"first_guesses(wordlist)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One difference is that in Jotto, most of the best guesses have two vowels, in Wordle three.\n",
"\n",
"`'OUIJA'` is not in our word list, but it was in another list, and it is uniquely bad as a Jotto guess, worse than `'AXIOM'` or `'AUDIO'`. \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Next Steps\n",
"\n",
"There are many directions you could take this if you are interested:\n",
"- **Other games:**\n",
" - Implement [Mastermind](https://en.wikipedia.org/wiki/Mastermind_%28board_game%29). The default version has 6 colors and 4 pegs. Can you go beyond that?\n",
" - Consider a Jotto game variant where each reply consists of two numbers: the number of letters in common with the target, and the number of letters that are in the exact correct position, as in Mastermind.\n",
" - Research what other computer scientists have done with [Jotto](https://arxiv.org/abs/1107.3342) or [Mastermind](http://serkangur.freeservers.com/).\n",
" - There are many variants of Wordle: Evil Wordle, Anti-Wordle, Quordle, Octordle, ...\n",
" - Refactor the code so it can more smoothly handle multiple different games.\n",
"- **Better strategy**:\n",
" - Our `minimizing_tree` function is **greedy** in that it guesses the word that minimizes some metric of the current situation without looking ahead to future branches in the tree. Can you get better performance by doing some **look-ahead**? Perhaps with a beam search?\n",
" - As an alternative to look-ahead, can you improve a tree by editing it? Given a tree, look for interior nodes that end up with a worse-than-expected average score, and see if the node can be replaced with something better (covering the same target words). Correcting a few bad nodes might be faster than carefully searching for good nodes in the first place.\n",
" - The three metrics (max, expectation, and negative entropy) are all designed as proxies to what we really want to minimize: the average number of guesses. Can we estimate that directly? For example, we know a branch of size 1 will always take 1 guess; a branch of size 2 an average of 3/2 guesses; and a branch of size 3 an average of 5/3 guesses if one of the words partitions the other two, otherwise an average of 2. Can we learn a function that takes a set of words as input and estimates the average number of guesses for the set? Would a deep neural net be a good way to learn this function?\n",
" - Is it feasible to do a complete search and find the guaranteed optimal strategy? What optimizations to the code would be necessary? Is it worthwhile to port to a different language? How long would the search take?\n",
" - We assume that the list of taregt words is known to the guesser. The [New York Times WordleBot](https://www.nytimes.com/interactive/2022/upshot/wordle-bot.html) initally took this approach too, but then switched to a more nuanced approach where the guesser (the Bot) does not know for sure the list of target words, but instead assigns words a probability of being a target word that is correlated with the word's frequency in English usage. Can you develop a guesser that works along these lines?\n",
"- **Chooser strategy**:\n",
" - Analyze the game where the chooser is not random, but rather is an adversary to the guesser–the chooser tries to choose a word that will maximize the guesser's score. What's a good strategy for the chooser? Is there a strategy equilibrium?\n",
" - Refactor `play` to accomodate three roles:\n",
" - A chooser, who decides what the target word is.\n",
" - A guesser, who guesses the target word.\n",
" - A replier, who says what the reply to the guess is."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}