First bit of the A-level miscellany

[cas-master-teacher-training.git] / hangman / 02-hangman-guesser.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:eb35fa497310659186b8d082192529c5f3ce0083adaa1704282cce83da804db6"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Hangman 2: the guesser\n",
      "Note that we're not trying to do anything clever here. We're just trying to make something that makes a series of legal moves in the game and that sometimes might win. We want to get something that fits the player-sized hole when we put the setter and guesser together. The clever players come later. \n",
      "\n",
      "We also need to think about how to have the guesser interact with a human setter, so that it can play against a human. It won't get much use, but we should have it for completeness.\n",
      "\n",
      "But before we can build something that fits the hole, we need to understand what shape the hole is. What is the interface between the guesser and the setter?\n",
      "\n",
      "Spoiler space\n",
      "\n",
      ".\n",
      "\n",
      ".\n",
      "\n",
      ".\n",
      "\n",
      ".\n",
      "\n",
      ".\n",
      "\n",
      ".\n",
      "\n",
      "."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The guesser only really needs to do one thing: make a guess. We'll say that the setter passes in the complete state of the game (disovered template, lives remaining, and wrong letters guessed) and the guesser simply returns the guess.\n",
      "\n",
      "Someone needs to keep track of the incorrect guesses so that the guesser doesn't keep making the same wrong guess. As the setter is already keeping track of the rest of the state, it's probably easier if the setter also keeps track of the wrong letters. That might allow us to keep the guesser state-free, which will keep it simpler. "
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Getting a game state\n",
      "If we need the guesser to interact with a human, let's get it to read the game state from a human.\n",
      "\n",
      "Remember that we want to return two lists of characters, not two strings.\n",
      "\n",
      "We'll also not do any input validation. Life's too short (for this example)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def read_game():\n",
      "    discovered = input('Enter the discovered word: ')\n",
      "    missed = input('Enter the wrong guesses: ')\n",
      "    return list(discovered), list(missed)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "read_game()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the discovered word: __pp_\n"
       ]
      },
      {
       "name": "stdout",
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Enter the wrong guesses: xv\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "(['_', '_', 'p', 'p', '_'], ['x', 'v'])"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "That was easy."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Basic strategy\n",
      "\n",
      "Our first strategy is to simply guess the letters in order, with \"order\" defined as how often the letters appear in English running text. That means we need to read some English text and count the letters."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import string\n",
      "import collections"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `collections` standard library contains all sorts of fun stuff. The `Counter` object is very useful. Take a look at the documentation for what it does. We'll be using two features here: generate a `dict`-like thing of counts, and return the things in frequency order.\n",
      "\n",
      "First, let's read all the letters in *The Complete Works of Sherlock Holmes*."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "letter_counts = collections.Counter(l.lower() for l in open('../sherlock-holmes.txt').read() if l in string.ascii_letters)\n",
      "letter_counts"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "Counter({'e': 53111, 't': 38981, 'a': 35137, 'o': 33512, 'i': 30140, 'h': 29047, 'n': 28682, 's': 27194, 'r': 24508, 'd': 18563, 'l': 17145, 'u': 13116, 'm': 11787, 'w': 11266, 'c': 10499, 'y': 9431, 'f': 8975, 'g': 7887, 'p': 6835, 'b': 6362, 'v': 4452, 'k': 3543, 'x': 549, 'j': 452, 'q': 426, 'z': 149})"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now, let's get them listed in order."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "letter_counts.most_common()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 22,
       "text": [
        "[('e', 53111),\n",
        " ('t', 38981),\n",
        " ('a', 35137),\n",
        " ('o', 33512),\n",
        " ('i', 30140),\n",
        " ('h', 29047),\n",
        " ('n', 28682),\n",
        " ('s', 27194),\n",
        " ('r', 24508),\n",
        " ('d', 18563),\n",
        " ('l', 17145),\n",
        " ('u', 13116),\n",
        " ('m', 11787),\n",
        " ('w', 11266),\n",
        " ('c', 10499),\n",
        " ('y', 9431),\n",
        " ('f', 8975),\n",
        " ('g', 7887),\n",
        " ('p', 6835),\n",
        " ('b', 6362),\n",
        " ('v', 4452),\n",
        " ('k', 3543),\n",
        " ('x', 549),\n",
        " ('j', 452),\n",
        " ('q', 426),\n",
        " ('z', 149)]"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "letters_in_order = [p[0] for p in letter_counts.most_common()]\n",
      "letters_in_order"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "['e',\n",
        " 't',\n",
        " 'a',\n",
        " 'o',\n",
        " 'i',\n",
        " 'h',\n",
        " 'n',\n",
        " 's',\n",
        " 'r',\n",
        " 'd',\n",
        " 'l',\n",
        " 'u',\n",
        " 'm',\n",
        " 'w',\n",
        " 'c',\n",
        " 'y',\n",
        " 'f',\n",
        " 'g',\n",
        " 'p',\n",
        " 'b',\n",
        " 'v',\n",
        " 'k',\n",
        " 'x',\n",
        " 'j',\n",
        " 'q',\n",
        " 'z']"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Make a guess\n",
      "How to make a guess? We want to guess the most common letter that hasn't already been guessed. \n",
      "\n",
      "That means we want to filter the available letters by removing the ones already guessed, and then take the first letter of the ones that are left. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def make_guess(discovered, missed):\n",
      "    return [l for l in letters_in_order if l not in (discovered + missed)][0]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "make_guess(list('__pp_'), list('exv'))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 26,
       "text": [
        "'t'"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "...and that's it. We don't need to keep track of game end: the setting player can do that.\n",
      "\n",
      "It's easy to see how we could have different strategies, depending on the order of letters used in the `make_guess` procedure. But that's for next time."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}