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 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, seven-letter words are worth 7 points, etc. Words that use all of the 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 15 points.\n",
    ">\n",
    "> ***Which seven-letter honeycomb results in the highest possible game 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, I felt somewhat compelled to solve this one.  (Note I didn't make up the word list; it is a standard Scrabble word list that I happen to host a copy of.) I'll show you how I address the problem, step by step:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 1: Words, Word Scores, and Pangrams\n",
    "\n",
    "Let's start by defining some basics:\n",
    "\n",
    "- A **valid word** is a string of at least 4 letters, with no 'S', and not more than 7 distinct letters.\n",
    "- A **word list** is, well, a list of words.\n",
    "- A **pangram** is a word with exactly 7 distinct letters.\n",
    "- The **word score** is 1 for a four letter word, or the length of the word for longer words, plus a bonus of 7 for a pangram.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing      import List, Set, Tuple, Dict\n",
    "from collections import Counter, defaultdict, namedtuple\n",
    "from itertools   import combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Word = str # Type for a word\n",
    "\n",
    "def valid_words(text) -> List[Word]:\n",
    "    \"\"\"Words with at least 4 letters, no 'S', and no more than 7 distinct letters.\"\"\"\n",
    "    return [w for w in text.upper().split() \n",
    "            if len(w) >= 4 and 'S' not in w and len(set(w)) <= 7]\n",
    "\n",
    "def is_pangram(word) -> bool: \n",
    "    \"\"\"Does a word have 7 distinct letters (some maybe more than once)?\"\"\"\n",
    "    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": [
       "['GAME', 'AMALGAM', 'GLAM', 'MEGAPLEX', 'CACCIATORE', 'EROTICA']"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mini = valid_words('game amalgam amalgamation glam gem gems em megaplex cacciatore erotica')\n",
    "mini"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that `gem` and `em` 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": [
       "{'GAME': 1,\n",
       " 'AMALGAM': 7,\n",
       " 'GLAM': 1,\n",
       " 'MEGAPLEX': 15,\n",
       " 'CACCIATORE': 17,\n",
       " 'EROTICA': 14}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{w: word_score(w) for w in mini}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 2: Honeycombs and Game Scores\n",
    "\n",
    "In a honeycomb the order of the letters doesn't matter; all that matters is:\n",
    "  1. The seven distinct letters in the honeycomb.\n",
    "  2. The one distinguished center letter.\n",
    "  \n",
    "Thus, we can represent a honeycomb as follows:\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Honeycomb(letters='AEGLMPX', center='G')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Honeycomb = namedtuple('Honeycomb', 'letters, center')\n",
    "\n",
    "hc = Honeycomb('AEGLMPX', 'G')\n",
    "hc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **game score** for a honeycomb is the sum of the word scores for all the words that the honeycomb can make. How do we know if a honeycomb can make a word? It can if (1) the word contains the honeycomb's center and (2) every letter in the word is in the honeycomb. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def game_score(honeycomb, words) -> int:\n",
    "    \"\"\"The total score for this honeycomb.\"\"\"\n",
    "    return sum(word_score(w) for w in words if can_make(honeycomb, w))\n",
    "\n",
    "def can_make(honeycomb, word) -> bool:\n",
    "    \"\"\"Can the honeycomb make this word?\"\"\"\n",
    "    letters, center = honeycomb\n",
    "    return center in word and all(L in letters for L in word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "game_score(hc, mini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'GAME': 1, 'AMALGAM': 7, 'GLAM': 1, 'MEGAPLEX': 15}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{w: word_score(w) for w in mini if can_make(hc, w)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 3: Best Honeycomb\n",
    "\n",
    "\n",
    "How many possible honeycombs are there? We can put any letter in the center, then any 6 letters around the outside; since there is no 'S', this gives a total of 25 × (24 choose 6) = 3,364,900 possible honeycombs. We could conceivably ask for the game score of every one of them and pick the best; that would probably take hours of computation (not seconds, and not days).\n",
    "\n",
    "However, a key constraint of the game is that **there must be at least one pangram** in the set of words that a valid honeycomb can make. That means that a valid honeycomb must ***be*** the set of seven letters in one of the pangram words in the word list, with any of the seven letters as the center. My approach to find the best (highest scoring) honeycomb is:\n",
    "\n",
    "  * Go through all the words and find all the valid honeycombs: the 7-letter pangram letter sets, with any of the 7 letters as center.\n",
    "  * Compute the game score for each valid honeycomb and return a honeycomb with maximal game score."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_honeycomb(words) -> Honeycomb: \n",
    "    \"\"\"Return a honeycomb with highest game score on these words.\"\"\"\n",
    "    return max(valid_honeycombs(words), \n",
    "               key=lambda h: game_score(h, words))\n",
    "\n",
    "def valid_honeycombs(words) -> List[Honeycomb]:\n",
    "    \"\"\"Valid Honeycombs are the pangram lettersets, with any center.\"\"\"\n",
    "    pangram_lettersets = {letterset(w) for w in words if is_pangram(w)}\n",
    "    return [Honeycomb(letters, center) \n",
    "            for letters in pangram_lettersets \n",
    "            for center in letters]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I will represent a set of letters as a sorted string of distinct letters. Why not a Python `set` (or `frozenset` if we want it to be the key of a dict)? Because a string takes up less space in memory, and its printed representation is  easier to read when debugging. Furthermore, with sets no more than 7 letters, the time to test for set membership will be small either way. Compare:\n",
    "- `frozenset({'A', 'E', 'G', 'L', 'M', 'P', 'X'})`\n",
    "- `'AEGLMPX'`\n",
    "\n",
    "I'll use the name `letterset` for the function that converts a word to a set of letters, and `Letterset` for the resulting type:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "Letterset = str # Type for a set of letters, like \"AGLM\"\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": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'GAME': 'AEGM',\n",
       " 'AMALGAM': 'AGLM',\n",
       " 'GLAM': 'AGLM',\n",
       " 'MEGAPLEX': 'AEGLMPX',\n",
       " 'CACCIATORE': 'ACEIORT',\n",
       " 'EROTICA': 'ACEIORT'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{w: letterset(w) for w in mini}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that 'AMALGAM' and 'GLAM' have the same letterset, as do 'CACCIATORE' and 'EROTICA'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[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'),\n",
       " 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')]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "valid_honeycombs(mini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Honeycomb(letters='ACEIORT', center='A')"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_honeycomb(mini)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**We're done!** We know how to find the best honeycomb. But so far, we've only done it  for the mini word list. \n",
    "\n",
    "# Step 4: 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": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  172820 enable1.txt\n"
     ]
    }
   ],
   "source": [
    "! [ -e enable1.txt ] || curl -O http://norvig.com/ngrams/enable1.txt\n",
    "! wc -w enable1.txt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "44585"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1 = valid_words(open('enable1.txt').read())\n",
    "len(enable1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14741"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pangrams = [w for w in enable1 if is_pangram(w)]\n",
    "len(pangrams)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7986"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len({letterset(w) for w in pangrams}) # pangram lettersets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55902"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(valid_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) valid honeycombs\n",
    "\n",
    "How long will it take to run `best_honeycomb(enable1)`? Most of the computation time is in `game_score` (which 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": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 11.4 ms, sys: 616 µs, total: 12 ms\n",
      "Wall time: 11.9 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "153"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time game_score(hc, enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About 11 milliseconds on my computer (this may vary). How many minutes would it be to run `game_score` for all 55,902 valid honeycombs?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.248699999999998"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ".011 * 55902 / 60"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "About 10 minutes. I could run `best_honeycomb(enable1)` right now and take a coffee break until it completes, 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",
    "# Step 5: Faster Algorithm: Points Table\n",
    "\n",
    "Here's my plan for a more efficient program:\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, 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 to be done only once, not 55,902  times. \n",
    "4. `game_score2` (the name is changed because the interface has changed) takes a honeycomb and a points table as input. The idea is that every word that the honeycomb can make must have a letterset that is the same as a valid **letter subset** of the honeycomb. A valid letter subset must include the center letter, and it may or may not include each of the other 6 letters, so there are exactly $2^6 = 64$ valid letter subsets. (The function `letter_subsets(honeycomb)` computes these.)\n",
    "The result of `game_score2` is the sum of the honeycomb's 64 letter subset entries in the points table.\n",
    "\n",
    "\n",
    "That means that in `game_score2` we no longer need to iterate over 44,585 words and check if each word is a subset of the honeycomb. Instead we iterate over the 64 subsets of the honeycomb and for each one check&mdash;in one table lookup&mdash;whether it is a word (or more than word) and how many total points those word(s) score.  Since 64 &lt; 44,585, that's a nice optimization!\n",
    "\n",
    "\n",
    "Here's the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "PointsTable = Dict[Letterset, int]\n",
    "\n",
    "def best_honeycomb(words) -> Honeycomb: \n",
    "    \"\"\"Return a honeycomb with highest game score on these words.\"\"\"\n",
    "    points_table = tabulate_points(words)\n",
    "    honeycombs = (Honeycomb(letters, center) \n",
    "                  for letters in points_table if len(letters) == 7 \n",
    "                  for center in letters)\n",
    "    return max(honeycombs, key=lambda h: game_score2(h, points_table))\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 64 subsets of the letters in the honeycomb, always including the center letter.\"\"\"\n",
    "    return [letters \n",
    "            for n in range(1, 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, given a points_table.\"\"\"\n",
    "    return sum(points_table[letterset] for letterset in letter_subsets(honeycomb))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's get a feel for how this works. \n",
    "\n",
    "First `letter_subsets` (a 4-letter honeycomb makes $2^3 = 8$ subsets; 7-letter honeycombs make 64):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['C', 'AC', 'BC', 'CD', 'ABC', 'ACD', 'BCD', 'ABCD']"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "letter_subsets(Honeycomb('ABCD', 'C')) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['GAME', 'AMALGAM', 'GLAM', 'MEGAPLEX', 'CACCIATORE', 'EROTICA']"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mini # Remind me again what the mini word list is?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now `tabulate_points`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'AEGM': 1, 'AGLM': 8, 'AEGLMPX': 15, 'ACEIORT': 31})"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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 `game_score` and `best_honeycomb` functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert game_score2(hc, tabulate_points(mini)) == 24\n",
    "assert best_honeycomb(mini).letters == 'ACEIORT'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 6: The Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, the solution to the puzzle:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.04 s, sys: 3.14 ms, total: 2.05 s\n",
      "Wall time: 2.05 s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(Honeycomb(letters='AEGINRT', center='R'), 3898)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time best = best_honeycomb(enable1)\n",
    "\n",
    "best, game_score(best, enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Wow! 3898 is a high score!** \n",
    "\n",
    "And it took only 2 seconds of computation to find the best honeycomb, not 10 minutes!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 7: Even Faster Algorithm: Branch and Bound\n",
    "\n",
    "A run time of 2 seconds is pretty good! But what if the word list were 100 times bigger? What if a honeycomb could have 14 letters, not just 7? We might still be looking for ideas to speed up the computation.  I happen to have one.\n",
    "\n",
    "Consider the word 'EQUIVOKE'. It is a pangram, but what with the 'Q' and 'V' and 'K', it is not a high-scoring honeycomb:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "game_score(Honeycomb('EIKOQUV', 'E'), enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "None of the other six center letters does any better. It would be great if we could eliminate all seven of these honeycombs at once, rather than trying each one in turn. So my idea is to:\n",
    "- Keep track of the best honeycomb and best score found so far.\n",
    "- For each new pangram letterset, ask \"if we weren't required to use the center letter, would this letterset score higher than the best honeycomb so far?\" \n",
    "- If yes, then try it with all seven centers; if not then discard it immediately.\n",
    "- This is called a [**branch and bound**](https://en.wikipedia.org/wiki/Branch_and_bound) algorithm: if an **upper bound** of the new letterset's score can't beat the best honeycomb so far, then we prune a whole **branch** of the search tree consisting of the seven honeycombs that have that letterset.\n",
    "\n",
    "What wpuld the score of a letterset be if we weren't required to use the center letter? It turns out I can make a dummy Honeycomb and specify the empty string for the center, `Honeycomb(letters, '')`, and call `game_score2` on that. This works because of a quirk of Python: we ask 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 `best_honeycomb` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_honeycomb(words) -> Honeycomb: \n",
    "    \"\"\"Return a honeycomb with highest game score on these words.\"\"\"\n",
    "    points_table = tabulate_points(words)\n",
    "    best, best_score = None, 0\n",
    "    for letters in points_table:\n",
    "        if len(letters) == 7 and game_score2(Honeycomb(letters, ''), points_table) > best_score:\n",
    "            for center in letters:\n",
    "                honeycomb = Honeycomb(letters, center)\n",
    "                score = game_score2(honeycomb, points_table)\n",
    "                if score > best_score:\n",
    "                    best, best_score = honeycomb, score\n",
    "    return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 459 ms, sys: 2.7 ms, total: 461 ms\n",
      "Wall time: 461 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "Honeycomb(letters='AEGINRT', center='R')"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time best_honeycomb(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Same honeycomb for the answer, but four times faster&mdash;less than half a second.\n",
    "\n",
    "# Step 8: Curiosity\n",
    "\n",
    "I'm curious about a bunch of things.\n",
    "\n",
    "* What's the highest-scoring individual word?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ANTITOTALITARIAN'"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(enable1, key=word_score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* What are some of the pangrams?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AARDWOLF',\n",
       " 'ANCIENTER',\n",
       " 'BABBLEMENT',\n",
       " 'BIVARIATE',\n",
       " 'CABEZON',\n",
       " 'CHEERFUL',\n",
       " 'COLLOGUING',\n",
       " 'CRANKLE',\n",
       " 'DEMERGERING',\n",
       " 'DWELLING',\n",
       " 'ETYMOLOGY',\n",
       " 'FLATTING',\n",
       " 'GARROTTING',\n",
       " 'HANDIER',\n",
       " 'IDENTIFY',\n",
       " 'INTERVIEWER',\n",
       " 'LARVICIDAL',\n",
       " 'MANDRAGORA',\n",
       " 'MORTGAGEE',\n",
       " 'NOTABLE',\n",
       " 'OVERHELD',\n",
       " 'PERONEAL',\n",
       " 'PRAWNED',\n",
       " 'QUILTER',\n",
       " 'REINITIATED',\n",
       " 'TABLEFUL',\n",
       " 'TOWHEAD',\n",
       " 'UNCHURCHLY',\n",
       " 'UTOPIAN',\n",
       " 'WINDAGE']"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pangrams[::500] # Every five-hundreth pangram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* What's the breakdown of reasons why words are invalid?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('has S', 103913), ('valid', 44585), ('> 7', 23400), ('< 4', 922)]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter('has S' if 'S' in w else \n",
    "        '< 4'   if len(w) < 4 else \n",
    "        '> 7'   if len(set(w)) > 7 else \n",
    "        'valid'\n",
    "        for w in open('enable1.txt').read().upper().split()).most_common()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are more than twice as many words with an 'S' as there are valid words.\n",
    "\n",
    "* About the points table: How many different letter subsets are there? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21661"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pts = tabulate_points(enable1)\n",
    "len(pts)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That means there's about two valid words for each letterset.\n",
    "\n",
    "* Which letter subsets score the most?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('AEGINRT', 832),\n",
       " ('ADEGINR', 486),\n",
       " ('ACILNOT', 470),\n",
       " ('ACEINRT', 465),\n",
       " ('CEINORT', 398),\n",
       " ('AEGILNT', 392),\n",
       " ('AGINORT', 380),\n",
       " ('ADEINRT', 318),\n",
       " ('CENORTU', 318),\n",
       " ('ACDEIRT', 307)]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pts.most_common(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The best honeycomb is also the highest scoring letter subset on its own (although it only gets 832 of the 3,898 total points from using all seven letters)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 9: Fancy Report\n",
    "\n",
    "I'd like to see the actual words that each honeycomb can make, in addition to the total score, 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(words, honeycomb=None):\n",
    "    \"\"\"Print stats, words, and word scores for the given honeycomb (or \n",
    "    for the best honeycomb if no honeycomb is given) over the given word list.\"\"\"\n",
    "    bins    = group_by(words, letterset)\n",
    "    adj     = (\"given\" if honeycomb else \"optimal\")\n",
    "    honeycomb = honeycomb or best_honeycomb(words)\n",
    "    points  = game_score(honeycomb, words)\n",
    "    subsets = letter_subsets(honeycomb)\n",
    "    nwords  = sum(len(bins[s]) for s in subsets)\n",
    "    print(f'For this list of {Ns(len(words), \"word\")}:')\n",
    "    print(f'The {adj} honeycomb {honeycomb.letters} with center {honeycomb.center}'\n",
    "          f' makes {Ns(nwords, \"word\")} for {Ns(points, \"point\")}:\\n')\n",
    "    indent = ' ' * 4\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",
    "            print(f'{s} makes {Ns(len(bins[s]), \"word\")} for {Ns(pts, \"point\")}:')\n",
    "            words = [f'{w}({word_score(w)})' for w in sorted(bins[s])]\n",
    "            print(fill(' '.join(words), width=80,\n",
    "                       initial_indent=indent, subsequent_indent=indent))\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": [
      "For this list of 6 words:\n",
      "The given honeycomb AEGLMPX with center G makes 4 words for 24 points:\n",
      "\n",
      "AEGLMPX makes 1 word for 15 points:\n",
      "    MEGAPLEX(15)\n",
      "AEGM makes 1 word for 1 point:\n",
      "    GAME(1)\n",
      "AGLM makes 2 words for 8 points:\n",
      "    AMALGAM(7) GLAM(1)\n"
     ]
    }
   ],
   "source": [
    "report(mini, hc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For this list of 44,585 words:\n",
      "The optimal honeycomb AEGINRT with center R makes 537 words for 3,898 points:\n",
      "\n",
      "AEGINRT makes 50 words for 832 points:\n",
      "    AERATING(15) AGGREGATING(18) ARGENTINE(16) ARGENTITE(16) ENTERTAINING(19)\n",
      "    ENTRAINING(17) ENTREATING(17) GARNIERITE(17) GARTERING(16) GENERATING(17)\n",
      "    GNATTIER(15) GRANITE(14) GRATINE(14) GRATINEE(15) GRATINEEING(18)\n",
      "    GREATENING(17) INGRATE(14) INGRATIATE(17) INTEGRATE(16) INTEGRATING(18)\n",
      "    INTENERATING(19) INTERAGE(15) INTERGANG(16) INTERREGNA(17) INTREATING(17)\n",
      "    ITERATING(16) ITINERATING(18) NATTERING(16) RATTENING(16) REAGGREGATING(20)\n",
      "    REATTAINING(18) REGENERATING(19) REGRANTING(17) REGRATING(16)\n",
      "    REINITIATING(19) REINTEGRATE(18) REINTEGRATING(20) REITERATING(18)\n",
      "    RETAGGING(16) RETAINING(16) RETARGETING(18) RETEARING(16) RETRAINING(17)\n",
      "    RETREATING(17) TANGERINE(16) TANGIER(14) TARGETING(16) TATTERING(16)\n",
      "    TEARING(14) TREATING(15)\n",
      "AEGINR makes 35 words for 270 points:\n",
      "    AGINNER(7) AGREEING(8) ANEARING(8) ANERGIA(7) ANGERING(8) ANGRIER(7)\n",
      "    ARGININE(8) EARING(6) EARNING(7) EARRING(7) ENGRAIN(7) ENGRAINING(10)\n",
      "    ENRAGING(8) GAINER(6) GANGRENING(10) GARNERING(9) GEARING(7) GRAINER(7)\n",
      "    GRAINIER(8) GRANNIE(7) GREGARINE(9) NAGGIER(7) NEARING(7) RANGIER(7)\n",
      "    REAGIN(6) REARING(7) REARRANGING(11) REEARNING(9) REENGAGING(10) REGAIN(6)\n",
      "    REGAINER(8) REGAINING(9) REGEARING(9) REGINA(6) REGINAE(7)\n",
      "AEGIRT makes 5 words for 34 points:\n",
      "    AIGRET(6) AIGRETTE(8) GAITER(6) IRRIGATE(8) TRIAGE(6)\n",
      "AEGNRT makes 13 words for 94 points:\n",
      "    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 makes 30 words for 232 points:\n",
      "    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)\n",
      "    ITINERANT(9) ITINERATE(9) NATTIER(7) NITRATE(7) RATINE(6) REATTAIN(8)\n",
      "    REINITIATE(10) RETAIN(6) RETAINER(8) RETINA(6) RETINAE(7) RETIRANT(8)\n",
      "    RETRAIN(7) TERRAIN(7) TERTIAN(7) TRAINEE(7) TRAINER(7) TRIENNIA(8)\n",
      "AGINRT makes 21 words for 167 points:\n",
      "    AIRTING(7) ATTIRING(8) GRANITA(7) GRANTING(8) GRATIN(6) GRATING(7)\n",
      "    INGRATIATING(12) INTRIGANT(9) IRRIGATING(10) IRRITATING(10) NARRATING(9)\n",
      "    NITRATING(9) RANTING(7) RATING(6) RATTING(7) TARING(6) TARRING(7) TARTING(7)\n",
      "    TITRATING(9) TRAINING(8) TRIAGING(8)\n",
      "EGINRT makes 26 words for 218 points:\n",
      "    ENGIRT(6) ENTERING(8) GETTERING(9) GITTERN(7) GREETING(8) IGNITER(7)\n",
      "    INTEGER(7) INTERNING(9) INTERRING(9) REENTERING(10) REGREETING(10)\n",
      "    REGRETTING(10) REIGNITE(8) REIGNITING(10) REINTERRING(11) RENTING(7)\n",
      "    RETINTING(9) RETIRING(8) RETTING(7) RINGENT(7) TEETERING(9) TENTERING(9)\n",
      "    TIERING(7) TITTERING(9) TREEING(7) TRIGGERING(10)\n",
      "AEGNR makes 18 words for 120 points:\n",
      "    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)\n",
      "    RANGER(6) REARRANGE(9) REENGAGE(8) REGNA(5)\n",
      "AEGRT makes 19 words for 123 points:\n",
      "    AGGREGATE(9) ERGATE(6) ETAGERE(7) GARGET(6) GARRET(6) GARTER(6) GRATE(5)\n",
      "    GRATER(6) GREAT(5) GREATER(7) REAGGREGATE(11) REGATTA(7) REGRATE(7) RETAG(5)\n",
      "    RETARGET(8) TAGGER(6) TARGE(5) TARGET(6) TERGA(5)\n",
      "AEINR makes 3 words for 19 points:\n",
      "    INANER(6) NARINE(6) RAINIER(7)\n",
      "AEIRT makes 20 words for 135 points:\n",
      "    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)\n",
      "    RETIARII(8) TARRIER(7) TATTIER(7) TEARIER(7) TERAI(5) TERRARIA(8) TITRATE(7)\n",
      "AENRT makes 19 words for 132 points:\n",
      "    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)\n",
      "    REENTRANT(9) RETREATANT(10) TANNER(6) TERNATE(7) TERRANE(7)\n",
      "AGINR makes 19 words for 138 points:\n",
      "    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)\n",
      "    INGRAINING(10) RAGGING(7) RAGING(6) RAINING(7) RANGING(7) RARING(6)\n",
      "AGIRT makes 1 word for 5 points:\n",
      "    TRAGI(5)\n",
      "AGNRT makes 1 word for 5 points:\n",
      "    GRANT(5)\n",
      "AINRT makes 9 words for 64 points:\n",
      "    ANTIAIR(7) ANTIAR(6) ANTIARIN(8) INTRANT(7) IRRITANT(8) RIANT(5) TITRANT(7)\n",
      "    TRAIN(5) TRINITARIAN(11)\n",
      "EGINR makes 24 words for 186 points:\n",
      "    ENGINEER(8) ENGINEERING(11) ERRING(6) GINGER(6) GINGERING(9) GINNER(6)\n",
      "    GINNIER(7) GREEING(7) GREENIE(7) GREENIER(8) GREENING(8) GRINNER(7)\n",
      "    NIGGER(6) REENGINEER(10) REENGINEERING(13) REGREENING(10) REIGN(5)\n",
      "    REIGNING(8) REINING(7) RENEGING(8) RENIG(5) RENIGGING(9) RERIGGING(9)\n",
      "    RINGER(6)\n",
      "EGIRT makes 4 words for 27 points:\n",
      "    GRITTIER(8) TERGITE(7) TIGER(5) TRIGGER(7)\n",
      "EGNRT makes 2 words for 12 points:\n",
      "    GERENT(6) REGENT(6)\n",
      "EINRT makes 29 words for 190 points:\n",
      "    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)\n",
      "    RENITENT(8) RENTIER(7) RETINE(6) RETINENE(8) RETINITE(8) RETINT(6)\n",
      "    TEENIER(7) TENTIER(7) TERRINE(7) TINIER(6) TINNER(6) TINNIER(7) TINTER(6)\n",
      "    TRIENE(6) TRINE(5)\n",
      "GINRT makes 6 words for 43 points:\n",
      "    GIRTING(7) GRITTING(8) RINGGIT(7) TIRING(6) TRIGGING(8) TRINING(7)\n",
      "AEGR makes 17 words for 84 points:\n",
      "    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)\n",
      "    REGGAE(6)\n",
      "AEIR makes 4 words for 22 points:\n",
      "    AERIE(5) AERIER(6) AIRER(5) AIRIER(6)\n",
      "AENR makes 9 words for 40 points:\n",
      "    ANEAR(5) ARENA(5) EARN(1) EARNER(6) NEAR(1) NEARER(6) RANEE(5) REEARN(6)\n",
      "    RERAN(5)\n",
      "AERT makes 24 words for 127 points:\n",
      "    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)\n",
      "    TATER(5) TATTER(6) TEAR(1) TEARER(6) TERRA(5) TERRAE(6) TETRA(5) TREAT(5)\n",
      "    TREATER(7)\n",
      "AGIR makes 2 words for 6 points:\n",
      "    AGRIA(5) RAGI(1)\n",
      "AGNR makes 5 words for 13 points:\n",
      "    GNAR(1) GNARR(5) GRAN(1) GRANA(5) RANG(1)\n",
      "AGRT makes 3 words for 13 points:\n",
      "    GRAT(1) RAGTAG(6) TAGRAG(6)\n",
      "AINR makes 4 words for 8 points:\n",
      "    AIRN(1) NAIRA(5) RAIN(1) RANI(1)\n",
      "AIRT makes 5 words for 21 points:\n",
      "    AIRT(1) ATRIA(5) RIATA(5) TIARA(5) TRAIT(5)\n",
      "ANRT makes 10 words for 50 points:\n",
      "    ANTRA(5) ARRANT(6) RANT(1) RATAN(5) RATTAN(6) TANTARA(7) TANTRA(6) TARN(1)\n",
      "    TARTAN(6) TARTANA(7)\n",
      "EGIR makes 3 words for 17 points:\n",
      "    GREIGE(6) RERIG(5) RIGGER(6)\n",
      "EGNR makes 6 words for 37 points:\n",
      "    GENRE(5) GREEN(5) GREENER(7) REGREEN(7) RENEGE(6) RENEGER(7)\n",
      "EGRT makes 7 words for 45 points:\n",
      "    EGRET(5) GETTER(6) GREET(5) GREETER(7) REGREET(7) REGRET(6) REGRETTER(9)\n",
      "EINR makes 4 words for 17 points:\n",
      "    INNER(5) REIN(1) RENIN(5) RENNIN(6)\n",
      "EIRT makes 17 words for 87 points:\n",
      "    RETIE(5) RETIRE(6) RETIREE(7) RETIRER(7) RITE(1) RITTER(6) TERRIER(7)\n",
      "    TERRIT(6) TIER(1) TIRE(1) TITER(5) TITRE(5) TITTER(6) TITTERER(8) TRIER(5)\n",
      "    TRITE(5) TRITER(6)\n",
      "ENRT makes 19 words for 104 points:\n",
      "    ENTER(5) ENTERER(7) ENTREE(6) ETERNE(6) NETTER(6) REENTER(7) RENNET(6)\n",
      "    RENT(1) RENTE(5) RENTER(6) RETENE(6) TEENER(6) TENNER(6) TENTER(6) TERN(1)\n",
      "    TERNE(5) TERREEN(7) TERRENE(7) TREEN(5)\n",
      "GINR makes 9 words for 44 points:\n",
      "    GIRN(1) GIRNING(7) GRIN(1) GRINNING(8) IRING(5) RIGGING(7) RING(1)\n",
      "    RINGING(7) RINNING(7)\n",
      "GIRT makes 3 words for 3 points:\n",
      "    GIRT(1) GRIT(1) TRIG(1)\n",
      "AER makes 7 words for 25 points:\n",
      "    AREA(1) AREAE(5) ARREAR(6) RARE(1) RARER(5) REAR(1) REARER(6)\n",
      "AGR makes 2 words for 2 points:\n",
      "    AGAR(1) RAGA(1)\n",
      "AIR makes 2 words for 2 points:\n",
      "    ARIA(1) RAIA(1)\n",
      "ART makes 5 words for 24 points:\n",
      "    ATTAR(5) RATATAT(7) TART(1) TARTAR(6) TATAR(5)\n",
      "EGR makes 4 words for 15 points:\n",
      "    EGER(1) EGGER(5) GREE(1) GREEGREE(8)\n",
      "EIR makes 2 words for 11 points:\n",
      "    EERIE(5) EERIER(6)\n",
      "ENR makes 1 word for 1 point:\n",
      "    ERNE(1)\n",
      "ERT makes 7 words for 27 points:\n",
      "    RETE(1) TEETER(6) TERETE(6) TERRET(6) TETTER(6) TREE(1) TRET(1)\n",
      "GIR makes 2 words for 7 points:\n",
      "    GRIG(1) GRIGRI(6)\n"
     ]
    }
   ],
   "source": [
    "report(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 10: S Words\n",
    "\n",
    "What if we allowed honeycombs and words to have an 'S' in them?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(98141, 44585)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enable1s = [w for w in open('enable1.txt').read().upper().split() \n",
    "           if len(w) >= 4 and len(set(w)) <= 7]\n",
    "\n",
    "len(enable1s), len(enable1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That more than doubles the number of words. Will it double the score?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "For this list of 98,141 words:\n",
      "The optimal honeycomb AEINRST with center E makes 1,179 words for 8,681 points:\n",
      "\n",
      "AEINRST makes 86 words for 1,381 points:\n",
      "    ANESTRI(14) ANTISERA(15) ANTISTRESS(17) ANTSIER(14) ARENITES(15)\n",
      "    ARSENITE(15) ARSENITES(16) ARTINESS(15) ARTINESSES(17) ATTAINERS(16)\n",
      "    ENTERTAINERS(19) ENTERTAINS(17) ENTRAINERS(17) ENTRAINS(15) ENTREATIES(17)\n",
      "    ERRANTRIES(17) INERTIAS(15) INSTANTER(16) INTENERATES(18) INTERSTATE(17)\n",
      "    INTERSTATES(18) INTERSTRAIN(18) INTERSTRAINS(19) INTRASTATE(17) INTREATS(15)\n",
      "    IRATENESS(16) IRATENESSES(18) ITINERANTS(17) ITINERARIES(18) ITINERATES(17)\n",
      "    NASTIER(14) NITRATES(15) RAINIEST(15) RATANIES(15) RATINES(14) REATTAINS(16)\n",
      "    REINITIATES(18) REINSTATE(16) REINSTATES(17) RESINATE(15) RESINATES(16)\n",
      "    RESISTANT(16) RESISTANTS(17) RESTRAIN(15) RESTRAINER(17) RESTRAINERS(18)\n",
      "    RESTRAINS(16) RESTRAINT(16) RESTRAINTS(17) RETAINERS(16) RETAINS(14)\n",
      "    RETINAS(14) RETIRANTS(16) RETRAINS(15) RETSINA(14) RETSINAS(15)\n",
      "    SANITARIES(17) SEATRAIN(15) SEATRAINS(16) STAINER(14) STAINERS(15)\n",
      "    STANNARIES(17) STEARIN(14) STEARINE(15) STEARINES(16) STEARINS(15)\n",
      "    STRAINER(15) STRAINERS(16) STRAITEN(15) STRAITENS(16) STRAITNESS(17)\n",
      "    STRAITNESSES(19) TANISTRIES(17) TANNERIES(16) TEARSTAIN(16) TEARSTAINS(17)\n",
      "    TENANTRIES(17) TERNARIES(16) TERRAINS(15) TERTIANS(15) TRAINEES(15)\n",
      "    TRAINERS(15) TRANSIENT(16) TRANSIENTS(17) TRISTEARIN(17) TRISTEARINS(18)\n",
      "AEINRS makes 16 words for 124 points:\n",
      "    AIRINESS(8) AIRINESSES(10) ANSERINE(8) ANSERINES(9) ARISEN(6) ARSINE(6)\n",
      "    ARSINES(7) INSANER(7) INSNARE(7) INSNARER(8) INSNARERS(9) INSNARES(8)\n",
      "    SENARII(7) SIERRAN(7) SIRENIAN(8) SIRENIANS(9)\n",
      "AEINRT makes 30 words for 232 points:\n",
      "    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)\n",
      "    ITINERANT(9) ITINERATE(9) NATTIER(7) NITRATE(7) RATINE(6) REATTAIN(8)\n",
      "    REINITIATE(10) RETAIN(6) RETAINER(8) RETINA(6) RETINAE(7) RETIRANT(8)\n",
      "    RETRAIN(7) TERRAIN(7) TERTIAN(7) TRAINEE(7) TRAINER(7) TRIENNIA(8)\n",
      "AEINST makes 80 words for 713 points:\n",
      "    ANISETTE(8) ANISETTES(9) ANTISENSE(9) ANTISTATE(9) ANTSIEST(8)\n",
      "    ASININITIES(11) ASSASSINATE(11) ASSASSINATES(12) ASTATINE(8) ASTATINES(9)\n",
      "    ENTASIA(7) ENTASIAS(8) ENTASIS(7) ETESIAN(7) ETESIANS(8) INANEST(7)\n",
      "    INANITIES(9) INITIATES(9) INNATENESS(10) INNATENESSES(12) INSANEST(8)\n",
      "    INSANITIES(10) INSATIATE(9) INSATIATENESS(13) INSATIATENESSES(15)\n",
      "    INSENSATE(9) INSTANTANEITIES(15) INSTANTIATE(11) INSTANTIATES(12)\n",
      "    INSTANTNESS(11) INSTANTNESSES(13) INSTATE(7) INSTATES(8) INTESTATE(9)\n",
      "    INTESTATES(10) ISATINE(7) ISATINES(8) NASTIES(7) NASTIEST(8) NASTINESS(9)\n",
      "    NASTINESSES(11) NATTIEST(8) NATTINESS(9) NATTINESSES(11) SANITATE(8)\n",
      "    SANITATES(9) SANITIES(8) SANITISE(8) SANITISES(9) SATINET(7) SATINETS(8)\n",
      "    SENTENTIA(9) SENTENTIAE(10) SESTINA(7) SESTINAS(8) STANINE(7) STANINES(8)\n",
      "    STANNITE(8) STANNITES(9) TAENIAS(7) TAENIASES(9) TAENIASIS(9) TANSIES(7)\n",
      "    TASTINESS(9) TASTINESSES(11) TATTINESS(9) TATTINESSES(11) TENIAS(6)\n",
      "    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 makes 60 words for 473 points:\n",
      "    AERIEST(7) AIREST(6) AIRIEST(7) ARIETTAS(8) ARIETTES(8) ARISTAE(7)\n",
      "    ARISTATE(8) ARTERIES(8) ARTERITIS(9) ARTIEST(7) ARTISTE(7) ARTISTES(8)\n",
      "    ARTISTRIES(10) ARTSIER(7) ARTSIEST(8) ASSISTER(8) ASSISTERS(9) ASTERIA(7)\n",
      "    ASTERIAS(8) ATRESIA(7) ATRESIAS(8) ATTIRES(7) EATERIES(8) IRATEST(7)\n",
      "    IRRITATES(9) ITERATES(8) RARITIES(8) RATITES(7) RATTIEST(8) REITERATES(10)\n",
      "    SATIRE(6) SATIRES(7) SATIRISE(8) SATIRISES(9) SERIATE(7) SERIATES(8)\n",
      "    SESTERTIA(9) STARRIER(8) STARRIEST(9) STRAITER(8) STRAITEST(9) STRIAE(6)\n",
      "    STRIATE(7) STRIATES(8) TARRIERS(8) TARRIES(7) TARRIEST(8) TARSIER(7)\n",
      "    TARSIERS(8) TASTIER(7) TEARIEST(8) TERAIS(6) TERTIARIES(10) TITRATES(8)\n",
      "    TRAITRESS(9) TRAITRESSES(11) TREATIES(8) TREATISE(8) TREATISES(9)\n",
      "    TRISTATE(8)\n",
      "AENRST makes 40 words for 336 points:\n",
      "    ANTEATERS(9) ANTRES(6) ARRESTANT(9) ARRESTANTS(10) ARSENATE(8) ARSENATES(9)\n",
      "    ASSENTER(8) ASSENTERS(9) ASTERN(6) EARNEST(7) EARNESTNESS(11)\n",
      "    EARNESTNESSES(13) EARNESTS(8) EASTERN(7) EASTERNER(9) EASTERNERS(10)\n",
      "    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)\n",
      "    RETREATANTS(11) SARSENET(8) SARSENETS(9) SERENATA(8) SERENATAS(9)\n",
      "    SERENATE(8) STERNA(6) TANNERS(7) TARANTASES(10) TARTNESS(8) TARTNESSES(10)\n",
      "    TERRANES(8)\n",
      "EINRST makes 70 words for 582 points:\n",
      "    ENTERITIS(9) ENTERITISES(11) ENTIRENESS(10) ENTIRENESSES(12) ENTIRES(7)\n",
      "    ENTIRETIES(10) ENTRIES(7) ESTRIN(6) ESTRINS(7) ETERNISE(8) ETERNISES(9)\n",
      "    ETERNITIES(10) INERTNESS(9) INERTNESSES(11) INERTS(6) INSERT(6) INSERTER(8)\n",
      "    INSERTERS(9) INSERTS(7) INSETTER(8) INSETTERS(9) INSISTER(8) INSISTERS(9)\n",
      "    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)\n",
      "    NITRES(6) NITRITES(8) REENTRIES(9) REINSERT(8) REINSERTS(9) REINTERS(8)\n",
      "    RENTIERS(8) RETINENES(9) RETINES(7) RETINITES(9) RETINITIS(9) RETINTS(7)\n",
      "    SENTRIES(8) SERENITIES(10) SINISTER(8) SINISTERNESS(12) SINISTERNESSES(14)\n",
      "    SINTER(6) SINTERS(7) STERNITE(8) STERNITES(9) STINTER(7) STINTERS(8)\n",
      "    TEENSIER(8) TEENTSIER(9) TERRINES(8) TINNERS(7) TINTERS(7) TRIENES(7)\n",
      "    TRIENS(6) TRIENTES(8) TRINES(6) TRINITIES(9) TRITENESS(9) TRITENESSES(11)\n",
      "AEINR makes 3 words for 19 points:\n",
      "    INANER(6) NARINE(6) RAINIER(7)\n",
      "AEINS makes 17 words for 129 points:\n",
      "    ANISE(5) ANISES(6) ASININE(7) EASINESS(8) EASINESSES(10) INANENESS(9)\n",
      "    INANENESSES(11) INANES(6) INSANE(6) INSANENESS(10) INSANENESSES(12)\n",
      "    NANNIES(7) SANIES(6) SANSEI(6) SANSEIS(7) SIENNA(6) SIENNAS(7)\n",
      "AEINT makes 10 words for 64 points:\n",
      "    ENTIA(5) INITIATE(8) INNATE(6) TAENIA(6) TAENIAE(7) TENIA(5) TENIAE(6)\n",
      "    TINEA(5) TITANATE(8) TITANITE(8)\n",
      "AEIRS makes 17 words for 106 points:\n",
      "    AERIES(6) AIRERS(6) ARISE(5) ARISES(6) ARRISES(7) EASIER(6) RAISE(5)\n",
      "    RAISER(6) RAISERS(7) RAISES(6) RERAISE(7) RERAISES(8) SASSIER(7) SERAI(5)\n",
      "    SERAIS(6) SIERRA(6) SIERRAS(7)\n",
      "AEIRT makes 20 words for 135 points:\n",
      "    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)\n",
      "    RETIARII(8) TARRIER(7) TATTIER(7) TEARIER(7) TERAI(5) TERRARIA(8) TITRATE(7)\n",
      "AEIST makes 15 words for 112 points:\n",
      "    EASIEST(7) ETATIST(7) SASSIEST(8) SATIATE(7) SATIATES(8) SATIETIES(9)\n",
      "    SIESTA(6) SIESTAS(7) STEATITE(8) STEATITES(9) TASSIE(6) TASSIES(7)\n",
      "    TASTIEST(8) TATTIES(7) TATTIEST(8)\n",
      "AENRS makes 25 words for 172 points:\n",
      "    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)\n",
      "    RARENESS(8) RARENESSES(10) REEARNS(7) RENNASE(7) RENNASES(8) SANER(5)\n",
      "    SARSEN(6) SARSENS(7) SNARE(5) SNARER(6) SNARERS(7) SNARES(6)\n",
      "AENRT makes 19 words for 132 points:\n",
      "    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)\n",
      "    REENTRANT(9) RETREATANT(10) TANNER(6) TERNATE(7) TERRANE(7)\n",
      "AENST makes 32 words for 217 points:\n",
      "    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)\n",
      "    NEATEST(7) NEATNESS(8) NEATNESSES(10) NEATS(5) SANEST(6) SATEEN(6)\n",
      "    SATEENS(7) SENATE(6) SENATES(7) SENSATE(7) SENSATES(8) SETENANT(8)\n",
      "    SETENANTS(9) STANE(5) STANES(6) TANNATES(8) TANNEST(7) TENANTS(7)\n",
      "AERST makes 85 words for 604 points:\n",
      "    AERATES(7) ARETES(6) ARREST(6) ARRESTEE(8) ARRESTEES(9) ARRESTER(8)\n",
      "    ARRESTERS(9) ARRESTS(7) ASSERT(6) ASSERTER(8) ASSERTERS(9) ASSERTS(7)\n",
      "    ASTER(5) ASTERS(6) ATTESTER(8) ATTESTERS(9) EASTER(6) EASTERS(7) EATERS(6)\n",
      "    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)\n",
      "    REASSERT(8) REASSERTS(9) REATAS(6) RESEAT(6) RESEATS(7) RESTART(7)\n",
      "    RESTARTS(8) RESTATE(7) RESTATES(8) RETASTE(7) RETASTES(8) RETEARS(7)\n",
      "    RETREATERS(10) RETREATS(8) SEAREST(7) SEATER(6) SEATERS(7) SERRATE(7)\n",
      "    SERRATES(8) STARE(5) STARER(6) STARERS(7) STARES(6) STARETS(7) STARTER(7)\n",
      "    STARTERS(8) STATER(6) STATERS(7) STEARATE(8) STEARATES(9) STRASSES(8)\n",
      "    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)\n",
      "    TERRAS(6) TERRASES(8) TESSERA(7) TESSERAE(8) TETRAS(6) TRASSES(7)\n",
      "    TREATERS(8) TREATS(6)\n",
      "EINRS makes 29 words for 184 points:\n",
      "    EERINESS(8) EERINESSES(10) ESERINE(7) ESERINES(8) INNERS(6) NEREIS(6)\n",
      "    REINS(5) RENINS(6) RENNINS(7) RERISEN(7) RESIN(5) RESINS(6) RINSE(5)\n",
      "    RINSER(6) RINSERS(7) RINSES(6) RISEN(5) SEINER(6) SEINERS(7) SEREIN(6)\n",
      "    SEREINS(7) SERIN(5) SERINE(6) SERINES(7) SERINS(6) SINNER(6) SINNERS(7)\n",
      "    SIREN(5) SIRENS(6)\n",
      "EINRT makes 29 words for 190 points:\n",
      "    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)\n",
      "    RENITENT(8) RENTIER(7) RETINE(6) RETINENE(8) RETINITE(8) RETINT(6)\n",
      "    TEENIER(7) TENTIER(7) TERRINE(7) TINIER(6) TINNER(6) TINNIER(7) TINTER(6)\n",
      "    TRIENE(6) TRINE(5)\n",
      "EINST makes 58 words for 469 points:\n",
      "    EINSTEIN(8) EINSTEINS(9) ENTITIES(8) INSENTIENT(10) INSET(5) INSETS(6)\n",
      "    INSISTENT(9) INTENSE(7) INTENSENESS(11) INTENSENESSES(13) INTENSEST(9)\n",
      "    INTENSITIES(11) INTENTNESS(10) INTENTNESSES(12) INTENTS(7) INTESTINE(9)\n",
      "    INTESTINES(10) INTINES(7) NEIST(5) NETTIEST(8) NINETEENS(9) NINETIES(8)\n",
      "    NITES(5) NITTIEST(8) SENITI(6) SENNIT(6) SENNITS(7) SENSITISE(9)\n",
      "    SENSITISES(10) SENTI(5) SENTIENT(8) SENTIENTS(9) SESTINE(7) SESTINES(8)\n",
      "    SIENITE(7) SIENITES(8) SITTEN(6) STEIN(5) STEINS(6) TEENIEST(8) TEENSIEST(9)\n",
      "    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)\n",
      "    TININESS(8) TININESSES(10) TINNIEST(8) TINNINESS(9) TINNINESSES(11)\n",
      "EIRST makes 38 words for 262 points:\n",
      "    EERIEST(7) IRITISES(8) RESIST(6) RESISTER(8) RESISTERS(9) RESISTS(7)\n",
      "    RESITE(6) RESITES(7) RETIES(6) RETIREES(8) RETIRERS(8) RETIRES(7) RETRIES(7)\n",
      "    RITES(5) RITTERS(7) SISTER(6) SISTERS(7) SITTER(6) SITTERS(7) STIRRER(7)\n",
      "    STIRRERS(8) STRETTI(7) TERRIERS(8) TERRIES(7) TERRITS(7) TESTIER(7) TIERS(5)\n",
      "    TIRES(5) TITERS(6) TITRES(6) TITTERERS(9) TITTERS(7) TRESSIER(8)\n",
      "    TRESSIEST(9) TRIERS(6) TRIES(5) TRISTE(6) TRITEST(7)\n",
      "ENRST makes 35 words for 246 points:\n",
      "    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)\n",
      "    RESENT(6) RESENTS(7) RETENES(7) SERENEST(8) STERN(5) STERNER(7) STERNEST(8)\n",
      "    STERNNESS(9) STERNNESSES(11) STERNS(6) TEENERS(7) TENNERS(7) TENSER(6)\n",
      "    TENTERS(7) TERNES(6) TERNS(5) TERREENS(8) TERRENES(8) TERSENESS(9)\n",
      "    TERSENESSES(11) TREENS(6)\n",
      "AEIN makes 2 words for 11 points:\n",
      "    INANE(5) NANNIE(6)\n",
      "AEIR makes 4 words for 22 points:\n",
      "    AERIE(5) AERIER(6) AIRER(5) AIRIER(6)\n",
      "AEIS makes 2 words for 13 points:\n",
      "    EASIES(6) SASSIES(7)\n",
      "AEIT makes 1 word for 6 points:\n",
      "    TATTIE(6)\n",
      "AENR makes 9 words for 40 points:\n",
      "    ANEAR(5) ARENA(5) EARN(1) EARNER(6) NEAR(1) NEARER(6) RANEE(5) REEARN(6)\n",
      "    RERAN(5)\n",
      "AENS makes 9 words for 46 points:\n",
      "    ANES(1) ANSAE(5) SANE(1) SANENESS(8) SANENESSES(10) SANES(5) SENNA(5)\n",
      "    SENNAS(6) SENSA(5)\n",
      "AENT makes 13 words for 63 points:\n",
      "    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 makes 26 words for 121 points:\n",
      "    AREAS(5) ARES(1) ARREARS(7) ARSE(1) ARSES(5) EARS(1) ERAS(1) ERASE(5)\n",
      "    ERASER(6) ERASERS(7) ERASES(6) RARES(5) RASE(1) RASER(5) RASERS(6) RASES(5)\n",
      "    REARERS(7) REARS(5) REASSESS(8) REASSESSES(10) SAREE(5) SAREES(6) SEAR(1)\n",
      "    SEARER(6) SEARS(5) SERA(1)\n",
      "AERT makes 24 words for 127 points:\n",
      "    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)\n",
      "    TATER(5) TATTER(6) TEAR(1) TEARER(6) TERRA(5) TERRAE(6) TETRA(5) TREAT(5)\n",
      "    TREATER(7)\n",
      "AEST makes 35 words for 164 points:\n",
      "    ASSET(5) ASSETS(6) ATES(1) ATTEST(6) ATTESTS(7) EAST(1) EASTS(5) EATS(1)\n",
      "    ESTATE(6) ESTATES(7) ETAS(1) SATE(1) SATES(5) SEAT(1) SEATS(5) SETA(1)\n",
      "    SETAE(5) STASES(6) STATE(5) STATES(6) TASSE(5) TASSES(6) TASSET(6)\n",
      "    TASSETS(7) TASTE(5) TASTES(6) TATES(5) TEAS(1) TEASE(5) TEASES(6) TEATS(5)\n",
      "    TESTA(5) TESTAE(6) TESTATE(7) TESTATES(8)\n",
      "EINR makes 4 words for 17 points:\n",
      "    INNER(5) REIN(1) RENIN(5) RENNIN(6)\n",
      "EINS makes 10 words for 53 points:\n",
      "    NINES(5) NINNIES(7) NISEI(5) NISEIS(6) SEINE(5) SEINES(6) SEISIN(6)\n",
      "    SEISINS(7) SINE(1) SINES(5)\n",
      "EINT makes 6 words for 28 points:\n",
      "    INTENT(6) INTINE(6) NINETEEN(8) NITE(1) TENTIE(6) TINE(1)\n",
      "EIRS makes 20 words for 101 points:\n",
      "    IRES(1) IRISES(6) REIS(1) RERISE(6) RERISES(7) RISE(1) RISER(5) RISERS(6)\n",
      "    RISES(5) SEISER(6) SEISERS(7) SERIES(6) SERRIES(7) SIRE(1) SIREE(5)\n",
      "    SIREES(6) SIRES(5) SIRREE(6) SIRREES(7) SISSIER(7)\n",
      "EIRT makes 17 words for 87 points:\n",
      "    RETIE(5) RETIRE(6) RETIREE(7) RETIRER(7) RITE(1) RITTER(6) TERRIER(7)\n",
      "    TERRIT(6) TIER(1) TIRE(1) TITER(5) TITRE(5) TITTER(6) TITTERER(8) TRIER(5)\n",
      "    TRITE(5) TRITER(6)\n",
      "EIST makes 8 words for 41 points:\n",
      "    SISSIEST(8) SITE(1) SITES(5) STIES(5) TESTIEST(8) TESTIS(6) TIES(1)\n",
      "    TITTIES(7)\n",
      "ENRS makes 12 words for 80 points:\n",
      "    ERNES(5) ERNS(1) RESEEN(6) SERENE(6) SERENENESS(10) SERENENESSES(12)\n",
      "    SERENER(7) SERENES(7) SNEER(5) SNEERER(7) SNEERERS(8) SNEERS(6)\n",
      "ENRT makes 19 words for 104 points:\n",
      "    ENTER(5) ENTERER(7) ENTREE(6) ETERNE(6) NETTER(6) REENTER(7) RENNET(6)\n",
      "    RENT(1) RENTE(5) RENTER(6) RETENE(6) TEENER(6) TENNER(6) TENTER(6) TERN(1)\n",
      "    TERNE(5) TERREEN(7) TERRENE(7) TREEN(5)\n",
      "ENST makes 18 words for 94 points:\n",
      "    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)\n",
      "    TENSES(6) TENSEST(7) TENTS(5)\n",
      "ERST makes 44 words for 266 points:\n",
      "    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)\n",
      "    RESTS(5) RETEST(6) RETESTS(7) RETS(1) SEREST(6) SETTER(6) SETTERS(7)\n",
      "    STEER(5) STEERER(7) STEERERS(8) STEERS(6) STERE(5) STERES(6) STREET(6)\n",
      "    STREETS(7) STRESS(6) STRESSES(8) STRETTE(7) TEETERS(7) TERRETS(7) TERSE(5)\n",
      "    TERSER(6) TERSEST(7) TESTER(6) TESTERS(7) TETTERS(7) TREES(5) TRESS(5)\n",
      "    TRESSES(7) TRETS(5)\n",
      "AER makes 7 words for 25 points:\n",
      "    AREA(1) AREAE(5) ARREAR(6) RARE(1) RARER(5) REAR(1) REARER(6)\n",
      "AES makes 8 words for 33 points:\n",
      "    ASEA(1) ASSES(5) ASSESS(6) ASSESSES(8) EASE(1) EASES(5) SASSES(6) SEAS(1)\n",
      "AET makes 2 words for 2 points:\n",
      "    TATE(1) TEAT(1)\n",
      "EIN makes 1 word for 1 point:\n",
      "    NINE(1)\n",
      "EIR makes 2 words for 11 points:\n",
      "    EERIE(5) EERIER(6)\n",
      "EIS makes 7 words for 35 points:\n",
      "    ISSEI(5) ISSEIS(6) SEIS(1) SEISE(5) SEISES(6) SISES(5) SISSIES(7)\n",
      "EIT makes 1 word for 6 points:\n",
      "    TITTIE(6)\n",
      "ENR makes 1 word for 1 point:\n",
      "    ERNE(1)\n",
      "ENS makes 6 words for 20 points:\n",
      "    NESS(1) NESSES(6) SEEN(1) SENE(1) SENSE(5) SENSES(6)\n",
      "ENT makes 5 words for 15 points:\n",
      "    ENTENTE(7) NETT(1) TEEN(1) TENET(5) TENT(1)\n",
      "ERS makes 13 words for 52 points:\n",
      "    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 makes 7 words for 27 points:\n",
      "    RETE(1) TEETER(6) TERETE(6) TERRET(6) TETTER(6) TREE(1) TRET(1)\n",
      "EST makes 18 words for 79 points:\n",
      "    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)\n",
      "    TSETSE(6) TSETSES(7)\n",
      "EN makes 1 word for 1 point:\n",
      "    NENE(1)\n",
      "ES makes 3 words for 7 points:\n",
      "    ESES(1) ESSES(5) SEES(1)\n"
     ]
    }
   ],
   "source": [
    "report(enable1s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes it does  (roughly) double the score!\n",
    "\n",
    "# Summary\n",
    "\n",
    "Thanks to a series of ideas, we were able to achieve a substantial reduction in the number of honeycombs that need to be examined (a factor of 400), the run time needed for `game_score` (a factor of about 200), and the overall run time (a factor of about 70,000).\n",
    "\n",
    "- **Enumeration (10 hours (estimate) run time; 3,364,900 honeycombs)**<br>Try every possible honeycomb.\n",
    "- **Pangram Lettersets (11 minutes (estimate) run time; 55,902 honeycombs)**<br>Try just the honeycombs that are pangram lettersets (with every center).\n",
    "- **Points Table (2 seconds run time; 55,902 honeycombs)**<br>Precompute the score for each letterset, and sum the 64 letter subsets of each honeycomb.\n",
    "- **Branch and Bound (1/2 second run time; 8,084 honeycombs)**<br>Try every center only for lettersets that score better than the best score so far.\n",
    "\n",
    "\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; 3,898 points &nbsp; &nbsp; &nbsp; &nbsp; 1,179 words; 8,681 points\n",
    "    <br>\n",
    "</center>"
   ]
  }
 ],
 "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
}