Updated notebook versions

[cas-master-teacher-training.git] / hangman / 04-hangman-better.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategies\n",
    "We've got the plumbing all working. Now to play and come up with some better playing strategies. \n",
    "\n",
    "First, some repetition from the previous section."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import re\n",
    "import random\n",
    "import string\n",
    "import collections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "WORDS = [w.strip() for w in open('/usr/share/dict/british-english').readlines() \n",
    "         if re.match(r'^[a-z]*$', w.strip())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "LETTER_COUNTS = collections.Counter(l.lower() for l in open('../sherlock-holmes.txt').read() if l in string.ascii_letters)\n",
    "LETTERS_IN_ORDER = [p[0] for p in LETTER_COUNTS.most_common()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "STARTING_LIVES = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Game:\n",
    "    def __init__(self, target, player=None, lives=STARTING_LIVES):\n",
    "        self.lives = lives\n",
    "        self.player = player\n",
    "        self.target = target\n",
    "        self.discovered = list('_' * len(target))\n",
    "        self.wrong_letters = []\n",
    "        self.game_finished = False\n",
    "        self.game_won = False\n",
    "        self.game_lost = False\n",
    "    \n",
    "    def find_all(self, letter):\n",
    "        return [p for p, l in enumerate(self.target) if l == letter]\n",
    "    \n",
    "    def update_discovered_word(self, guessed_letter):\n",
    "        locations = self.find_all(guessed_letter)\n",
    "        for location in locations:\n",
    "            self.discovered[location] = guessed_letter\n",
    "        return self.discovered\n",
    "    \n",
    "    def do_turn(self):\n",
    "        if self.player:\n",
    "            guess = self.player.guess(self.discovered, self.wrong_letters, self.lives)\n",
    "        else:\n",
    "            guess = self.ask_for_guess()\n",
    "        if guess in self.target:\n",
    "            self.update_discovered_word(guess)\n",
    "        else:\n",
    "            self.lives -= 1\n",
    "            if guess not in self.wrong_letters:\n",
    "                self.wrong_letters += [guess]\n",
    "        if self.lives == 0:\n",
    "            self.game_finished = True\n",
    "            self.game_lost = True\n",
    "        if '_' not in self.discovered:\n",
    "            self.game_finished = True\n",
    "            self.game_won = True\n",
    "            \n",
    "    def ask_for_guess(self):\n",
    "        print('Word:', ' '.join(self.discovered), \n",
    "              ' : Lives =', self.lives, \n",
    "              ', wrong guesses:', ' '.join(sorted(self.wrong_letters)))\n",
    "        guess = input('Enter letter: ').strip().lower()[0]\n",
    "        return guess\n",
    "    \n",
    "    def play_game(self):\n",
    "        while not self.game_finished:\n",
    "            self.do_turn()\n",
    "        if not self.player:\n",
    "            self.report_on_game()\n",
    "        return self.game_won\n",
    "    \n",
    "    def report_on_game(self):\n",
    "        if self.game_won:\n",
    "            print('You won! The word was', self.target)\n",
    "        else:\n",
    "            print('You lost. The word was', self.target)\n",
    "        return self.game_won"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerFixedOrder:\n",
    "    def __init__(self, ordered_letters):\n",
    "        self.ordered_letters = ordered_letters\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAlphabetical(PlayerFixedOrder):\n",
    "    def __init__(self):\n",
    "        super().__init__(string.ascii_lowercase)\n",
    "\n",
    "class PlayerFreqOrdered(PlayerFixedOrder):\n",
    "    def __init__(self):\n",
    "        super().__init__(LETTERS_IN_ORDER)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Timing runs\n",
    "Use the IPython `timeit` cellmagic to time runs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n",
      "45\n",
      "54\n",
      "54\n",
      "1 loops, best of 3: 207 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAlphabetical())\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "305\n",
      "331\n",
      "327\n",
      "316\n",
      "1 loops, best of 3: 212 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerFreqOrdered())\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "8\n",
      "15\n",
      "8\n",
      "1 loops, best of 3: 198 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerFixedOrder(list(reversed(string.ascii_lowercase))))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategy 1: letters in dictionary frequency order\n",
    "When we're looking at letter frequencies, we've been looking at running English text. But the words being preseted to the player aren't drawn randomly from novels: they're taken from the dictionary. That means our frequencies are off because we're looking at the wrong distribution of words.\n",
    "\n",
    "For example, 'e' and 't' are common in running text because words like 'the' occur very frequently. But 'the' only occurs once in the dictionary. Let's sample letters from the dictionary and see if that makes a difference."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "DICT_COUNTS = collections.Counter(''.join(WORDS))\n",
    "DICT_LETTERS_IN_ORDER = [p[0] for p in DICT_COUNTS.most_common()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'e': 60732, 's': 47997, 'i': 45470, 'a': 38268, 'r': 37522, 'n': 36868, 't': 36009, 'o': 31004, 'l': 26902, 'c': 21061, 'd': 20764, 'u': 17682, 'g': 16560, 'p': 15240, 'm': 13855, 'h': 11662, 'b': 9866, 'y': 7877, 'f': 7430, 'v': 5325, 'k': 4829, 'w': 4757, 'x': 1425, 'q': 1020, 'z': 979, 'j': 965})"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DICT_COUNTS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['e', 's', 'i', 'a', 'r', 'n', 't', 'o', 'l', 'c', 'd', 'u', 'g', 'p', 'm', 'h', 'b', 'y', 'f', 'v', 'k', 'w', 'x', 'q', 'z', 'j']\n",
      "['e', 't', 'a', 'o', 'i', 'h', 'n', 's', 'r', 'd', 'l', 'u', 'm', 'w', 'c', 'y', 'f', 'g', 'p', 'b', 'v', 'k', 'x', 'j', 'q', 'z']\n"
     ]
    }
   ],
   "source": [
    "print(DICT_LETTERS_IN_ORDER)\n",
    "print(LETTERS_IN_ORDER)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The letter orders are certainly different. Let's see if it make the player more effective than the ~30% of `FreqOrder`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "463\n"
     ]
    }
   ],
   "source": [
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerFixedOrder(DICT_LETTERS_IN_ORDER))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For convenience, we can wrap this new behaviour up in its own class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerDictOrder(PlayerFixedOrder):\n",
    "    def __init__(self):\n",
    "        super().__init__(DICT_LETTERS_IN_ORDER)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "474\n",
      "460\n",
      "490\n",
      "467\n",
      "1 loops, best of 3: 220 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerDictOrder())\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That was worth it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategy 2: paying attention the target word\n",
    "The strategies so far haven't paid any attention to the target word. Can we use information about the target to help refine our guesses?\n",
    "\n",
    "We've just seen that sampling letters from the dictionary works better than other approaches. But if we're presented with a seven letter word, we don't need to pay attention to the letter occurences in three- or ten-letter words. \n",
    "\n",
    "Let's build our first \"adaptive\" player, one that adapts its behaviour to what's happening in this game. \n",
    "\n",
    "The idea is that the player will hold internally a set of `candidate_words` that could match what it knows about the target. It will then count the letters in that set and pick the most frequent, but so-far-unguessed, letter.\n",
    "\n",
    "When the player is created, the it's give `all_words` it can chose from, but `candidate_words` is non-existent. As soon as it's given a word, it can filter `all_words` so that `candidate_words` are just those words with the same length as the `discovered` word. From the `candidate_words`, the player can create its own set of `ordered_letters`. Guesses are pulled from the `ordered_letters` the same as before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveLength:\n",
    "    def __init__(self, words):\n",
    "        self.all_words = words\n",
    "        self.candidate_words = None\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        if not self.candidate_words:\n",
    "            self.set_ordered_letters(len(discovered))\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def set_ordered_letters(self, word_len):\n",
    "        self.candidate_words = [w for w in self.all_words if len(w) == word_len]\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "452\n"
     ]
    }
   ],
   "source": [
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveLength(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "480\n",
      "444\n",
      "504\n",
      "463\n",
      "1 loops, best of 3: 18.5 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveLength(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's a bit better, but quite a lot slower. Can we improve the performance, to offset the cost of the slower game?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategy 3: using discovered letters\n",
    "Once we've made some successful guesses, we know more about the `target` and we can use that information to further filter the `candiate_words`. For instance, if we know the `target` is seven letters with an 'e' in the second and fourth positions, there are probably very few candiate words to choose from.\n",
    "\n",
    "The challenge here is to filter the `candidate_words` depending on the letter pattern. That's non-trivial, so we'll look at how to do that bit first.\n",
    "\n",
    "(This matching is the sort of thing that regular expressions are designed for, but I think there are enough new ideas in this material so far. See the end of this notebook for implementations of the adaptive players that use regexes.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Matching\n",
    "The problem: given a pattern and a target word, determine if the word matches the pattern. The return value of `match` should be a Boolean.\n",
    "\n",
    "A target is a sequence of letters. \n",
    "\n",
    "A pattern is a sequence of either a letter or an underscore.\n",
    "\n",
    "A target matches a pattern if the corresponding elements of both match.\n",
    "\n",
    "* A target letter always matches an underscore.\n",
    "\n",
    "* A target letter matches a pattern letter if they are the same.\n",
    "\n",
    "If any element doesn't match, the whole match fails.\n",
    "\n",
    "If the target and pattern are different lengths, the match fails.\n",
    "\n",
    "The built-in `zip` will allow us to pair up the elements of the pattern and target."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def match(pattern, target):\n",
    "    if len(pattern) != len(target):\n",
    "        return False\n",
    "    for m, c in zip(pattern, target):\n",
    "        if m == '_':\n",
    "            # true\n",
    "            pass\n",
    "        elif m != '_' and m == c:\n",
    "            # true\n",
    "            pass\n",
    "        else:\n",
    "            return False\n",
    "    return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match('__pp_', 'happy')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match('__pp_', 'hippo')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match('__pp_', 'hello')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match('__pp_', 'happier')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That all seems to be working. Let's put it in a `player` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveIncludedLetters:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered):\n",
    "        self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w)]\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]\n",
    "        \n",
    "    def match(self, pattern, target):\n",
    "        if len(pattern) != len(target):\n",
    "            return False\n",
    "        for m, c in zip(pattern, target):\n",
    "            if m == '_':\n",
    "                # true\n",
    "                pass\n",
    "            elif m != '_' and m == c:\n",
    "                # true\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "981\n"
     ]
    }
   ],
   "source": [
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveIncludedLetters(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "982\n",
      "987\n",
      "984\n",
      "982\n",
      "1 loops, best of 3: 51.7 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveIncludedLetters(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quite an improvement!\n",
    "\n",
    "But let's see if we can do better."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategy 4: using wrong guesses\n",
    "If we make a guess that's wrong, we can also use that to eliminate `candidate_words`. If we know the `target` doesn't contain an 'e', we can eliminate all `candidate_words` that contain an 'e'. If we also know that the word contains an 'e' in the third positon, we can also eliminate all words that contain and 'e' in any other position.\n",
    "\n",
    "This requires an different verion of `match`, so that a word matches a pattern if an underscore in the pattern does not match any of the known-incorrect letters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def match_exclusion(pattern, target, excluded=None):\n",
    "    if not excluded:\n",
    "        excluded = ''\n",
    "    if len(pattern) != len(target):\n",
    "        return False\n",
    "    for m, c in zip(pattern, target):\n",
    "        if m == '_' and c not in excluded:\n",
    "            # true\n",
    "            pass\n",
    "        elif m != '_':\n",
    "            # true\n",
    "            pass\n",
    "        else:\n",
    "            return False\n",
    "    return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match_exclusion('__pp_', 'happy', 'x')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match_exclusion('__pp_', 'happy', 'a')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match_exclusion('__pp_', 'happy', 'p')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "match_exclusion('__pp_', 'happy', 'hp')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveExcludedLetters:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered, missed)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        attempted_letters = list(set(l.lower() for l in discovered + missed if l in string.ascii_letters))\n",
    "        self.candidate_words = [w for w in self.candidate_words if self.match_exclusion(discovered, w, attempted_letters)]\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]\n",
    "        \n",
    "    def match_exclusion(self, pattern, target, excluded=None):\n",
    "        if not excluded:\n",
    "            excluded = ''\n",
    "        if len(pattern) != len(target):\n",
    "            return False\n",
    "        for m, c in zip(pattern, target):\n",
    "            if m == '_' and c not in excluded:\n",
    "                # true\n",
    "                pass\n",
    "            elif m != '_':\n",
    "                # true\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "737\n"
     ]
    }
   ],
   "source": [
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveExcludedLetters(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "735\n",
      "748\n",
      "742\n",
      "748\n",
      "1 loops, best of 3: 1min 4s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveExcludedLetters(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's better than the non-adaptive players, but not as good as the `IncludedLetters` player. But we could combine the two approaches. Will that work better?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategy 5: using both correct and wrong guesses\n",
    "Not much to say. Let's just merge the two previous approaches."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptivePattern:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered, missed)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        attempted_letters = list(set(l.lower() for l in discovered + missed if l in string.ascii_letters))\n",
    "        self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w, attempted_letters)]\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]\n",
    "        \n",
    "    def match(self, pattern, target, excluded=None):\n",
    "        if not excluded:\n",
    "            excluded = ''\n",
    "        if len(pattern) != len(target):\n",
    "            return False\n",
    "        for m, c in zip(pattern, target):\n",
    "            if m == '_' and c not in excluded:\n",
    "                # true\n",
    "                pass\n",
    "            elif m != '_' and m == c:\n",
    "                # true\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "993\n"
     ]
    }
   ],
   "source": [
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptivePattern(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "990\n",
      "995\n",
      "992\n",
      "994\n",
      "1 loops, best of 3: 47.1 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptivePattern(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DRYing it up\n",
    "You've probably noticed some duplicate code above. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptive:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered, missed)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        pass\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() \n",
    "                                     for l in ''.join(self.candidate_words) + string.ascii_lowercase \n",
    "                                     if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]\n",
    "\n",
    "    def match(self, pattern, target, excluded=None):\n",
    "        if not excluded:\n",
    "            excluded = ''\n",
    "        if len(pattern) != len(target):\n",
    "            return False\n",
    "        for m, c in zip(pattern, target):\n",
    "            if m == '_' and c not in excluded:\n",
    "                # true\n",
    "                pass\n",
    "            elif m != '_' and m == c:\n",
    "                # true\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveLength(PlayerAdaptive):\n",
    "    def __init__(self, words):\n",
    "        super().__init__(words)\n",
    "        self.word_len = None\n",
    "        self.ordered_letters = None\n",
    "        \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        if not self.word_len:\n",
    "            self.word_len = len(discovered)\n",
    "            self.candidate_words = [w for w in self.candidate_words if len(w) == self.word_len]\n",
    "    \n",
    "    def set_ordered_letters(self):\n",
    "        if not self.ordered_letters:\n",
    "            super().set_ordered_letters()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveIncludedLetters(PlayerAdaptive):\n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveExcludedLetters(PlayerAdaptive):\n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        if missed:\n",
    "            empty_target = '_' * len(discovered)\n",
    "            self.candidate_words = [w for w in self.candidate_words if self.match(empty_target, w, missed)]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptivePattern(PlayerAdaptive):\n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        attempted_letters = [l for l in discovered if l != '_'] + missed\n",
    "        self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w, attempted_letters)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "472\n",
      "460\n",
      "462\n",
      "484\n",
      "1 loops, best of 3: 17 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveLength(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "988\n",
      "985\n",
      "987\n",
      "988\n",
      "1 loops, best of 3: 49.3 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveIncludedLetters(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "575\n",
      "611\n",
      "583\n",
      "607\n",
      "1 loops, best of 3: 5min 10s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveExcludedLetters(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "990\n",
      "992\n",
      "995\n",
      "991\n",
      "1 loops, best of 3: 39.1 s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptivePattern(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "puffy ['p', 'u', '_', '_', 'y'] ['s', 'e', 'a', 'o', 'i', 'm', 'l', 'n', 'r', 't']\n",
      "jar ['_', 'a', 'r'] ['t', 'p', 'g', 'w', 'd', 'm', 'b', 'y', 'f', 'o']\n",
      "fate ['_', 'a', '_', 'e'] ['l', 'r', 'm', 'p', 's', 'g', 'd', 'k', 'v', 'b']\n",
      "robs ['_', 'o', 'b', 's'] ['e', 'a', 't', 'h', 'g', 'f', 'l', 'c', 'm', 'j']\n"
     ]
    }
   ],
   "source": [
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptivePattern(WORDS))\n",
    "    g.play_game()\n",
    "    if not g.game_won:\n",
    "        print(g.target, g.discovered, g.wrong_letters)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Better strategy 6: divide and conquer\n",
    "This is a general approach to solving big problems: divide the candidate set into two equal halves, so that a simple test can discard half the candidates. \n",
    "\n",
    "For Hangman, we want to guess the letter that will eliminate half the `candidate_words`. For each letter that's present in all of the candidate words, score the letter +1 for every word it appears in, and -1 for every word it doesn't appear in. The closer the total is to zero, the closer letter is to being in half the `candidate_words`. We then pick the unguesses letter with the score closest to zero.\n",
    "\n",
    "As the `PlayerAdaptivePattern` seems to work well, we'll use that to keep track of the `candidate_words`. This variant changes the order of the letters, so it's a rewrite of `set_ordered_letters()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveSplit(PlayerAdaptivePattern):\n",
    "    def set_ordered_letters(self):\n",
    "        def letter_diff(l):\n",
    "            total = 0\n",
    "            for w in self.candidate_words:\n",
    "                if l in w:\n",
    "                    total += 1\n",
    "                else:\n",
    "                    total -= 1\n",
    "            return total\n",
    "            # return abs(sum(1 if l in w else -1 for w in self.candidate_words))\n",
    "        possible_letters = set(''.join(self.candidate_words))\n",
    "        letter_diffs = [(l, letter_diff(l)) for l in possible_letters]\n",
    "        self.ordered_letters = [p[0] for p in sorted(letter_diffs, key=lambda p: p[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113\n",
      "114\n",
      "131\n",
      "132\n",
      "1 loops, best of 3: 2min 28s per loop\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "wins = 0\n",
    "for _ in range(1000):\n",
    "    g = Game(random.choice(WORDS), player=PlayerAdaptiveSplit(WORDS))\n",
    "    g.play_game()\n",
    "    if g.game_won:\n",
    "        wins += 1\n",
    "print(wins)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oh.\n",
    "\n",
    "Why is this happening?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## See below for the regex-using versions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveIncludedLettersRegex:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered):\n",
    "        exp = re.compile('^' + ''.join(discovered).replace('_', '.') + '$')\n",
    "        self.candidate_words = [w for w in self.candidate_words if exp.match(w)]\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveExcludedLettersRegex:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(missed)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, missed):\n",
    "        if missed:\n",
    "            exp = re.compile('^[^' + ''.join(missed) + ']*$')\n",
    "            self.candidate_words = [w for w in self.candidate_words if exp.match(w)]\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "re.match('^[^xaz]*$', 'happy')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptivePatternRegex:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered, missed)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        attempted_letters = list(set(l.lower() for l in discovered + missed if l in string.ascii_letters))\n",
    "        if attempted_letters:\n",
    "            exclusion_pattern = '[^' + ''.join(attempted_letters) + ']'\n",
    "        else:\n",
    "            exclusion_pattern = '.'\n",
    "        exp = re.compile('^' + ''.join(discovered).replace('_', exclusion_pattern) + '$')\n",
    "        self.candidate_words = [w for w in self.candidate_words if exp.match(w)]\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() for l in ''.join(self.candidate_words) if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveRegex:\n",
    "    def __init__(self, words):\n",
    "        self.candidate_words = words\n",
    "        \n",
    "    def guess(self, discovered, missed, lives):\n",
    "        self.filter_candidate_words(discovered, missed)\n",
    "        self.set_ordered_letters()\n",
    "        return [l for l in self.ordered_letters if l not in discovered + missed][0]\n",
    "    \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        pass\n",
    "        \n",
    "    def set_ordered_letters(self):\n",
    "        counts = collections.Counter(l.lower() \n",
    "                                     for l in ''.join(self.candidate_words) + string.ascii_lowercase \n",
    "                                     if l in string.ascii_letters)\n",
    "        self.ordered_letters = [p[0] for p in counts.most_common()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveLengthRegex(PlayerAdaptiveRegex):\n",
    "    def __init__(self, words):\n",
    "        super().__init__(words)\n",
    "        self.word_len = None\n",
    "        self.ordered_letters = None\n",
    "        \n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        if not self.word_len:\n",
    "            self.word_len = len(discovered)\n",
    "            self.candidate_words = [w for w in self.candidate_words if len(w) == self.word_len]\n",
    "    \n",
    "    def set_ordered_letters(self):\n",
    "        if not self.ordered_letters:\n",
    "            super().set_ordered_letters()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveIncludedLettersRegex(PlayerAdaptiveRegex):\n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        exp = re.compile('^' + ''.join(discovered).replace('_', '.') + '$')\n",
    "        self.candidate_words = [w for w in self.candidate_words if exp.match(w)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptiveExcludedLettersRegex(PlayerAdaptiveRegex):\n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        if missed:\n",
    "            exp = re.compile('^[^' + ''.join(missed) + ']*$')\n",
    "            self.candidate_words = [w for w in self.candidate_words if exp.match(w)]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class PlayerAdaptivePatternRegex(PlayerAdaptiveRegex):\n",
    "    def filter_candidate_words(self, discovered, missed):\n",
    "        attempted_letters = [l for l in discovered if l != '_'] + missed\n",
    "        if attempted_letters:\n",
    "            exclusion_pattern = '[^' + ''.join(attempted_letters) + ']'\n",
    "        else:\n",
    "            exclusion_pattern = '.'\n",
    "        exp = re.compile('^' + ''.join(discovered).replace('_', exclusion_pattern) + '$')\n",
    "        self.candidate_words = [w for w in self.candidate_words if exp.match(w)]"
   ]
  }
 ],
 "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.5.2+"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}