From 07484b53aa43b00983f682a41e81e72d2c8e723c Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Tue, 2 Dec 2014 12:13:35 +0000 Subject: [PATCH] Now includes versions without reguar expressions --- Untitled0.ipynb | 216 +++++++++++++++++++++++------ hangman-better.ipynb | 322 ++++++++++++++++++++++++++++++++++++++++++- hangman2.html | 19 ++- 3 files changed, 508 insertions(+), 49 deletions(-) diff --git a/Untitled0.ipynb b/Untitled0.ipynb index 992afac..ff4a58e 100644 --- a/Untitled0.ipynb +++ b/Untitled0.ipynb @@ -1,7 +1,7 @@ { "metadata": { "name": "", - "signature": "sha256:a4f2510e4612d8ec6693f09edf9acc836f64b1078feac9000ff71e3ea775ee2f" + "signature": "sha256:796179cdb4347de4d86a7db09f3e024ef710983a025f30cfe2a424e9a755bc6b" }, "nbformat": 3, "nbformat_minor": 0, @@ -44,13 +44,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 3, + "prompt_number": 2, "text": [ "['Brian']" ] } ], - "prompt_number": 3 + "prompt_number": 2 }, { "cell_type": "code", @@ -66,13 +66,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 8, + "prompt_number": 3, "text": [ "True" ] } ], - "prompt_number": 8 + "prompt_number": 3 }, { "cell_type": "code", @@ -87,13 +87,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 6, + "prompt_number": 4, "text": [ "True" ] } ], - "prompt_number": 6 + "prompt_number": 4 }, { "cell_type": "code", @@ -107,13 +107,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 9, + "prompt_number": 5, "text": [ - "True" + "False" ] } ], - "prompt_number": 9 + "prompt_number": 5 }, { "cell_type": "code", @@ -130,13 +130,13 @@ { "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", @@ -167,7 +167,7 @@ "language": "python", "metadata": {}, "outputs": [], - "prompt_number": 22 + "prompt_number": 7 }, { "cell_type": "code", @@ -182,7 +182,7 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 21, + "prompt_number": 8, "text": [ "[8,\n", " 2,\n", @@ -587,7 +587,7 @@ ] } ], - "prompt_number": 21 + "prompt_number": 8 }, { "cell_type": "code", @@ -604,7 +604,7 @@ { "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", @@ -895,7 +895,7 @@ ] } ], - "prompt_number": 24 + "prompt_number": 9 }, { "cell_type": "code", @@ -913,7 +913,7 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 30, + "prompt_number": 10, "text": [ "{(7, 3): 42,\n", " (6, 9): 76,\n", @@ -1318,7 +1318,7 @@ ] } ], - "prompt_number": 30 + "prompt_number": 10 }, { "cell_type": "code", @@ -1332,13 +1332,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 35, + "prompt_number": 11, "text": [ "31" ] } ], - "prompt_number": 35 + "prompt_number": 11 }, { "cell_type": "code", @@ -1353,7 +1353,7 @@ { "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", @@ -1644,7 +1644,7 @@ ] } ], - "prompt_number": 27 + "prompt_number": 12 }, { "cell_type": "code", @@ -1661,7 +1661,7 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 63, + "prompt_number": 13, "text": [ "{(7, 3): 42,\n", " (6, 9): 76,\n", @@ -2066,7 +2066,7 @@ ] } ], - "prompt_number": 63 + "prompt_number": 13 }, { "cell_type": "code", @@ -2083,7 +2083,7 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 65, + "prompt_number": 14, "text": [ "{(7, 3): 42,\n", " (6, 9): 76,\n", @@ -2488,7 +2488,7 @@ ] } ], - "prompt_number": 65 + "prompt_number": 14 }, { "cell_type": "code", @@ -2502,13 +2502,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 66, + "prompt_number": 15, "text": [ "True" ] } ], - "prompt_number": 66 + "prompt_number": 15 }, { "cell_type": "code", @@ -2526,12 +2526,12 @@ "output_type": "pyerr", "traceback": [ "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mKeyError\u001b[0m Traceback (most recent call last)", - "\u001b[1;32m\u001b[0m in \u001b[0;36m\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\u001b[0m in \u001b[0;36m\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", @@ -2547,13 +2547,13 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 69, + "prompt_number": 17, "text": [ "0" ] } ], - "prompt_number": 69 + "prompt_number": 17 }, { "cell_type": "code", @@ -2569,13 +2569,13 @@ { "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", @@ -2593,13 +2593,13 @@ { "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", @@ -2613,7 +2613,7 @@ { "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", @@ -2904,7 +2904,7 @@ ] } ], - "prompt_number": 75 + "prompt_number": 20 }, { "cell_type": "code", @@ -2918,7 +2918,7 @@ { "metadata": {}, "output_type": "pyout", - "prompt_number": 76, + "prompt_number": 21, "text": [ "[8,\n", " 2,\n", @@ -3323,7 +3323,141 @@ ] } ], - "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", diff --git a/hangman-better.ipynb b/hangman-better.ipynb index eaf1665..20a12e0 100644 --- a/hangman-better.ipynb +++ b/hangman-better.ipynb @@ -1,7 +1,7 @@ { "metadata": { "name": "", - "signature": "sha256:545958b09bd5e8fa505a87efb9adac0a47f5192bcc21e705711935beec6eb83c" + "signature": "sha256:32b3b300745f022158bfde0b3fc0a50b11d36551211371d50140e9f9d2a7b8e1" }, "nbformat": 3, "nbformat_minor": 0, @@ -2001,6 +2001,324 @@ ], "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, @@ -2008,7 +2326,7 @@ "language": "python", "metadata": {}, "outputs": [], - "prompt_number": 53 + "prompt_number": 72 } ], "metadata": {} diff --git a/hangman2.html b/hangman2.html index 0a092a1..a11a9df 100644 --- a/hangman2.html +++ b/hangman2.html @@ -52,11 +52,15 @@ # 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 @@ -117,7 +121,7 @@ We've got a list of valid words. # 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`) @@ -125,7 +129,7 @@ Three data items: * `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) --- @@ -140,9 +144,12 @@ Three data items: ## Hints 1. Remember `.join()` ? -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? -- 2.34.1