ipynb/SpellingBee.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\" align=\"right\"><i>Peter Norvig, 3 Jan 2020</i></div>\n",
    "\n",
    "# Spelling Bee Puzzle\n",
    "\n",
    "The [3 Jan. 2020 edition of the **538 Riddler**](https://fivethirtyeight.com/features/can-you-solve-the-vexing-vexillology/) concerns the popular NYTimes  [**Spelling Bee**](https://www.nytimes.com/puzzles/spelling-bee) puzzle:\n",
    "\n",
    "> In this game, seven letters are arranged in a **honeycomb** lattice, with one letter in the center. Here’s the lattice from Dec. 24, 2019:\n",
    "> \n",
    "> <img src=\"https://fivethirtyeight.com/wp-content/uploads/2020/01/Screen-Shot-2019-12-24-at-5.46.55-PM.png?w=1136\" width=\"150\">\n",
    "> \n",
    "> The goal is to identify as many words as possible that meet the following criteria:\n",
    "> 1. The word must be at least four letters long.\n",
    "> 2. The word must include the central letter.\n",
    "> 3. The word cannot include any letter beyond the seven given letters.\n",
    ">\n",
    ">Note that letters can be repeated. For example, the words GAME and AMALGAM are both acceptable words. Four-letter words are worth 1 point each, while five-letter words are worth 5 points, six-letter words are worth 6 points, etc. Words that use all seven letters in the honeycomb are known as **pangrams** and earn 7 bonus points (in addition to the points for the length of the word). So in the above example, MEGAPLEX is worth 8 + 7 = 15 points.\n",
    ">\n",
    "> ***Which seven-letter honeycomb results in the highest possible score?*** To be a valid choice of seven letters, no letter can be repeated, it must not contain the letter S (that would be too easy) and there must be at least one pangram.\n",
    ">\n",
    "> For consistency, please use [this word list](https://norvig.com/ngrams/enable1.txt) to check your game score.\n",
    "\n",
    "\n",
    "\n",
    "Since the referenced [word list](https://norvig.com/ngrams/enable1.txt) came from [***my*** web site](https://norvig.com/ngrams), I felt somewhat compelled to solve this one.  (Note it is a standard Scrabble® word list that I happen to host a copy of; I didn't curate it.) \n",
    "\n",
    "I'll show you how I address the problem. First some imports, then we'll work through 10 steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter, defaultdict\n",
    "from dataclasses import dataclass\n",
    "from itertools   import combinations\n",
    "from typing      import List, Set, Dict, Tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1: Words, Word Scores, and Pangrams\n",
    "\n",
    "Let's start by defining some basic terms:\n",
    "\n",
    "- **valid word**: a string of at least 4  letters ('A' to 'Z' but not 'S'), and not more than 7 distinct letters.\n",
    "- **word list**: a list of valid  words.\n",
    "- **pangram**: a word with exactly 7 distinct letters.\n",
    "- **word score**: 1 for a four letter word, or the length of the word for longer words, plus 7 for a pangram."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_valid(word) -> bool:\n",
    "    \"\"\"Is word 4 or more letters, no 'S', and no more than 7 distinct letters?\"\"\"\n",
    "    return len(word) >= 4 and 'S' not in word and len(set(word)) <= 7\n",
    "\n",
    "def word_list(text) -> List[str]: \n",
    "    \"\"\"All the valid words in text (uppercased).\"\"\"\n",
    "    return [w for w in text.upper().split() if is_valid(w)]\n",
    "\n",
    "def is_pangram(word) -> bool: return len(set(word)) == 7\n",
    "\n",
    "def word_score(word) -> int: \n",
    "    \"\"\"The points for this word, including bonus for pangram.\"\"\"\n",
    "    return 1 if len(word) == 4 else len(word) + 7 * is_pangram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll make a mini word list to experiment with: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AMALGAM', 'CACCIATORE', 'EROTICA', 'GAME', 'GLAM', 'MEGAPLEX']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mini = word_list('amalgam amalgamation cacciatore erotica em game gem gems glam megaplex')\n",
    "mini"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that `em` and `gem` are too short, `gems` has an `s` which is not allowed, and `amalgamation` has too many distinct letters (8). We're left with six valid words out of the ten candidate words. Here are examples of the other two functions in action:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'CACCIATORE', 'EROTICA', 'MEGAPLEX'}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{w for w in mini if is_pangram(w)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AMALGAM': 7,\n",
       " 'CACCIATORE': 17,\n",
       " 'EROTICA': 14,\n",
       " 'GAME': 1,\n",
       " 'GLAM': 1,\n",
       " 'MEGAPLEX': 15}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{w: word_score(w) for w in mini}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2: Honeycombs and Lettersets\n",
    "\n",
    "A honeycomb lattice consists of (1) a set of seven distinct letters and (2) the one distinguished center letter:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "Letter = Letterset = str # Types\n",
    "\n",
    "@dataclass(frozen=True, order=True)\n",
    "class Honeycomb:\n",
    "    \"\"\"A Honeycomb lattice, with 7 letters, 1 of which is the center.\"\"\"\n",
    "    letters: Letterset # 7 letters\n",
    "    center:  Letter    # 1 letter\n",
    "        \n",
    "def letterset(word) -> Letterset:\n",
    "    \"\"\"The set of letters in a word, represented as a sorted str.\"\"\"\n",
    "    return ''.join(sorted(set(word)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Honeycomb(letters='AEGLMPX', center='G')"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "hc = Honeycomb(letterset('MEGAPLEX'), 'G')\n",
    "hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The type `Letter` is a `str` of 1 letter and `Letterset` is an unordered collection of letters, which I will represent as a sorted `str`. Why not a Python `set` or `frozenset`? Because a `str` takes up less space in memory, and its printed representation is  easier to read when debugging. Compare:\n",
    "- `frozenset({'A', 'E', 'G', 'L', 'M', 'P', 'X'})`\n",
    "- `'AEGLMPX'`\n",
    "\n",
    "Why sorted? So that  equal lettersets are equal:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert letterset('EROTICA') == letterset('CACCIATORE') == 'ACEIORT'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3: Game Score\n",
    "\n",
    "The **game score** for a honeycomb is the sum of the word scores for all the words that the honeycomb **can make**. \n",
    "\n",
    "A honeycomb can make a word if\n",
    "(1) the word contains the honeycomb's center, and\n",
    "(2) every letter in the word is in the honeycomb. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def game_score(honeycomb, wordlist) -> int:\n",
    "    \"\"\"The total score for this honeycomb.\"\"\"\n",
    "    return sum(word_score(w) \n",
    "               for w in wordlist if can_make(honeycomb, w))\n",
    "\n",
    "def can_make(honeycomb, word) -> bool:\n",
    "    \"\"\"Can the honeycomb make this word?\"\"\"\n",
    "    return honeycomb.center in word and all(L in honeycomb.letters for L in word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AMALGAM': 7, 'GAME': 1, 'GLAM': 1, 'MEGAPLEX': 15}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{w: word_score(w) for w in mini if can_make(hc, w)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert game_score(hc, mini) == 24 == sum(_.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4: Top Honeycomb\n",
    "\n",
    "The strategy for finding the top (highest-scoring) honeycomb is:\n",
    " - Compile a list of valid candidate honeycombs.\n",
    " - For each honeycomb, compute the game score.\n",
    " - Return a (score, honeycomb) tuple with the highest score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_honeycomb(words) -> Tuple[int, Honeycomb]: \n",
    "    \"\"\"Return a (score, honeycomb) tuple with a highest-scoring honeycomb.\"\"\"\n",
    "    return max((game_score(h, words), h) \n",
    "               for h in candidate_honeycombs(words))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What are the possible candidate honeycombs? We can put any letter (except 'S') in the center, then any 6 remaining letters around the outside;  this gives  25 × (24 choose 6) = 3,364,900 possible honeycombs. It would take hours to apply `game_score` to all of these.\n",
    "\n",
    "Fortunately, we can use the constraint that a valid honeycomb **must make at least one pangram**.  So the letters of any valid honeycomb must ***be*** the letterset of some pangram (and the center can be any of those letters):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def candidate_honeycombs(words) -> List[Honeycomb]:\n",
    "    \"\"\"Valid honeycombs have pangram letters, with any center.\"\"\"\n",
    "    return [Honeycomb(letters, center) \n",
    "            for letters in pangram_lettersets(words)\n",
    "            for center in letters]\n",
    "\n",
    "def pangram_lettersets(words) -> Set[Letterset]:\n",
    "    \"\"\"All lettersets from the pangram words.\"\"\"\n",
    "    return {letterset(w) for w in words if is_pangram(w)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'ACEIORT', 'AEGLMPX'}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pangram_lettersets(mini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Honeycomb(letters='AEGLMPX', center='A'),\n",
       " Honeycomb(letters='AEGLMPX', center='E'),\n",
       " Honeycomb(letters='AEGLMPX', center='G'),\n",
       " Honeycomb(letters='AEGLMPX', center='L'),\n",
       " Honeycomb(letters='AEGLMPX', center='M'),\n",
       " Honeycomb(letters='AEGLMPX', center='P'),\n",
       " Honeycomb(letters='AEGLMPX', center='X'),\n",
       " Honeycomb(letters='ACEIORT', center='A'),\n",
       " Honeycomb(letters='ACEIORT', center='C'),\n",
       " Honeycomb(letters='ACEIORT', center='E'),\n",
       " Honeycomb(letters='ACEIORT', center='I'),\n",
       " Honeycomb(letters='ACEIORT', center='O'),\n",
       " Honeycomb(letters='ACEIORT', center='R'),\n",
       " Honeycomb(letters='ACEIORT', center='T')]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "candidate_honeycombs(mini) # 2×7 of them"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we're ready to find the highest-scoring honeycomb with the mini word list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(31, Honeycomb(letters='ACEIORT', center='T'))"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "top_honeycomb(mini)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**It works.** But that's just the mini word list. \n",
    "\n",
    "# 5: The enable1 Word List\n",
    "\n",
    "Here's the real word list, `enable1.txt`, and some counts derived from it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "aa\n",
      "aah\n",
      "aahed\n",
      "aahing\n",
      "aahs\n",
      "aal\n",
      "aalii\n",
      "aaliis\n",
      "aals\n",
      "aardvark\n"
     ]
    }
   ],
   "source": [
    "! [ -e enable1.txt ] || curl -O http://norvig.com/ngrams/enable1.txt\n",
    "! head enable1.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  172820 enable1.txt\n"
     ]
    }
   ],
   "source": [
    "! wc -w enable1.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44585"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1 = word_list(open('enable1.txt').read())\n",
    "\n",
    "len(enable1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14741"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len([w for w in enable1 if is_pangram(w)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7986"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(pangram_lettersets(enable1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55902"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(candidate_honeycombs(enable1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To summarize, there are:\n",
    "\n",
    "- 172,820 words in the `enable1` word list\n",
    "- 44,585 valid Spelling Bee words\n",
    "- 14,741 pangram words \n",
    "- 7,986 distinct pangram lettersets\n",
    "- 55,902 (7 × 7,986) candidate pangram-containing honeycombs\n",
    "- out of 3,364,900 theoretically possible honeycombs\n",
    "\n",
    "How long will it take to run `top_honeycomb(enable1)`? Most of the computation time is in `game_score` (each call has to look at all 44,585 valid words), so let's estimate the total time by first checking how long it takes to compute the game score of a single honeycomb:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.48 ms ± 29.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit game_score(hc, enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Roughly 9 milliseconds on my computer (this may vary). How many seconds to run `game_score` for all 55,902 valid honeycombs?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "503.118"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "55902 * 9/1000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About 500 seconds, or 8 minutes. I could run `top_honeycomb(enable1)`, take a coffee break, come back, and declare victory. \n",
    "\n",
    "But I think that a puzzle like this deserves a more elegant solution. I'd like to get the run time under a minute (as is suggested in [Project Euler](https://projecteuler.net/)), and I have an idea how to do it. \n",
    "\n",
    "# 6: Faster Algorithm: Points Table\n",
    "\n",
    "Here's my plan:\n",
    "\n",
    "1. Keep the same strategy of trying every pangram letterset, but do some precomputation that will make `game_score` much faster.\n",
    "1. The precomputation is: compute the `letterset` and `word_score` for each word in the word list, and make a table of `{letterset: total_points}` giving the total number of word score points for all the words that correspond to each letterset. I call this a **points table**.\n",
    "3. These calculations are independent of the honeycomb, so they need be done only once, not 55,902  times. \n",
    "4. Every word that a honeycomb can make is formed from a **letter subset** of the honeycomb's 7 letters. A valid letter subset must include the center letter, and may include any non-empty subset of the other 6 letters, so there are 2<sup>6</sup> – 1 = 63 valid letter subsets. \n",
    "4. `game_score2` considers each of the 63 letter subsets of a honeycomb, and sums the point table entry for each one. \n",
    "5. Thus, `game_score2` iterates over just 63 letter subsets; a big optimization over `game_score`, which iterated over 44,585 words.\n",
    "\n",
    "\n",
    "Here's the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "PointsTable = Dict[Letterset, int] # How many points does a letterset score?\n",
    "\n",
    "def top_honeycomb2(words) -> Tuple[int, Honeycomb]: \n",
    "    \"\"\"Return a (score, honeycomb) tuple with a highest-scoring honeycomb.\"\"\"\n",
    "    points_table = tabulate_points(words)\n",
    "    return max((game_score2(h, points_table), h) \n",
    "               for h in candidate_honeycombs(words))\n",
    "\n",
    "def tabulate_points(words) -> PointsTable:\n",
    "    \"\"\"Return a Counter of {letterset: points} from words.\"\"\"\n",
    "    table = Counter()\n",
    "    for w in words:\n",
    "        table[letterset(w)] += word_score(w)\n",
    "    return table\n",
    "\n",
    "def letter_subsets(honeycomb) -> List[Letterset]:\n",
    "    \"\"\"The 63 subsets of the letters in the honeycomb, each including the center letter.\"\"\"\n",
    "    return [letters \n",
    "            for n in range(2, 8) \n",
    "            for letters in map(''.join, combinations(honeycomb.letters, n))\n",
    "            if honeycomb.center in letters]\n",
    "\n",
    "def game_score2(honeycomb, points_table) -> int:\n",
    "    \"\"\"The total score for this honeycomb, using a points table.\"\"\"\n",
    "    return sum(points_table[s] for s in letter_subsets(honeycomb))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's get a feel for how this works. \n",
    "\n",
    "First consider `letter_subsets`. A 4-letter honeycomb makes $2^3 - 1= 7$ subsets; 7-letter honeycombs make $2^6 - 1= 63$ subsets:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AG', 'LG', 'MG', 'ALG', 'AMG', 'LMG', 'ALMG']"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "letter_subsets(Honeycomb('ALMG', 'G')) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's eminded ourselves what `mini` is, and compute `tabulate_points(mini)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mini = ['AMALGAM', 'CACCIATORE', 'EROTICA', 'GAME', 'GLAM', 'MEGAPLEX']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Counter({'AGLM': 8, 'ACEIORT': 31, 'AEGM': 1, 'AEGLMPX': 15})"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('mini =', mini)\n",
    "tabulate_points(mini)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The letterset `'AGLM'` gets 8 points, 7 for AMALGAM and 1 for GLAM.  `'ACEIORT'` gets 31 points, 17 for CACCIATORE and 14 for EROTICA. The other lettersets represent one word each. \n",
    "\n",
    "Let's make sure we haven't broken the  `top_honeycomb` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert top_honeycomb(mini) == top_honeycomb2(mini)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7: The Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, the solution to the puzzle on the real word list:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1.65 s, sys: 3.78 ms, total: 1.65 s\n",
      "Wall time: 1.65 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(3898, Honeycomb(letters='AEGINRT', center='R'))"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time top_honeycomb2(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Wow! 3898 is a high score!** And the whole computation took **less than 2 seconds**!\n",
    "\n",
    "We can see that `game_score2` is about 300 times faster than `game_score`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "26.4 µs ± 90.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "points_table = tabulate_points(enable1)\n",
    "\n",
    "%timeit game_score2(hc, points_table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 8: Even Faster Algorithm: Branch and Bound\n",
    "\n",
    "A run time of less than 2 seconds is pretty good! But I'm not ready to stop now.\n",
    "\n",
    "Consider the word **JUKEBOX**. It is a pangram, but what with the **J**, **K**,  and **X**, it is a low-scoring honeycomb, regardless of what center is used:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{Honeycomb(letters='BEJKOUX', center='J'): 26,\n",
       " Honeycomb(letters='BEJKOUX', center='U'): 32,\n",
       " Honeycomb(letters='BEJKOUX', center='K'): 26,\n",
       " Honeycomb(letters='BEJKOUX', center='E'): 37,\n",
       " Honeycomb(letters='BEJKOUX', center='B'): 49,\n",
       " Honeycomb(letters='BEJKOUX', center='O'): 39,\n",
       " Honeycomb(letters='BEJKOUX', center='X'): 15}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "honeycombs = [Honeycomb(letterset('JUKEBOX'), C) for C in 'JUKEBOX']\n",
    "\n",
    "{h: game_score(h, enable1) for h in honeycombs}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It would be great if we could determine that **JUKEBOX** is not a top honeycomb in one call to `game_score2`, rather than seven calls. My idea:\n",
    "- Keep track of the top score found so far.\n",
    "- For each pangram letterset, ask \"if we weren't required to use the center letter, what would this letterset score?\"\n",
    "- Check if that score (which is an upper bound of the score using any one center letter) is higher than the top score so far.\n",
    "- If yes, then try it with all seven centers; if not then discard it without trying any centers.\n",
    "- This is called a [**branch and bound**](https://en.wikipedia.org/wiki/Branch_and_bound) algorithm: prune a whole **branch** (of 7 honeycombs) if an upper **bound** can't beat the top score.\n",
    "\n",
    "To compute the score of a honeycomb with no center, it turns out I can just call `game_score2` on `Honeycomb(letters, '')`. This works because of a quirk of Python:  `game_score2` checks if `honeycomb.center in letters`; normally in Python the expression `x in y` means \"is `x` a member of the collection `y`\", but when `y` is a string it means \"is `x` a substring of `y`\", and the empty string is a substring of every string. (If I had represented a letterset as a Python `set`, this wouldn't work.)\n",
    "\n",
    "Thus, I can rewrite `top_honeycomb` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_honeycomb3(words) -> Tuple[int, Honeycomb]: \n",
    "    \"\"\"Return a (score, honeycomb) tuple with a highest-scoring honeycomb.\"\"\"\n",
    "    points_table = tabulate_points(words)\n",
    "    top_score, top = -1, None\n",
    "    pangrams = (s for s in points_table if len(s) == 7)\n",
    "    for p in pangrams:\n",
    "        if game_score2(Honeycomb(p, ''), points_table) > top_score:\n",
    "            for center in p:\n",
    "                honeycomb = Honeycomb(p, center)\n",
    "                score = game_score2(honeycomb, points_table)\n",
    "                if score > top_score:\n",
    "                    top_score, top = score, honeycomb\n",
    "    return top_score, top"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 360 ms, sys: 2 ms, total: 362 ms\n",
      "Wall time: 361 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(3898, Honeycomb(letters='AEGINRT', center='R'))"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time top_honeycomb3(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Awesome! We get the same answer, and the computation is about 5 times faster; about **1/3 second**.\n",
    "\n",
    "For how many pangram lettersets did we have to check all 7 centers? We can find out by copy-pasting `top_honeycomb3` and annotating it to keep a `COUNT` of the number of pangrams that are checked, and to print a line of output when a honeycomb (either with or without a center letter) outscores the top score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ADFLORW scores  333 with center ∅ (pangram  1 (1/7986))\n",
      "        scores  265 with center A \n",
      "ABDENOR scores 1856 with center ∅ (pangram  2 (2/7986))\n",
      "        scores 1148 with center A \n",
      "        scores 1476 with center D \n",
      "        scores 1578 with center E \n",
      "ABEIRTV scores 1585 with center ∅ (pangram  3 (4/7986))\n",
      "ABDEORT scores 2434 with center ∅ (pangram  4 (28/7986))\n",
      "        scores 1679 with center A \n",
      "        scores 2134 with center E \n",
      "ABCDERT scores 2254 with center ∅ (pangram  5 (35/7986))\n",
      "ACELNRT scores 2529 with center ∅ (pangram  6 (46/7986))\n",
      "        scores 2158 with center A \n",
      "        scores 2225 with center E \n",
      "ACDELRT scores 2746 with center ∅ (pangram  7 (47/7986))\n",
      "        scores 2273 with center A \n",
      "        scores 2608 with center E \n",
      "ACENORT scores 2799 with center ∅ (pangram  8 (50/7986))\n",
      "ACEIPRT scores 2653 with center ∅ (pangram  9 (57/7986))\n",
      "ACDEIRT scores 3407 with center ∅ (pangram 10 (71/7986))\n",
      "        scores 3023 with center E \n",
      "ACEINRT scores 3575 with center ∅ (pangram 11 (77/7986))\n",
      "ADEOPRT scores 3031 with center ∅ (pangram 12 (157/7986))\n",
      "AEGINRT scores 4688 with center ∅ (pangram 13 (178/7986))\n",
      "        scores 3372 with center A \n",
      "        scores 3769 with center E \n",
      "        scores 3782 with center N \n",
      "        scores 3898 with center R \n",
      "ADEINRT scores 4020 with center ∅ (pangram 14 (419/7986))\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(3898, Honeycomb(letters='AEGINRT', center='R'))"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def top_honeycomb3_annotated(words) -> Tuple[int, Honeycomb]: \n",
    "    \"\"\"Return a (score, honeycomb) tuple with a highest-scoring honeycomb. Print stuff.\"\"\"\n",
    "    points_table = tabulate_points(words)\n",
    "    top_score, top = -1, None\n",
    "    pangrams = [s for s in points_table if len(s) == 7]\n",
    "    COUNT = 0\n",
    "    for i, p in enumerate(pangrams, 1):\n",
    "        if game_score2(Honeycomb(p, ''), points_table) > top_score:\n",
    "            COUNT +=1; \n",
    "            print(f'{p} scores {game_score2(Honeycomb(p, \"\"), points_table):4}',\n",
    "                  f'with center ∅ (pangram {COUNT:2} ({i}/{len(pangrams)}))')\n",
    "            for center in p:\n",
    "                honeycomb = Honeycomb(p, center)\n",
    "                score = game_score2(honeycomb, points_table)\n",
    "                if score > top_score:\n",
    "                    top_score, top = score, honeycomb\n",
    "                    print(f'{\" \":8}scores {top_score:4} with center {top.center} ')\n",
    "    return top_score, top\n",
    "\n",
    "top_honeycomb3_annotated(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Only 14 pangram lettersets had to have all 7 centers checked. We were lucky that the 4th pangram out of 7986, ABDEORT, happened to be aa good one, scoring 2134 points (with center E), setting a high score so that most of the remaining pangrams only needed to be checked with an empty center. The total number of calls to `game_score2` is:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8084"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(pangram_lettersets(enable1)) + 14 * 7"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "8,084 is a big improvement over 55,902.\n",
    "\n",
    "# 9: Fancy Report\n",
    "\n",
    "I'd like to see the actual words that each honeycomb can make, and I'm curious about how the words are divided up by letterset. Here's a function to provide such a report. I remembered that there is a `fill` function in Python (it is in the `textwrap` module) but this turned out to be a lot more complicated than I expected. I guess it is difficult to create a practical extraction and reporting tool. I feel you, [Larry Wall](http://www.wall.org/~larry/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "from textwrap import fill\n",
    "\n",
    "def report(honeycomb=None, words=enable1):\n",
    "    \"\"\"Print stats, words, and word scores for the given honeycomb (or the top\n",
    "    honeycomb if no honeycomb is given) over the given word list.\"\"\"\n",
    "    bins    = group_by(words, key=letterset)\n",
    "    if honeycomb is None:\n",
    "        adj = \"Top \"\n",
    "        score, honeycomb = top_honeycomb3(words)\n",
    "    else:\n",
    "        adj = \"\"\n",
    "        score = game_score(honeycomb, words)\n",
    "    subsets = letter_subsets(honeycomb)\n",
    "    nwords  = sum(len(bins[s]) for s in subsets)\n",
    "    print(f'{adj}{honeycomb} scores {Ns(score, \"point\")} on {Ns(nwords, \"word\")}',\n",
    "          f'from a {len(words)} word list:\\n')\n",
    "    for s in sorted(subsets, key=lambda s: (-len(s), s)):\n",
    "        if bins[s]:\n",
    "            pts = sum(word_score(w) for w in bins[s])\n",
    "            wcount = Ns(len(bins[s]), \"pangram\" if is_pangram(s) else \"word\")\n",
    "            intro = f'{s:>7} {Ns(pts, \"point\"):>10} {wcount:>8} '\n",
    "            words = [f'{w}({word_score(w)})' for w in sorted(bins[s])]\n",
    "            print(fill(' '.join(words), width=110, \n",
    "                       initial_indent=intro, subsequent_indent=' '*8))\n",
    "            \n",
    "def Ns(n, noun):\n",
    "    \"\"\"A string with `n` followed by the plural or singular of noun:\n",
    "    Ns(3, 'bear') => '3 bears'; Ns(1, 'world') => '1 world'\"\"\"  \n",
    "    return f\"{n:d} {noun}{' ' if n == 1 else 's'}\"\n",
    "\n",
    "def group_by(items, key):\n",
    "    \"Group items into bins of a dict, each bin keyed by key(item).\"\n",
    "    bins = defaultdict(list)\n",
    "    for item in items:\n",
    "        bins[key(item)].append(item)\n",
    "    return bins"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Honeycomb(letters='AEGLMPX', center='G') scores 24 points on 4 words from a 6 word list:\n",
      "\n",
      "AEGLMPX  15 points 1 pangram  MEGAPLEX(15)\n",
      "   AEGM   1 point   1 word  GAME(1)\n",
      "   AGLM   8 points  2 words AMALGAM(7) GLAM(1)\n"
     ]
    }
   ],
   "source": [
    "report(Honeycomb('AEGLMPX', 'G'), mini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top Honeycomb(letters='AEGINRT', center='R') scores 3898 points on 537 words from a 44585 word list:\n",
      "\n",
      "AEGINRT 832 points 50 pangrams AERATING(15) AGGREGATING(18) ARGENTINE(16) ARGENTITE(16) ENTERTAINING(19)\n",
      "        ENTRAINING(17) ENTREATING(17) GARNIERITE(17) GARTERING(16) GENERATING(17) GNATTIER(15) GRANITE(14)\n",
      "        GRATINE(14) GRATINEE(15) GRATINEEING(18) GREATENING(17) INGRATE(14) INGRATIATE(17) INTEGRATE(16)\n",
      "        INTEGRATING(18) INTENERATING(19) INTERAGE(15) INTERGANG(16) INTERREGNA(17) INTREATING(17)\n",
      "        ITERATING(16) ITINERATING(18) NATTERING(16) RATTENING(16) REAGGREGATING(20) REATTAINING(18)\n",
      "        REGENERATING(19) REGRANTING(17) REGRATING(16) REINITIATING(19) REINTEGRATE(18) REINTEGRATING(20)\n",
      "        REITERATING(18) RETAGGING(16) RETAINING(16) RETARGETING(18) RETEARING(16) RETRAINING(17)\n",
      "        RETREATING(17) TANGERINE(16) TANGIER(14) TARGETING(16) TATTERING(16) TEARING(14) TREATING(15)\n",
      " AEGINR 270 points 35 words AGINNER(7) AGREEING(8) ANEARING(8) ANERGIA(7) ANGERING(8) ANGRIER(7) ARGININE(8)\n",
      "        EARING(6) EARNING(7) EARRING(7) ENGRAIN(7) ENGRAINING(10) ENRAGING(8) GAINER(6) GANGRENING(10)\n",
      "        GARNERING(9) GEARING(7) GRAINER(7) GRAINIER(8) GRANNIE(7) GREGARINE(9) NAGGIER(7) NEARING(7)\n",
      "        RANGIER(7) REAGIN(6) REARING(7) REARRANGING(11) REEARNING(9) REENGAGING(10) REGAIN(6) REGAINER(8)\n",
      "        REGAINING(9) REGEARING(9) REGINA(6) REGINAE(7)\n",
      " AEGIRT  34 points  5 words AIGRET(6) AIGRETTE(8) GAITER(6) IRRIGATE(8) TRIAGE(6)\n",
      " AEGNRT  94 points 13 words ARGENT(6) GARNET(6) GENERATE(8) GRANTEE(7) GRANTER(7) GREATEN(7) NEGATER(7)\n",
      "        REAGENT(7) REGENERATE(10) REGNANT(7) REGRANT(7) TANAGER(7) TEENAGER(8)\n",
      " AEINRT 232 points 30 words ARENITE(7) ATTAINER(8) ENTERTAIN(9) ENTERTAINER(11) ENTRAIN(7) ENTRAINER(9)\n",
      "        INERRANT(8) INERTIA(7) INERTIAE(8) INTENERATE(10) INTREAT(7) ITERANT(7) ITINERANT(9) ITINERATE(9)\n",
      "        NATTIER(7) NITRATE(7) RATINE(6) REATTAIN(8) REINITIATE(10) RETAIN(6) RETAINER(8) RETINA(6) RETINAE(7)\n",
      "        RETIRANT(8) RETRAIN(7) TERRAIN(7) TERTIAN(7) TRAINEE(7) TRAINER(7) TRIENNIA(8)\n",
      " AGINRT 167 points 21 words AIRTING(7) ATTIRING(8) GRANITA(7) GRANTING(8) GRATIN(6) GRATING(7)\n",
      "        INGRATIATING(12) INTRIGANT(9) IRRIGATING(10) IRRITATING(10) NARRATING(9) NITRATING(9) RANTING(7)\n",
      "        RATING(6) RATTING(7) TARING(6) TARRING(7) TARTING(7) TITRATING(9) TRAINING(8) TRIAGING(8)\n",
      " EGINRT 218 points 26 words ENGIRT(6) ENTERING(8) GETTERING(9) GITTERN(7) GREETING(8) IGNITER(7) INTEGER(7)\n",
      "        INTERNING(9) INTERRING(9) REENTERING(10) REGREETING(10) REGRETTING(10) REIGNITE(8) REIGNITING(10)\n",
      "        REINTERRING(11) RENTING(7) RETINTING(9) RETIRING(8) RETTING(7) RINGENT(7) TEETERING(9) TENTERING(9)\n",
      "        TIERING(7) TITTERING(9) TREEING(7) TRIGGERING(10)\n",
      "  AEGNR 120 points 18 words ANGER(5) ARRANGE(7) ARRANGER(8) ENGAGER(7) ENRAGE(6) GANGER(6) GANGRENE(8)\n",
      "        GARNER(6) GENERA(6) GRANGE(6) GRANGER(7) GREENGAGE(9) NAGGER(6) RANGE(5) RANGER(6) REARRANGE(9)\n",
      "        REENGAGE(8) REGNA(5)\n",
      "  AEGRT 123 points 19 words AGGREGATE(9) ERGATE(6) ETAGERE(7) GARGET(6) GARRET(6) GARTER(6) GRATE(5) GRATER(6)\n",
      "        GREAT(5) GREATER(7) REAGGREGATE(11) REGATTA(7) REGRATE(7) RETAG(5) RETARGET(8) TAGGER(6) TARGE(5)\n",
      "        TARGET(6) TERGA(5)\n",
      "  AEINR  19 points  3 words INANER(6) NARINE(6) RAINIER(7)\n",
      "  AEIRT 135 points 20 words ARIETTA(7) ARIETTE(7) ARTIER(6) ATTIRE(6) ATTRITE(7) IRATE(5) IRATER(6)\n",
      "        IRRITATE(8) ITERATE(7) RATITE(6) RATTIER(7) REITERATE(9) RETIA(5) RETIARII(8) TARRIER(7) TATTIER(7)\n",
      "        TEARIER(7) TERAI(5) TERRARIA(8) TITRATE(7)\n",
      "  AENRT 132 points 19 words ANTEATER(8) ANTRE(5) ENTERA(6) ENTRANT(7) ENTREAT(7) ERRANT(6) NARRATE(7)\n",
      "        NARRATER(8) NATTER(6) NEATER(6) RANTER(6) RATTEEN(7) RATTEN(6) RATTENER(8) REENTRANT(9) RETREATANT(10)\n",
      "        TANNER(6) TERNATE(7) TERRANE(7)\n",
      "  AGINR 138 points 19 words AGRARIAN(8) AIRING(6) ANGARIA(7) ARRAIGN(7) ARRAIGNING(10) ARRANGING(9)\n",
      "        GARAGING(8) GARNI(5) GARRING(7) GNARRING(8) GRAIN(5) GRAINING(8) INGRAIN(7) INGRAINING(10) RAGGING(7)\n",
      "        RAGING(6) RAINING(7) RANGING(7) RARING(6)\n",
      "  AGIRT   5 points  1 word  TRAGI(5)\n",
      "  AGNRT   5 points  1 word  GRANT(5)\n",
      "  AINRT  64 points  9 words ANTIAIR(7) ANTIAR(6) ANTIARIN(8) INTRANT(7) IRRITANT(8) RIANT(5) TITRANT(7)\n",
      "        TRAIN(5) TRINITARIAN(11)\n",
      "  EGINR 186 points 24 words ENGINEER(8) ENGINEERING(11) ERRING(6) GINGER(6) GINGERING(9) GINNER(6) GINNIER(7)\n",
      "        GREEING(7) GREENIE(7) GREENIER(8) GREENING(8) GRINNER(7) NIGGER(6) REENGINEER(10) REENGINEERING(13)\n",
      "        REGREENING(10) REIGN(5) REIGNING(8) REINING(7) RENEGING(8) RENIG(5) RENIGGING(9) RERIGGING(9)\n",
      "        RINGER(6)\n",
      "  EGIRT  27 points  4 words GRITTIER(8) TERGITE(7) TIGER(5) TRIGGER(7)\n",
      "  EGNRT  12 points  2 words GERENT(6) REGENT(6)\n",
      "  EINRT 190 points 29 words ENTIRE(6) INERT(5) INTER(5) INTERN(6) INTERNE(7) INTERNEE(8) INTERTIE(8)\n",
      "        NETTIER(7) NITER(5) NITERIE(7) NITRE(5) NITRITE(7) NITTIER(7) REINTER(7) RENITENT(8) RENTIER(7)\n",
      "        RETINE(6) RETINENE(8) RETINITE(8) RETINT(6) TEENIER(7) TENTIER(7) TERRINE(7) TINIER(6) TINNER(6)\n",
      "        TINNIER(7) TINTER(6) TRIENE(6) TRINE(5)\n",
      "  GINRT  43 points  6 words GIRTING(7) GRITTING(8) RINGGIT(7) TIRING(6) TRIGGING(8) TRINING(7)\n",
      "   AEGR  84 points 17 words AGER(1) AGGER(5) AGREE(5) ARREARAGE(9) EAGER(5) EAGERER(7) EAGRE(5) EGGAR(5)\n",
      "        GAGER(5) GAGGER(6) GARAGE(6) GEAR(1) RAGE(1) RAGEE(5) RAGGEE(6) REGEAR(6) REGGAE(6)\n",
      "   AEIR  22 points  4 words AERIE(5) AERIER(6) AIRER(5) AIRIER(6)\n",
      "   AENR  40 points  9 words ANEAR(5) ARENA(5) EARN(1) EARNER(6) NEAR(1) NEARER(6) RANEE(5) REEARN(6) RERAN(5)\n",
      "   AERT 127 points 24 words AERATE(6) ARETE(5) EATER(5) ERRATA(6) RATE(1) RATER(5) RATTER(6) REATA(5)\n",
      "        RETEAR(6) RETREAT(7) RETREATER(9) TARE(1) TARRE(5) TARTER(6) TARTRATE(8) TATER(5) TATTER(6) TEAR(1)\n",
      "        TEARER(6) TERRA(5) TERRAE(6) TETRA(5) TREAT(5) TREATER(7)\n",
      "   AGIR   6 points  2 words AGRIA(5) RAGI(1)\n",
      "   AGNR  13 points  5 words GNAR(1) GNARR(5) GRAN(1) GRANA(5) RANG(1)\n",
      "   AGRT  13 points  3 words GRAT(1) RAGTAG(6) TAGRAG(6)\n",
      "   AINR   8 points  4 words AIRN(1) NAIRA(5) RAIN(1) RANI(1)\n",
      "   AIRT  21 points  5 words AIRT(1) ATRIA(5) RIATA(5) TIARA(5) TRAIT(5)\n",
      "   ANRT  50 points 10 words ANTRA(5) ARRANT(6) RANT(1) RATAN(5) RATTAN(6) TANTARA(7) TANTRA(6) TARN(1)\n",
      "        TARTAN(6) TARTANA(7)\n",
      "   EGIR  17 points  3 words GREIGE(6) RERIG(5) RIGGER(6)\n",
      "   EGNR  37 points  6 words GENRE(5) GREEN(5) GREENER(7) REGREEN(7) RENEGE(6) RENEGER(7)\n",
      "   EGRT  45 points  7 words EGRET(5) GETTER(6) GREET(5) GREETER(7) REGREET(7) REGRET(6) REGRETTER(9)\n",
      "   EINR  17 points  4 words INNER(5) REIN(1) RENIN(5) RENNIN(6)\n",
      "   EIRT  87 points 17 words RETIE(5) RETIRE(6) RETIREE(7) RETIRER(7) RITE(1) RITTER(6) TERRIER(7) TERRIT(6)\n",
      "        TIER(1) TIRE(1) TITER(5) TITRE(5) TITTER(6) TITTERER(8) TRIER(5) TRITE(5) TRITER(6)\n",
      "   ENRT 104 points 19 words ENTER(5) ENTERER(7) ENTREE(6) ETERNE(6) NETTER(6) REENTER(7) RENNET(6) RENT(1)\n",
      "        RENTE(5) RENTER(6) RETENE(6) TEENER(6) TENNER(6) TENTER(6) TERN(1) TERNE(5) TERREEN(7) TERRENE(7)\n",
      "        TREEN(5)\n",
      "   GINR  44 points  9 words GIRN(1) GIRNING(7) GRIN(1) GRINNING(8) IRING(5) RIGGING(7) RING(1) RINGING(7)\n",
      "        RINNING(7)\n",
      "   GIRT   3 points  3 words GIRT(1) GRIT(1) TRIG(1)\n",
      "    AER  25 points  7 words AREA(1) AREAE(5) ARREAR(6) RARE(1) RARER(5) REAR(1) REARER(6)\n",
      "    AGR   2 points  2 words AGAR(1) RAGA(1)\n",
      "    AIR   2 points  2 words ARIA(1) RAIA(1)\n",
      "    ART  24 points  5 words ATTAR(5) RATATAT(7) TART(1) TARTAR(6) TATAR(5)\n",
      "    EGR  15 points  4 words EGER(1) EGGER(5) GREE(1) GREEGREE(8)\n",
      "    EIR  11 points  2 words EERIE(5) EERIER(6)\n",
      "    ENR   1 point   1 word  ERNE(1)\n",
      "    ERT  27 points  7 words RETE(1) TEETER(6) TERETE(6) TERRET(6) TETTER(6) TREE(1) TRET(1)\n",
      "    GIR   7 points  2 words GRIG(1) GRIGRI(6)\n"
     ]
    }
   ],
   "source": [
    "report(words=enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 10: 'S' Words\n",
    "\n",
    "What if we allowed honeycombs and words to have an 'S' in them? I'll make a new word list, and report on it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top Honeycomb(letters='AEINRST', center='E') scores 8681 points on 1179 words from a 98141 word list:\n",
      "\n",
      "AEINRST 1381 points 86 pangrams ANESTRI(14) ANTISERA(15) ANTISTRESS(17) ANTSIER(14) ARENITES(15) ARSENITE(15)\n",
      "        ARSENITES(16) ARTINESS(15) ARTINESSES(17) ATTAINERS(16) ENTERTAINERS(19) ENTERTAINS(17) ENTRAINERS(17)\n",
      "        ENTRAINS(15) ENTREATIES(17) ERRANTRIES(17) INERTIAS(15) INSTANTER(16) INTENERATES(18) INTERSTATE(17)\n",
      "        INTERSTATES(18) INTERSTRAIN(18) INTERSTRAINS(19) INTRASTATE(17) INTREATS(15) IRATENESS(16)\n",
      "        IRATENESSES(18) ITINERANTS(17) ITINERARIES(18) ITINERATES(17) NASTIER(14) NITRATES(15) RAINIEST(15)\n",
      "        RATANIES(15) RATINES(14) REATTAINS(16) REINITIATES(18) REINSTATE(16) REINSTATES(17) RESINATE(15)\n",
      "        RESINATES(16) RESISTANT(16) RESISTANTS(17) RESTRAIN(15) RESTRAINER(17) RESTRAINERS(18) RESTRAINS(16)\n",
      "        RESTRAINT(16) RESTRAINTS(17) RETAINERS(16) RETAINS(14) RETINAS(14) RETIRANTS(16) RETRAINS(15)\n",
      "        RETSINA(14) RETSINAS(15) SANITARIES(17) SEATRAIN(15) SEATRAINS(16) STAINER(14) STAINERS(15)\n",
      "        STANNARIES(17) STEARIN(14) STEARINE(15) STEARINES(16) STEARINS(15) STRAINER(15) STRAINERS(16)\n",
      "        STRAITEN(15) STRAITENS(16) STRAITNESS(17) STRAITNESSES(19) TANISTRIES(17) TANNERIES(16) TEARSTAIN(16)\n",
      "        TEARSTAINS(17) TENANTRIES(17) TERNARIES(16) TERRAINS(15) TERTIANS(15) TRAINEES(15) TRAINERS(15)\n",
      "        TRANSIENT(16) TRANSIENTS(17) TRISTEARIN(17) TRISTEARINS(18)\n",
      " AEINRS 124 points 16 words AIRINESS(8) AIRINESSES(10) ANSERINE(8) ANSERINES(9) ARISEN(6) ARSINE(6) ARSINES(7)\n",
      "        INSANER(7) INSNARE(7) INSNARER(8) INSNARERS(9) INSNARES(8) SENARII(7) SIERRAN(7) SIRENIAN(8)\n",
      "        SIRENIANS(9)\n",
      " AEINRT 232 points 30 words ARENITE(7) ATTAINER(8) ENTERTAIN(9) ENTERTAINER(11) ENTRAIN(7) ENTRAINER(9)\n",
      "        INERRANT(8) INERTIA(7) INERTIAE(8) INTENERATE(10) INTREAT(7) ITERANT(7) ITINERANT(9) ITINERATE(9)\n",
      "        NATTIER(7) NITRATE(7) RATINE(6) REATTAIN(8) REINITIATE(10) RETAIN(6) RETAINER(8) RETINA(6) RETINAE(7)\n",
      "        RETIRANT(8) RETRAIN(7) TERRAIN(7) TERTIAN(7) TRAINEE(7) TRAINER(7) TRIENNIA(8)\n",
      " AEINST 713 points 80 words ANISETTE(8) ANISETTES(9) ANTISENSE(9) ANTISTATE(9) ANTSIEST(8) ASININITIES(11)\n",
      "        ASSASSINATE(11) ASSASSINATES(12) ASTATINE(8) ASTATINES(9) ENTASIA(7) ENTASIAS(8) ENTASIS(7) ETESIAN(7)\n",
      "        ETESIANS(8) INANEST(7) INANITIES(9) INITIATES(9) INNATENESS(10) INNATENESSES(12) INSANEST(8)\n",
      "        INSANITIES(10) INSATIATE(9) INSATIATENESS(13) INSATIATENESSES(15) INSENSATE(9) INSTANTANEITIES(15)\n",
      "        INSTANTIATE(11) INSTANTIATES(12) INSTANTNESS(11) INSTANTNESSES(13) INSTATE(7) INSTATES(8) INTESTATE(9)\n",
      "        INTESTATES(10) ISATINE(7) ISATINES(8) NASTIES(7) NASTIEST(8) NASTINESS(9) NASTINESSES(11) NATTIEST(8)\n",
      "        NATTINESS(9) NATTINESSES(11) SANITATE(8) SANITATES(9) SANITIES(8) SANITISE(8) SANITISES(9) SATINET(7)\n",
      "        SATINETS(8) SENTENTIA(9) SENTENTIAE(10) SESTINA(7) SESTINAS(8) STANINE(7) STANINES(8) STANNITE(8)\n",
      "        STANNITES(9) TAENIAS(7) TAENIASES(9) TAENIASIS(9) TANSIES(7) TASTINESS(9) TASTINESSES(11) TATTINESS(9)\n",
      "        TATTINESSES(11) TENIAS(6) TENIASES(8) TENIASIS(8) TETANIES(8) TETANISE(8) TETANISES(9) TINEAS(6)\n",
      "        TISANE(6) TISANES(7) TITANATES(9) TITANESS(8) TITANESSES(10) TITANITES(9)\n",
      " AEIRST 473 points 60 words AERIEST(7) AIREST(6) AIRIEST(7) ARIETTAS(8) ARIETTES(8) ARISTAE(7) ARISTATE(8)\n",
      "        ARTERIES(8) ARTERITIS(9) ARTIEST(7) ARTISTE(7) ARTISTES(8) ARTISTRIES(10) ARTSIER(7) ARTSIEST(8)\n",
      "        ASSISTER(8) ASSISTERS(9) ASTERIA(7) ASTERIAS(8) ATRESIA(7) ATRESIAS(8) ATTIRES(7) EATERIES(8)\n",
      "        IRATEST(7) IRRITATES(9) ITERATES(8) RARITIES(8) RATITES(7) RATTIEST(8) REITERATES(10) SATIRE(6)\n",
      "        SATIRES(7) SATIRISE(8) SATIRISES(9) SERIATE(7) SERIATES(8) SESTERTIA(9) STARRIER(8) STARRIEST(9)\n",
      "        STRAITER(8) STRAITEST(9) STRIAE(6) STRIATE(7) STRIATES(8) TARRIERS(8) TARRIES(7) TARRIEST(8)\n",
      "        TARSIER(7) TARSIERS(8) TASTIER(7) TEARIEST(8) TERAIS(6) TERTIARIES(10) TITRATES(8) TRAITRESS(9)\n",
      "        TRAITRESSES(11) TREATIES(8) TREATISE(8) TREATISES(9) TRISTATE(8)\n",
      " AENRST 336 points 40 words ANTEATERS(9) ANTRES(6) ARRESTANT(9) ARRESTANTS(10) ARSENATE(8) ARSENATES(9)\n",
      "        ASSENTER(8) ASSENTERS(9) ASTERN(6) EARNEST(7) EARNESTNESS(11) EARNESTNESSES(13) EARNESTS(8) EASTERN(7)\n",
      "        EASTERNER(9) EASTERNERS(10) ENTRANTS(8) ENTREATS(8) ERRANTS(7) NARRATERS(9) NARRATES(8) NATTERS(7)\n",
      "        NEAREST(7) RANTERS(7) RATTEENS(8) RATTENERS(9) RATTENS(7) REENTRANTS(10) RETREATANTS(11) SARSENET(8)\n",
      "        SARSENETS(9) SERENATA(8) SERENATAS(9) SERENATE(8) STERNA(6) TANNERS(7) TARANTASES(10) TARTNESS(8)\n",
      "        TARTNESSES(10) TERRANES(8)\n",
      " EINRST 582 points 70 words ENTERITIS(9) ENTERITISES(11) ENTIRENESS(10) ENTIRENESSES(12) ENTIRES(7)\n",
      "        ENTIRETIES(10) ENTRIES(7) ESTRIN(6) ESTRINS(7) ETERNISE(8) ETERNISES(9) ETERNITIES(10) INERTNESS(9)\n",
      "        INERTNESSES(11) INERTS(6) INSERT(6) INSERTER(8) INSERTERS(9) INSERTS(7) INSETTER(8) INSETTERS(9)\n",
      "        INSISTER(8) INSISTERS(9) INTENSER(8) INTEREST(8) INTERESTS(9) INTERNEES(9) INTERNES(8) INTERNIST(9)\n",
      "        INTERNISTS(10) INTERNS(7) INTERS(6) INTERTIES(9) NITERIES(8) NITERS(6) NITRES(6) NITRITES(8)\n",
      "        REENTRIES(9) REINSERT(8) REINSERTS(9) REINTERS(8) RENTIERS(8) RETINENES(9) RETINES(7) RETINITES(9)\n",
      "        RETINITIS(9) RETINTS(7) SENTRIES(8) SERENITIES(10) SINISTER(8) SINISTERNESS(12) SINISTERNESSES(14)\n",
      "        SINTER(6) SINTERS(7) STERNITE(8) STERNITES(9) STINTER(7) STINTERS(8) TEENSIER(8) TEENTSIER(9)\n",
      "        TERRINES(8) TINNERS(7) TINTERS(7) TRIENES(7) TRIENS(6) TRIENTES(8) TRINES(6) TRINITIES(9) TRITENESS(9)\n",
      "        TRITENESSES(11)\n",
      "  AEINR  19 points  3 words INANER(6) NARINE(6) RAINIER(7)\n",
      "  AEINS 129 points 17 words ANISE(5) ANISES(6) ASININE(7) EASINESS(8) EASINESSES(10) INANENESS(9)\n",
      "        INANENESSES(11) INANES(6) INSANE(6) INSANENESS(10) INSANENESSES(12) NANNIES(7) SANIES(6) SANSEI(6)\n",
      "        SANSEIS(7) SIENNA(6) SIENNAS(7)\n",
      "  AEINT  64 points 10 words ENTIA(5) INITIATE(8) INNATE(6) TAENIA(6) TAENIAE(7) TENIA(5) TENIAE(6) TINEA(5)\n",
      "        TITANATE(8) TITANITE(8)\n",
      "  AEIRS 106 points 17 words AERIES(6) AIRERS(6) ARISE(5) ARISES(6) ARRISES(7) EASIER(6) RAISE(5) RAISER(6)\n",
      "        RAISERS(7) RAISES(6) RERAISE(7) RERAISES(8) SASSIER(7) SERAI(5) SERAIS(6) SIERRA(6) SIERRAS(7)\n",
      "  AEIRT 135 points 20 words ARIETTA(7) ARIETTE(7) ARTIER(6) ATTIRE(6) ATTRITE(7) IRATE(5) IRATER(6)\n",
      "        IRRITATE(8) ITERATE(7) RATITE(6) RATTIER(7) REITERATE(9) RETIA(5) RETIARII(8) TARRIER(7) TATTIER(7)\n",
      "        TEARIER(7) TERAI(5) TERRARIA(8) TITRATE(7)\n",
      "  AEIST 112 points 15 words EASIEST(7) ETATIST(7) SASSIEST(8) SATIATE(7) SATIATES(8) SATIETIES(9) SIESTA(6)\n",
      "        SIESTAS(7) STEATITE(8) STEATITES(9) TASSIE(6) TASSIES(7) TASTIEST(8) TATTIES(7) TATTIEST(8)\n",
      "  AENRS 172 points 25 words ANEARS(6) ARENAS(6) EARNERS(7) EARNS(5) ENSNARE(7) ENSNARER(8) ENSNARERS(9)\n",
      "        ENSNARES(8) NARES(5) NEARNESS(8) NEARNESSES(10) NEARS(5) RANEES(6) RARENESS(8) RARENESSES(10)\n",
      "        REEARNS(7) RENNASE(7) RENNASES(8) SANER(5) SARSEN(6) SARSENS(7) SNARE(5) SNARER(6) SNARERS(7)\n",
      "        SNARES(6)\n",
      "  AENRT 132 points 19 words ANTEATER(8) ANTRE(5) ENTERA(6) ENTRANT(7) ENTREAT(7) ERRANT(6) NARRATE(7)\n",
      "        NARRATER(8) NATTER(6) NEATER(6) RANTER(6) RATTEEN(7) RATTEN(6) RATTENER(8) REENTRANT(9) RETREATANT(10)\n",
      "        TANNER(6) TERNATE(7) TERRANE(7)\n",
      "  AENST 217 points 32 words ANATASE(7) ANATASES(8) ANENST(6) ANNATES(7) ANSATE(6) ANTENNAS(8) ANTES(5)\n",
      "        ASSENT(6) ASSENTS(7) ENATES(6) ENTASES(7) ETNAS(5) NATES(5) NEATENS(7) NEATEST(7) NEATNESS(8)\n",
      "        NEATNESSES(10) NEATS(5) SANEST(6) SATEEN(6) SATEENS(7) SENATE(6) SENATES(7) SENSATE(7) SENSATES(8)\n",
      "        SETENANT(8) SETENANTS(9) STANE(5) STANES(6) TANNATES(8) TANNEST(7) TENANTS(7)\n",
      "  AERST 604 points 85 words AERATES(7) ARETES(6) ARREST(6) ARRESTEE(8) ARRESTEES(9) ARRESTER(8) ARRESTERS(9)\n",
      "        ARRESTS(7) ASSERT(6) ASSERTER(8) ASSERTERS(9) ASSERTS(7) ASTER(5) ASTERS(6) ATTESTER(8) ATTESTERS(9)\n",
      "        EASTER(6) EASTERS(7) EATERS(6) ERRATAS(7) ESTERASE(8) ESTERASES(9) ESTREAT(7) ESTREATS(8) RAREST(6)\n",
      "        RASTER(6) RASTERS(7) RATERS(6) RATES(5) RATTERS(7) REARREST(8) REARRESTS(9) REASSERT(8) REASSERTS(9)\n",
      "        REATAS(6) RESEAT(6) RESEATS(7) RESTART(7) RESTARTS(8) RESTATE(7) RESTATES(8) RETASTE(7) RETASTES(8)\n",
      "        RETEARS(7) RETREATERS(10) RETREATS(8) SEAREST(7) SEATER(6) SEATERS(7) SERRATE(7) SERRATES(8) STARE(5)\n",
      "        STARER(6) STARERS(7) STARES(6) STARETS(7) STARTER(7) STARTERS(8) STATER(6) STATERS(7) STEARATE(8)\n",
      "        STEARATES(9) STRASSES(8) STRETTA(7) STRETTAS(8) TARES(5) TARRES(6) TARTEST(7) TARTRATES(9) TASTER(6)\n",
      "        TASTERS(7) TATERS(6) TATTERS(7) TEARERS(7) TEARS(5) TEASER(6) TEASERS(7) TERRAS(6) TERRASES(8)\n",
      "        TESSERA(7) TESSERAE(8) TETRAS(6) TRASSES(7) TREATERS(8) TREATS(6)\n",
      "  EINRS 184 points 29 words EERINESS(8) EERINESSES(10) ESERINE(7) ESERINES(8) INNERS(6) NEREIS(6) REINS(5)\n",
      "        RENINS(6) RENNINS(7) RERISEN(7) RESIN(5) RESINS(6) RINSE(5) RINSER(6) RINSERS(7) RINSES(6) RISEN(5)\n",
      "        SEINER(6) SEINERS(7) SEREIN(6) SEREINS(7) SERIN(5) SERINE(6) SERINES(7) SERINS(6) SINNER(6) SINNERS(7)\n",
      "        SIREN(5) SIRENS(6)\n",
      "  EINRT 190 points 29 words ENTIRE(6) INERT(5) INTER(5) INTERN(6) INTERNE(7) INTERNEE(8) INTERTIE(8)\n",
      "        NETTIER(7) NITER(5) NITERIE(7) NITRE(5) NITRITE(7) NITTIER(7) REINTER(7) RENITENT(8) RENTIER(7)\n",
      "        RETINE(6) RETINENE(8) RETINITE(8) RETINT(6) TEENIER(7) TENTIER(7) TERRINE(7) TINIER(6) TINNER(6)\n",
      "        TINNIER(7) TINTER(6) TRIENE(6) TRINE(5)\n",
      "  EINST 469 points 58 words EINSTEIN(8) EINSTEINS(9) ENTITIES(8) INSENTIENT(10) INSET(5) INSETS(6)\n",
      "        INSISTENT(9) INTENSE(7) INTENSENESS(11) INTENSENESSES(13) INTENSEST(9) INTENSITIES(11) INTENTNESS(10)\n",
      "        INTENTNESSES(12) INTENTS(7) INTESTINE(9) INTESTINES(10) INTINES(7) NEIST(5) NETTIEST(8) NINETEENS(9)\n",
      "        NINETIES(8) NITES(5) NITTIEST(8) SENITI(6) SENNIT(6) SENNITS(7) SENSITISE(9) SENSITISES(10) SENTI(5)\n",
      "        SENTIENT(8) SENTIENTS(9) SESTINE(7) SESTINES(8) SIENITE(7) SIENITES(8) SITTEN(6) STEIN(5) STEINS(6)\n",
      "        TEENIEST(8) TEENSIEST(9) TEENTSIEST(10) TENNIES(7) TENNIS(6) TENNISES(8) TENNIST(7) TENNISTS(8)\n",
      "        TENSITIES(9) TENTIEST(8) TESTINESS(9) TESTINESSES(11) TINES(5) TINIEST(7) TININESS(8) TININESSES(10)\n",
      "        TINNIEST(8) TINNINESS(9) TINNINESSES(11)\n",
      "  EIRST 262 points 38 words EERIEST(7) IRITISES(8) RESIST(6) RESISTER(8) RESISTERS(9) RESISTS(7) RESITE(6)\n",
      "        RESITES(7) RETIES(6) RETIREES(8) RETIRERS(8) RETIRES(7) RETRIES(7) RITES(5) RITTERS(7) SISTER(6)\n",
      "        SISTERS(7) SITTER(6) SITTERS(7) STIRRER(7) STIRRERS(8) STRETTI(7) TERRIERS(8) TERRIES(7) TERRITS(7)\n",
      "        TESTIER(7) TIERS(5) TIRES(5) TITERS(6) TITRES(6) TITTERERS(9) TITTERS(7) TRESSIER(8) TRESSIEST(9)\n",
      "        TRIERS(6) TRIES(5) TRISTE(6) TRITEST(7)\n",
      "  ENRST 246 points 35 words ENTERERS(8) ENTERS(6) ENTREES(7) NERTS(5) NESTER(6) NESTERS(7) NETTERS(7)\n",
      "        REENTERS(8) RENEST(6) RENESTS(7) RENNETS(7) RENTERS(7) RENTES(6) RENTS(5) RESENT(6) RESENTS(7)\n",
      "        RETENES(7) SERENEST(8) STERN(5) STERNER(7) STERNEST(8) STERNNESS(9) STERNNESSES(11) STERNS(6)\n",
      "        TEENERS(7) TENNERS(7) TENSER(6) TENTERS(7) TERNES(6) TERNS(5) TERREENS(8) TERRENES(8) TERSENESS(9)\n",
      "        TERSENESSES(11) TREENS(6)\n",
      "   AEIN  11 points  2 words INANE(5) NANNIE(6)\n",
      "   AEIR  22 points  4 words AERIE(5) AERIER(6) AIRER(5) AIRIER(6)\n",
      "   AEIS  13 points  2 words EASIES(6) SASSIES(7)\n",
      "   AEIT   6 points  1 word  TATTIE(6)\n",
      "   AENR  40 points  9 words ANEAR(5) ARENA(5) EARN(1) EARNER(6) NEAR(1) NEARER(6) RANEE(5) REEARN(6) RERAN(5)\n",
      "   AENS  46 points  9 words ANES(1) ANSAE(5) SANE(1) SANENESS(8) SANENESSES(10) SANES(5) SENNA(5) SENNAS(6)\n",
      "        SENSA(5)\n",
      "   AENT  63 points 13 words ANENT(5) ANTAE(5) ANTE(1) ANTENNA(7) ANTENNAE(8) ATTENT(6) EATEN(5) ENATE(5)\n",
      "        ETNA(1) NEAT(1) NEATEN(6) TANNATE(7) TENANT(6)\n",
      "   AERS 121 points 26 words AREAS(5) ARES(1) ARREARS(7) ARSE(1) ARSES(5) EARS(1) ERAS(1) ERASE(5) ERASER(6)\n",
      "        ERASERS(7) ERASES(6) RARES(5) RASE(1) RASER(5) RASERS(6) RASES(5) REARERS(7) REARS(5) REASSESS(8)\n",
      "        REASSESSES(10) SAREE(5) SAREES(6) SEAR(1) SEARER(6) SEARS(5) SERA(1)\n",
      "   AERT 127 points 24 words AERATE(6) ARETE(5) EATER(5) ERRATA(6) RATE(1) RATER(5) RATTER(6) REATA(5)\n",
      "        RETEAR(6) RETREAT(7) RETREATER(9) TARE(1) TARRE(5) TARTER(6) TARTRATE(8) TATER(5) TATTER(6) TEAR(1)\n",
      "        TEARER(6) TERRA(5) TERRAE(6) TETRA(5) TREAT(5) TREATER(7)\n",
      "   AEST 164 points 35 words ASSET(5) ASSETS(6) ATES(1) ATTEST(6) ATTESTS(7) EAST(1) EASTS(5) EATS(1) ESTATE(6)\n",
      "        ESTATES(7) ETAS(1) SATE(1) SATES(5) SEAT(1) SEATS(5) SETA(1) SETAE(5) STASES(6) STATE(5) STATES(6)\n",
      "        TASSE(5) TASSES(6) TASSET(6) TASSETS(7) TASTE(5) TASTES(6) TATES(5) TEAS(1) TEASE(5) TEASES(6)\n",
      "        TEATS(5) TESTA(5) TESTAE(6) TESTATE(7) TESTATES(8)\n",
      "   EINR  17 points  4 words INNER(5) REIN(1) RENIN(5) RENNIN(6)\n",
      "   EINS  53 points 10 words NINES(5) NINNIES(7) NISEI(5) NISEIS(6) SEINE(5) SEINES(6) SEISIN(6) SEISINS(7)\n",
      "        SINE(1) SINES(5)\n",
      "   EINT  28 points  6 words INTENT(6) INTINE(6) NINETEEN(8) NITE(1) TENTIE(6) TINE(1)\n",
      "   EIRS 101 points 20 words IRES(1) IRISES(6) REIS(1) RERISE(6) RERISES(7) RISE(1) RISER(5) RISERS(6) RISES(5)\n",
      "        SEISER(6) SEISERS(7) SERIES(6) SERRIES(7) SIRE(1) SIREE(5) SIREES(6) SIRES(5) SIRREE(6) SIRREES(7)\n",
      "        SISSIER(7)\n",
      "   EIRT  87 points 17 words RETIE(5) RETIRE(6) RETIREE(7) RETIRER(7) RITE(1) RITTER(6) TERRIER(7) TERRIT(6)\n",
      "        TIER(1) TIRE(1) TITER(5) TITRE(5) TITTER(6) TITTERER(8) TRIER(5) TRITE(5) TRITER(6)\n",
      "   EIST  41 points  8 words SISSIEST(8) SITE(1) SITES(5) STIES(5) TESTIEST(8) TESTIS(6) TIES(1) TITTIES(7)\n",
      "   ENRS  80 points 12 words ERNES(5) ERNS(1) RESEEN(6) SERENE(6) SERENENESS(10) SERENENESSES(12) SERENER(7)\n",
      "        SERENES(7) SNEER(5) SNEERER(7) SNEERERS(8) SNEERS(6)\n",
      "   ENRT 104 points 19 words ENTER(5) ENTERER(7) ENTREE(6) ETERNE(6) NETTER(6) REENTER(7) RENNET(6) RENT(1)\n",
      "        RENTE(5) RENTER(6) RETENE(6) TEENER(6) TENNER(6) TENTER(6) TERN(1) TERNE(5) TERREEN(7) TERRENE(7)\n",
      "        TREEN(5)\n",
      "   ENST  94 points 18 words ENTENTES(8) NEST(1) NESTS(5) NETS(1) NETTS(5) SENNET(6) SENNETS(7) SENT(1)\n",
      "        SENTE(5) TEENS(5) TENETS(6) TENS(1) TENSE(5) TENSENESS(9) TENSENESSES(11) TENSES(6) TENSEST(7)\n",
      "        TENTS(5)\n",
      "   ERST 266 points 44 words ERST(1) ESTER(5) ESTERS(6) REEST(5) REESTS(6) RESET(5) RESETS(6) RESETTER(8)\n",
      "        RESETTERS(9) REST(1) RESTER(6) RESTERS(7) RESTRESS(8) RESTRESSES(10) RESTS(5) RETEST(6) RETESTS(7)\n",
      "        RETS(1) SEREST(6) SETTER(6) SETTERS(7) STEER(5) STEERER(7) STEERERS(8) STEERS(6) STERE(5) STERES(6)\n",
      "        STREET(6) STREETS(7) STRESS(6) STRESSES(8) STRETTE(7) TEETERS(7) TERRETS(7) TERSE(5) TERSER(6)\n",
      "        TERSEST(7) TESTER(6) TESTERS(7) TETTERS(7) TREES(5) TRESS(5) TRESSES(7) TRETS(5)\n",
      "    AER  25 points  7 words AREA(1) AREAE(5) ARREAR(6) RARE(1) RARER(5) REAR(1) REARER(6)\n",
      "    AES  33 points  8 words ASEA(1) ASSES(5) ASSESS(6) ASSESSES(8) EASE(1) EASES(5) SASSES(6) SEAS(1)\n",
      "    AET   2 points  2 words TATE(1) TEAT(1)\n",
      "    EIN   1 point   1 word  NINE(1)\n",
      "    EIR  11 points  2 words EERIE(5) EERIER(6)\n",
      "    EIS  35 points  7 words ISSEI(5) ISSEIS(6) SEIS(1) SEISE(5) SEISES(6) SISES(5) SISSIES(7)\n",
      "    EIT   6 points  1 word  TITTIE(6)\n",
      "    ENR   1 point   1 word  ERNE(1)\n",
      "    ENS  20 points  6 words NESS(1) NESSES(6) SEEN(1) SENE(1) SENSE(5) SENSES(6)\n",
      "    ENT  15 points  5 words ENTENTE(7) NETT(1) TEEN(1) TENET(5) TENT(1)\n",
      "    ERS  52 points 13 words ERRS(1) ERSES(5) REES(1) RESEE(5) RESEES(6) SEER(1) SEERESS(7) SEERESSES(9)\n",
      "        SEERS(5) SERE(1) SERER(5) SERES(5) SERS(1)\n",
      "    ERT  27 points  7 words RETE(1) TEETER(6) TERETE(6) TERRET(6) TETTER(6) TREE(1) TRET(1)\n",
      "    EST  79 points 18 words SESTET(6) SESTETS(7) SETS(1) SETT(1) SETTEE(6) SETTEES(7) SETTS(5) STET(1)\n",
      "        STETS(5) TEES(1) TEST(1) TESTEE(6) TESTEES(7) TESTES(6) TESTS(5) TETS(1) TSETSE(6) TSETSES(7)\n",
      "     EN   1 point   1 word  NENE(1)\n",
      "     ES   7 points  3 words ESES(1) ESSES(5) SEES(1)\n"
     ]
    }
   ],
   "source": [
    "enable1s = [w for w in open('enable1.txt').read().upper().split()\n",
    "            if len(w) >= 4 and len(set(w)) <= 7]\n",
    "\n",
    "report(words=enable1s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Allowing 'S' words more than doubles the score!\n",
    "\n",
    "Here are pictures for the highest-scoring honeycombs, with and without an S:\n",
    "\n",
    "<img src=\"http://norvig.com/honeycombs.png\" width=\"350\">\n",
    "<center>\n",
    "   537 words &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1,179 words \n",
    "    <br>50 pangrams  &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 86 pangrams\n",
    "    <br>3,898 points &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 8,681 points\n",
    "    <br>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "This notebook showed how to find the highest-scoring honeycomb. Four ideas led to four approaches:\n",
    "\n",
    "1. **Brute Force Enumeration**: Compute the game score for every possible honeycomb; return the highest-scoring.\n",
    "2. **Pangram Lettersets**: Compute the game score for just the honeycombs that are pangram lettersets (with all possible centers).\n",
    "3. **Points Table**: Precompute the score for each letterset; then for each candidate honeycomb, sum the scores of the 63 letter subsets.\n",
    "4. **Branch and Bound**: Try all 7 centers only for lettersets that score better than the top score so far.\n",
    "\n",
    "These ideas led to substantial improvements (gain) in number of honeycombs processed, `game_score` run time, and total run time:\n",
    "\n",
    "\n",
    "|Approach|Honeycombs|Gain|`game_score` Time|Gain|Total Run Time|Gain|\n",
    "|--------|----------|--------|----|---|---|---|\n",
    "|**1. Brute Force Enumeration**|3,364,900|——|9000 microseconds|——|8.5 hours|——|\n",
    "|**2. Pangram Lettersets**|55,902|60×|9000 microseconds|——|500 seconds|60×|\n",
    "|**3. Points Table**|55,902|60×|25 microseconds|360×|1.6 seconds|20,000×|\n",
    "|**4. Branch and Bound**|8,084 |400×|25 microseconds|360×|0.36 seconds|80,000×|\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}