{
"metadata": {
"name": "",
- "signature": "sha256:a4f2510e4612d8ec6693f09edf9acc836f64b1078feac9000ff71e3ea775ee2f"
+ "signature": "sha256:796179cdb4347de4d86a7db09f3e024ef710983a025f30cfe2a424e9a755bc6b"
},
"nbformat": 3,
"nbformat_minor": 0,
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 3,
+ "prompt_number": 2,
"text": [
"['Brian']"
]
}
],
- "prompt_number": 3
+ "prompt_number": 2
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 8,
+ "prompt_number": 3,
"text": [
"True"
]
}
],
- "prompt_number": 8
+ "prompt_number": 3
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 6,
+ "prompt_number": 4,
"text": [
"True"
]
}
],
- "prompt_number": 6
+ "prompt_number": 4
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 9,
+ "prompt_number": 5,
"text": [
- "True"
+ "False"
]
}
],
- "prompt_number": 9
+ "prompt_number": 5
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 18,
+ "prompt_number": 6,
"text": [
"[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]"
]
}
],
- "prompt_number": 18
+ "prompt_number": 6
},
{
"cell_type": "code",
"language": "python",
"metadata": {},
"outputs": [],
- "prompt_number": 22
+ "prompt_number": 7
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 21,
+ "prompt_number": 8,
"text": [
"[8,\n",
" 2,\n",
]
}
],
- "prompt_number": 21
+ "prompt_number": 8
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 24,
+ "prompt_number": 9,
"text": [
"[[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],\n",
" [49,\n",
]
}
],
- "prompt_number": 24
+ "prompt_number": 9
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 30,
+ "prompt_number": 10,
"text": [
"{(7, 3): 42,\n",
" (6, 9): 76,\n",
]
}
],
- "prompt_number": 30
+ "prompt_number": 10
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 35,
+ "prompt_number": 11,
"text": [
"31"
]
}
],
- "prompt_number": 35
+ "prompt_number": 11
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 27,
+ "prompt_number": 12,
"text": [
"[[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],\n",
" [49,\n",
]
}
],
- "prompt_number": 27
+ "prompt_number": 12
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 63,
+ "prompt_number": 13,
"text": [
"{(7, 3): 42,\n",
" (6, 9): 76,\n",
]
}
],
- "prompt_number": 63
+ "prompt_number": 13
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 65,
+ "prompt_number": 14,
"text": [
"{(7, 3): 42,\n",
" (6, 9): 76,\n",
]
}
],
- "prompt_number": 65
+ "prompt_number": 14
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 66,
+ "prompt_number": 15,
"text": [
"True"
]
}
],
- "prompt_number": 66
+ "prompt_number": 15
},
{
"cell_type": "code",
"output_type": "pyerr",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyError\u001b[0m Traceback (most recent call last)",
- "\u001b[1;32m<ipython-input-67-fb0bb5c8abf1>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m 1\u001b[0m \u001b[0md\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0md\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m99\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
+ "\u001b[1;32m<ipython-input-16-fb0bb5c8abf1>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m 1\u001b[0m \u001b[0md\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0md\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m99\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mKeyError\u001b[0m: 99"
]
}
],
- "prompt_number": 67
+ "prompt_number": 16
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 69,
+ "prompt_number": 17,
"text": [
"0"
]
}
],
- "prompt_number": 69
+ "prompt_number": 17
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 71,
+ "prompt_number": 18,
"text": [
"Counter({'e': 52876, 't': 37842, 'a': 34376, 'o': 33200, 'n': 28378, 'h': 27803, 's': 26432, 'i': 26366, 'r': 24304, 'd': 18349, 'l': 16854, 'u': 13070, 'm': 11055, 'w': 10508, 'c': 10172, 'y': 8976, 'f': 8785, 'g': 7733, 'p': 6652, 'b': 5883, 'v': 4367, 'I': 3774, 'k': 3465, 'H': 1244, 'T': 1139, 'S': 762, 'A': 761, 'W': 758, 'M': 732, 'x': 541, 'B': 479, 'Y': 455, 'q': 406, 'j': 338, 'C': 327, 'O': 312, 'N': 304, 'L': 291, 'E': 235, 'D': 214, 'R': 204, 'F': 190, 'P': 183, 'G': 154, 'z': 147, 'J': 114, 'V': 85, 'K': 78, 'U': 46, 'Q': 20, 'X': 8, 'Z': 2})"
]
}
],
- "prompt_number": 71
+ "prompt_number": 18
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 74,
+ "prompt_number": 19,
"text": [
"[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]"
]
}
],
- "prompt_number": 74
+ "prompt_number": 19
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 75,
+ "prompt_number": 20,
"text": [
"[[8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8],\n",
" [49,\n",
]
}
],
- "prompt_number": 75
+ "prompt_number": 20
},
{
"cell_type": "code",
{
"metadata": {},
"output_type": "pyout",
- "prompt_number": 76,
+ "prompt_number": 21,
"text": [
"[8,\n",
" 2,\n",
]
}
],
- "prompt_number": 76
+ "prompt_number": 21
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "s1 = 'hello'\n",
+ "s2 = '__lk_'"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 27
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "list(zip(s1, s2))"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "metadata": {},
+ "output_type": "pyout",
+ "prompt_number": 23,
+ "text": [
+ "[('h', '_'), ('e', '_'), ('l', 'l'), ('l', 'l'), ('o', '_')]"
+ ]
+ }
+ ],
+ "prompt_number": 23
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "def match_positive(pattern, target):\n",
+ " if len(pattern) != len(target):\n",
+ " return False\n",
+ " for m, c in zip(pattern, target):\n",
+ " if m != '_' and m != c:\n",
+ " return False\n",
+ " return True"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 31
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "match_positive('he__o', 'hello')"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "metadata": {},
+ "output_type": "pyout",
+ "prompt_number": 38,
+ "text": [
+ "True"
+ ]
+ }
+ ],
+ "prompt_number": 38
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "def match(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"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 56
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "match('__l_o', 'hello', 'def')"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "metadata": {},
+ "output_type": "pyout",
+ "prompt_number": 60,
+ "text": [
+ "False"
+ ]
+ }
+ ],
+ "prompt_number": 60
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "'_' == '_' and 'l' not in 'xyz'"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "metadata": {},
+ "output_type": "pyout",
+ "prompt_number": 48,
+ "text": [
+ "True"
+ ]
+ }
+ ],
+ "prompt_number": 48
},
{
"cell_type": "code",
{
"metadata": {
"name": "",
- "signature": "sha256:545958b09bd5e8fa505a87efb9adac0a47f5192bcc21e705711935beec6eb83c"
+ "signature": "sha256:32b3b300745f022158bfde0b3fc0a50b11d36551211371d50140e9f9d2a7b8e1"
},
"nbformat": 3,
"nbformat_minor": 0,
],
"prompt_number": 53
},
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "class PlayerAdaptiveNoRegex:\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",
+ " guessed_letters = [l.lower() for l in discovered + missed if l in string.ascii_letters]\n",
+ " return [l for l in self.ordered_letters if l not in guessed_letters][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 "
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 59
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "class PlayerAdaptiveLengthNoRegex(PlayerAdaptiveNoRegex):\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()"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 60
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "class PlayerAdaptiveIncludedLettersNoRegex(PlayerAdaptiveNoRegex):\n",
+ " def filter_candidate_words(self, discovered, missed):\n",
+ " self.candidate_words = [w for w in self.candidate_words if self.match(discovered, w)]"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 61
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "class PlayerAdaptiveExcludedLettersNoRegex(PlayerAdaptiveNoRegex):\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)] "
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 66
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "class PlayerAdaptivePatternNoRegex(PlayerAdaptiveNoRegex):\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)]"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [],
+ "prompt_number": 67
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "%%timeit\n",
+ "\n",
+ "wins = 0\n",
+ "for _ in range(1000):\n",
+ " g = Game(random.choice(WORDS), player=PlayerAdaptiveLengthNoRegex(WORDS))\n",
+ " g.play_game()\n",
+ " if g.game_won:\n",
+ " wins += 1\n",
+ "print(wins)"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "471\n",
+ "492"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "502"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "469"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "1 loops, best of 3: 16 s per loop\n"
+ ]
+ }
+ ],
+ "prompt_number": 69
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "%%timeit\n",
+ "\n",
+ "wins = 0\n",
+ "for _ in range(1000):\n",
+ " g = Game(random.choice(WORDS), player=PlayerAdaptiveIncludedLettersNoRegex(WORDS))\n",
+ " g.play_game()\n",
+ " if g.game_won:\n",
+ " wins += 1\n",
+ "print(wins)"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "978\n",
+ "979"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "983"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "979"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "1 loops, best of 3: 48 s per loop\n"
+ ]
+ }
+ ],
+ "prompt_number": 70
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "%%timeit\n",
+ "\n",
+ "wins = 0\n",
+ "for _ in range(1000):\n",
+ " g = Game(random.choice(WORDS), player=PlayerAdaptiveExcludedLettersNoRegex(WORDS))\n",
+ " g.play_game()\n",
+ " if g.game_won:\n",
+ " wins += 1\n",
+ "print(wins)"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "582\n",
+ "595"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "587"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "611"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "1 loops, best of 3: 4min 59s per loop\n"
+ ]
+ }
+ ],
+ "prompt_number": 71
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "%%timeit\n",
+ "\n",
+ "wins = 0\n",
+ "for _ in range(1000):\n",
+ " g = Game(random.choice(WORDS), player=PlayerAdaptivePatternNoRegex(WORDS))\n",
+ " g.play_game()\n",
+ " if g.game_won:\n",
+ " wins += 1\n",
+ "print(wins)"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "991\n",
+ "992"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "993"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "994"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "\n",
+ "1 loops, best of 3: 37.9 s per loop\n"
+ ]
+ }
+ ],
+ "prompt_number": 72
+ },
{
"cell_type": "code",
"collapsed": false,
"language": "python",
"metadata": {},
"outputs": [],
- "prompt_number": 53
+ "prompt_number": 72
}
],
"metadata": {}
# Hangman
-1. **Set a puzzle** <== here
+1. **Set a puzzle** ← here
2. Guess a word
3. Automatic player
4. Better strategies
+## Filtering the dictionary
+
+What's the best way to filter the dictionary of invalid words?
+
---
layout: true
# Representing the game state
-Three data items:
+Five data items:
* `target`, the target word: a `string`
* `discovered`, what's been found so far: a `list` of letters (each a length-one `string`)
* `guess`, the letter that's just been guessed: a length-one `string`
* `lives`, the lives remaining: an `int`
* `wrong_letters`, the incorrect guesses: a `list` (optional)
- * (but it makes the automated players easier if they don't have to track wrong guesses and therefore be made stateless)
+ * (but it makes the automated players easier if they don't have to track wrong guesses)
---
## Hints
1. Remember `<string>.join(<list>)` ?
-2. `input('prompt')` (or `input('prompt').strip().lower()[0]` )
-3. Walk over `target`, looking for `guess`. Explicit iteration (`for letter in target:`) or with a comprehension (`enumerate(target)`)
-4. `target[n] = guess`. Note that you need the numerical position, and you need all the positions for repeated words.
+2. `input('prompt')` (or `guess = input('prompt').strip().lower()[0]` )
+3. Walk over `target`, looking for `guess`.
+ * Explicit iteration (`for i in range(len(target)):`)
+ * With a comprehension (`[... for i, l in enumerate(target) if... ]`)
+4. `target[n] = guess`.
+ * Note that you need the numerical position, and you need *all* the positions for repeated letters.
5. How do you know the guess is wrong?