Hangman Solving
Word Guessing Strategy 101
enough for two 82-width buffers (set-frame-size (selected-frame) 176 76)
The Goal
Write a program that plays the Hangman game. A description of the game can be found here.
The Problem
Your goal is to use a provided API to play Hangman efficiently. You need to guess a word using as few guesses as possible, and make no more than maxWrongGuesses incorrect guesses. You are writing the letter/word guessing strategy.
We would like you to use the provided Java APIs and to write your solution in Java or a JVM-based language. However, if are not comfortable with that, please feel free to use any other reasonably mainstream programming language (C++, Python, Ruby, etc.). If you do use another language, please make sure that your program can accept a dictionary file and a list of test words (that are in the dictionary). The output of the program should be a score for each test word and the average score across all test words. Also, if you don’t use Java, please provide build instructions if they are not straightforward.
Your score for a word will be:
right before exceeding maxWrongGuesses incorrect guesses
or
25 if you lost the game before guessing the word correctly.
You will need to write an implementation of the GuessingStrategy interface and some code to use your GuessingStrategy on a HangmanGame instance.
The pseudocode to run your strategy for a HangmanGame is:
// runs your strategy for the given game, then returns the score public int run(HangmanGame game, GuessingStrategy strategy) { while (game has not been won or lost) { ask the strategy for the next guess apply the next guess to the game } return game.score(); }
A trivial strategy might be to guess ‘A’, then ‘B’, then ‘C’, etc. until you’ve guessed every letter in the word (this will work great for “cab”!) or you’ve lost.
Every word you encounter will be a word from the words.txt file.
Example
For example, let’s say the word is FACTUAL.
Here is what a series of calls might look like:
HangmanGame game = new HangmanGame(“factual”, 4); // secret word is factual, 4 wrong guesses are allowed System.out.println(game); new GuessLetter(‘a’).makeGuess(game); System.out.println(game); new GuessWord(“natural”).makeGuess(game); System.out.println(game); new GuessLetter(‘x’).makeGuess(game); System.out.println(game); new GuessLetter(‘u’).makeGuess(game); System.out.println(game); new GuessLetter(‘l’).makeGuess(game); System.out.println(game); new GuessWord(“factual”).makeGuess(game); System.out.println(game);
The output would be:
-------; score=0; status=KEEP_GUESSING -A—A-; score=1; status=KEEP_GUESSING -A—A-; score=2; status=KEEP_GUESSING -A—A-; score=3; status=KEEP_GUESSING -A–UA-; score=4; status=KEEP_GUESSING -A–UAL; score=5; status=KEEP_GUESSING FACTUAL; score=5; status=GAME_WON
game.score() will be 5 in this case since there were 4 letter guesses and 1 incorrect word guess made.
Sample Data
As a baseline, here are scores for a reasonably good guessing strategy against a set of 15 random words. Your strategy will likely be better for some of the words and worse for other words, but the average score/word should be in the same ballpark.
COMAKER = 25 (was not able to guess the word before making more than 5 mistakes) CUMULATE = 9 ERUPTIVE = 5 FACTUAL = 9 MONADISM = 8 MUS = 25 (was not able to guess the word before making more than 5 mistakes) NAGGING = 7 OSES = 5 REMEMBERED = 5 SPODUMENES = 4 STEREOISOMERS = 2 TOXICS = 11 TRICHROMATS = 5 TRIOSE = 5 UNIFORMED = 5
Resources
You should have been provided with a zip file with source code and a dictionary file to get you started. If you were not sent this zip file, or you have any questions about the contents, please let us know right away.
The resources contain a dictionary file called words.txt. You can assume all words that your program will be tested with come from this dictionary file.
Judging
Your solution will be graded on the following criteria
- code quality, readability, and design. In terms of quality, please write your code as if it would eventually be pushed into production.
- performance (speed/memory footprint). We are more concerned with average time per game, so expensive one-time initialization is okay (as long as it’s not too egregious)
- total score for ~1000 random words, compared to the total score of several reference implementations for the same ~1000 words (max wrong guesses is typically set to 5)
python3 hangman.py -t data/words.txt `cat data/2.txt | tr “\n” ” “`
./hangman.py -t data/words.txt `cat data/2.txt | tr “\n” ” “`
nada
get 3.3.0
http://www.python.org/download/releases/3.3.0/
ignore factual/ __pycache__/ python basic class template thing I made
Convert their java to Python as first step.
Sanity test java->py.
$ python3 src/HangmanGame.py -------; score=0; status=KEEP_GUESSING -A—A-; score=1; status=KEEP_GUESSING -A—A-; score=2; status=KEEP_GUESSING -A—A-; score=3; status=KEEP_GUESSING -A–UA-; score=4; status=KEEP_GUESSING -A–UAL; score=5; status=KEEP_GUESSING FACTUAL; score=5; status=GAME_WON
Output == good
File reading first. Then dump into set?
- yes.
Pick next letter based on what’s already been guessed.
Uh… I need a game runner first… done.
And… this is working. -------; score=1; status=KEEP_GUESSING —T—; score=2; status=KEEP_GUESSING -A-T-A-; score=3; status=KEEP_GUESSING -A-T-A-; score=4; status=KEEP_GUESSING -A-T-A-; score=5; status=KEEP_GUESSING -A-T-A-; score=6; status=KEEP_GUESSING -A-T-A-; score=7; status=KEEP_GUESSING -A-T-A-; score=25; status=GAME_LOST FACTUAL = 25
Make it so!
run function like so: public int run(HangmanGame game, GuessingStrategy strategy)
Make it DBG(printable, prefix=”“, printFlag=True)
Use guessedSoFar to figure out word candidates.
Probably should regex it.
Pretty stupid regex builder, but it works. We’ll see if we need speed later.
build letter frequency info from possible word list
use it instead of common english letters
Hey. I didn’t lose this time!
$ ./hangman.py 1.7 MiB Possibles: 23208 RUBEOLA GUESS: E -------; score=1; status=KEEP_GUESSING Possibles: 23208 RUBEOLA GUESS: S -------; score=2; status=KEEP_GUESSING Possibles: 23208 RUBEOLA GUESS: I -------; score=3; status=KEEP_GUESSING Possibles: 23208 RUBEOLA GUESS: A -A—A-; score=4; status=KEEP_GUESSING Possibles: 300 LASHKAR GUESS: L -A—AL; score=5; status=KEEP_GUESSING Possibles: 46 LACUNAL GUESS: T -A-T-AL; score=6; status=KEEP_GUESSING Possibles: 7 LACTEAL GUESS: C -ACT-AL; score=7; status=KEEP_GUESSING Possibles: 3 LACTEAL GUESS: U -ACTUAL; score=8; status=KEEP_GUESSING Possibles: 2 TACTUAL GUESS: F FACTUAL; score=9; status=GAME_WON FACTUAL = 9
Reject words containing failed guesses
getIncorrectlyGuessedLetters() regex set… [badletters]+
Any matches, throw out.
Rejecting based on incorrect letters
- may need to update for incorrect words when word guessing goes in
- been TODO’d in code
regex to remove words containing incorrect letter choice bugged
- but working partially… it removes some.
$ ./hangman.py 1.7 MiB Possibles: 23208 Pick: BOOZIERset() GUESS: E -------; score=1; status=KEEP_GUESSING [E]+ Possibles: 22401 Pick: BOOZIER{‘E’} GUESS: S -------; score=2; status=KEEP_GUESSING [ES]+ Possibles: 19745 Pick: BOOZIER{‘E’, ‘S’} GUESS: I -------; score=3; status=KEEP_GUESSING [EIS]+ Possibles: 19241 Pick: BOOZIER{‘E’, ‘I’, ‘S’} GUESS: A -A—A-; score=4; status=KEEP_GUESSING [EIS]+ Possibles: 279 Pick: VATICAL{‘E’, ‘I’, ‘S’} GUESS: L -A—AL; score=5; status=KEEP_GUESSING [EIS]+ Possibles: 45 Pick: VATICAL{‘E’, ‘I’, ‘S’} GUESS: T -A-T-AL; score=6; status=KEEP_GUESSING [EIS]+ Possibles: 7 Pick: CANTHAL{‘E’, ‘I’, ‘S’} GUESS: C -ACT-AL; score=7; status=KEEP_GUESSING [EIS]+ Possibles: 3 Pick: LACTEAL{‘E’, ‘I’, ‘S’} GUESS: U -ACTUAL; score=8; status=KEEP_GUESSING [EIS]+ Possibles: 2 Pick: TACTUAL{‘E’, ‘I’, ‘S’} GUESS: F FACTUAL; score=9; status=GAME_WON FACTUAL = 9
Ah, match(). Don’t use match. Use search().
Currently only guesses at words if it’s possible to win that way.
- location of dictionary
- list of words
- max guesses
$ ./hangman.py -h usage: hangman.py [-h] [-g GUESSES] filename word [word …]
positional arguments: filename read dictionary in from file word list of words to play hangman on
optional arguments: -h, –help show this help message and exit -g GUESSES, –guesses GUESSES max number of wrong guesses
Reuse strategy.
Also:
- average score
Their words: COMAKER = 25 (was not able to guess the word before making more than 5 mistakes) CUMULATE = 9 ERUPTIVE = 5 FACTUAL = 9 MONADISM = 8 MUS = 25 (was not able to guess the word before making more than 5 mistakes) NAGGING = 7 OSES = 5 REMEMBERED = 5 SPODUMENES = 4 STEREOISOMERS = 2 TOXICS = 11 TRICHROMATS = 5 TRIOSE = 5 UNIFORMED = 5 average: 8.666666666
$ ./hangman.py words.txt COMAKER CUMULATE ERUPTIVE FACTUAL MONADISM MUS NAGGING OSES REMEMBERED SPODUMENES STEREOISOMERS TOXICS TRICHROMATS TRIOSE UNIFORMED COMAKER = 12 CUMULATE = 9 ERUPTIVE = 8 FACTUAL = 10 MONADISM = 6 MUS = 25 NAGGING = 5 OSES = 4 REMEMBERED = 5 SPODUMENES = 4 STEREOISOMERS = 3 TOXICS = 7 TRICHROMATS = 5 TRIOSE = 7 UNIFORMED = 10 average: 7.999999999999999
Yay. 0.77777777777 better!
Seems a bit slow.
15 words: real 0m6.904s user 0m6.815s sys 0m0.086s
1000 would take… 7 or 8 minutes.
Get timing on function level… util.Timer is ready for action!
Now start using it.
$ time ./hangman.py words.txt MUS Namespace(filename=’words.txt’, guesses=5, verbose=False, word=[‘MUS’]) Strategy init took 0.191967964 sec. Strategery took 0.197170019 sec. Strategery took 0.010432959 sec. Strategery took 0.008641958 sec. Strategery took 0.007431984 sec. Strategery took 0.006187916 sec. Strategery took 0.006028175 sec. Strategery took 0.005857944 sec. Game took 0.242306948 sec. MUS = 25 average: 25.0 Total: 0.260428905 sec.
So, the first guess takes way too long… 75% of the run is the first guess.
But the timing works, so #014 is done.
Speed up first strategy run.
- don’t do regexes, since they’re useless. We haven’t guessed anything yet.
- just check word lengths
Slightly better.
previous: Strategery took 0.197170019 sec. now: Strategery took 0.163403034 sec.
The possible words update takes pretty much all the strategy time. Update took 0.155512094 sec. Strategery took 0.164095163 sec.
Update took 0.004542828 sec. Strategery took 0.010727882 sec.
Update took 0.003679991 sec. Strategery took 0.008900166 sec.
Update took 0.003553867 sec. Strategery took 0.007694006 sec.
Update took 0.003237009 sec. Strategery took 0.006378174 sec.
Update took 0.002988100 sec. Strategery took 0.006038904 sec.
Update took 0.002842903 sec. Strategery took 0.005592108 sec.
Iterations over the set isn’t the problem. ITERATION took 0.014471054 sec. But still, don’t really want to do that every time… do you?
Maybe: Divide words up into different sets based on length. Possible words tree, basically.
foo = defaultdict(set) foo[secretWordLen] <– just the possible words of that length
Better. Namespace(filename=’words.txt’, guesses=5, verbose=False, word=[‘MUS’]) Strategy init took 0.162680149 sec.
Update took 0.000102043 sec. Strategery took 0.005481005 sec.
Update took 0.001863003 sec. Strategery took 0.005516052 sec.
Update took 0.001174927 sec. Strategery took 0.003688097 sec.
Update took 0.000879049 sec. Strategery took 0.002399921 sec.
Update took 0.000616074 sec. Strategery took 0.001395941 sec.
Update took 0.000432968 sec. Strategery took 0.000988960 sec.
Update took 0.000344038 sec. Strategery took 0.000798941 sec. Game took 0.020552158 sec. MUS = 25 average: 25.0 Total: 0.020627975 sec.
Before: ./hangman.py words.txt COMAKER CUMULATE ERUPTIVE FACTUAL MONADISM MUS NAGGING OSES REMEMBERED SPODUMENES STEREOISOMERS TOXICS TRICHROMATS TRIOSE UNIFORMED … real 0m6.904s user 0m6.815s sys 0m0.086s After: ./hangman.py words.txt COMAKER CUMULATE ERUPTIVE FACTUAL MONADISM MUS NAGGING OSES REMEMBERED SPODUMENES STEREOISOMERS TOXICS TRICHROMATS TRIOSE UNIFORMED … real 0m3.490s user 0m3.458s sys 0m0.029s
Twice as fast. And update isn’t the long pole anymore.
Putting words on the command line won’t cut it for when we move to large sets.
- two files. One dictionary, one of words to be played.
Estimate for 1000 games: Average game time: 0.219625076 sec. (15 game sample) so 1000 would be 219 seconds. 3.6 minutes.
letterStrategy() is the long pole now. It’s 2 for loops. One to get the letter frequencies and one to chose which of those to use.
$ python3 -m cProfile -s cumulative hangman.py words.txt 100.txt … 19949500 function calls (19942752 primitive calls) in 25.122 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function) 8/1 0.000 0.000 25.122 25.122 {built-in method exec} 1 0.014 0.014 25.122 25.122 hangman.py:4(<module>) 1 0.002 0.002 25.102 25.102 hangman.py:43(main) 101 0.008 0.000 24.812 0.246 hangman.py:24(run) 726 0.038 0.000 24.787 0.034 FrequencyStrategy.py:57(nextGuess) 594 4.213 0.007 20.595 0.035 FrequencyStrategy.py:95(letterStrategy) …
Can we use bulit-in functions instead of for loops?
http://www.python.org/doc/essays/list2str.html “If you feel the need for speed, go for built-in functions - you can’t beat a loop written in C.”
So the letter frequency list is taking all the time. Average game time goes down to 0.04 when I switch back to popular letters.
map() + list comprehension brought the time down some, at the cost of extra memory. Old: 594 4.213 0.007 20.595 0.035 FrequencyStrategy.py:95(letterStrategy) Average game time: 0.219625076 sec. New: 590 0.054 0.000 9.721 0.016 FrequencyStrategy.py:95(letterStrategy) Average game time: 0.137980131 sec.
Brings estimate for 1000 games to 2.2 minutes. Actual for 100 games is 13s.
Initial guesses are taking the vast majority of time, so move to part 3.
http://stackoverflow.com/questions/9245638/select-random-lines-from-a-file-in-bash
sort -R words.txt | head -n 100 >100.txt Damn. “Invalid option -R”. Guess that’s Linux only.
This works for one line: head -$((${RANDOM} % `wc -l < words.txt` + 1)) words.txt | tail -1
But not for >1.
Eh. Just do it in python CLI.
- 100.txt
- 1000.txt
Estimate for 1000 games to 2.2 minutes. Actual for 100 games is 13s. Make it faster.
Moved to dev branch in case this goes horribly wrong.
Do some strategizing in the init.
Pre-make sets based on what the initial guesses will be.
E.g. A: set of all words length 5 B: set of all words length 5 containing most popular letter in set A
- but it’s based on position, so.. hm…
C: set of all words length 5 NOT containing most popular letter in set A Possibly also the 4 sets for guess 2.
Also pre-make letter frequencies.
And cache all guess results along the way in every game just in case another game uses it.
- To Do: [4/4]
- [X] WordSet class
- [X] copy()
- [X] updated()
- Words has been culled. Redo frequency.
- [X] allWords -> WordSet
- Would need to make WordSet a class so defaultdict worked right…
- [X] possibleWords -> WordSet
- [X] remove letter freq gen from strat. Use WordSet’s.
- [X] WordSet class
Pausing To Do list to note speed gain: $ time python3 hangman.py words.txt 15.txt … average: 7.267326732673272 Average game time: 0.052958725 sec.
real 0m6.356s user 0m6.295s sys 0m0.058s
So 1000 will now take ~1 min. Yay!
Back to work…
- To Do: [3/3]
- [X] cache WordSet for each guess
- 1.9 sec for 15 words (5 cache hits, but those aren’t used yet)
- [X] look in cache for match
- 1.85 sec for 15 words
- 4.3 sec for 100
- Average game time: 0.032850029 sec.
- 1000 games in ~32 sec
- [X] combine cache & allWords?
- I think this removes need for firstUpdatePossibleWords()
- Hm… this makes each game take long…
- Wait. Nevermind. I was silly. Time is the same.
- [X] cache WordSet for each guess
Just ran 1000 for real for the first time. average: 7.987012987012973 Average game time: 0.014038171 sec.
real 0m15.202s user 0m15.119s sys 0m0.077s
Very nice…
- To Do 3: [2/2]
- [X] pre-guess first level (fail for most popular letter)
- [X] Only do it for non-small lists.
- Don’t need to bother if the only possible word is “ETHYLENEDIAMINETETRAACETATES”
- [X] make letterStrategy() not need game
- it only uses game for getAllGuessedLetters()
- make it just take a set instead
- it only uses game for getAllGuessedLetters()
- [X] freebie
- [X] Only do it for non-small lists.
- [X] Push to master branch
- [X] pre-guess first level (fail for most popular letter)
Hm… impressive gains for 15 words, but 1000 is less impressive. Guess that makes sense.
1000 words w/ pre-seeded-first-guess-miss cache: average: 7.9560439560439455 Average game time: 0.013550419 sec.
real 0m14.987s user 0m14.904s sys 0m0.078s
Don’t guess most popular letter…
Instead guess the letter that would halve the possibilities. i.e. binary search hangman
…if that’s possible. I haven’t printed out the letter counters in a long time.
Current, “choose most frequent letter” strategy: average: 8.042957042957035 Average game time: 0.014179471 sec. real 0m15.650s
And, no so great. average: 14.666666666666668
Maybe first 2 use that, the rest use most common? average: 8.441558441558433 Average game time: 0.013310668 sec. real 0m14.986s
So apparently gunning for 50% wrong chance instead of best chance of being right increases your score. Who’ve thunk.
Not much increase in speed, either, so… remove it.
orderedLetters = wordSet.letterFreq.most_common() if guessesLeft > 2:
target = len(wordSet) // 2 orderedLetters.sort(key = lambda lc: abs(lc[1]-target))
for letter, _ in orderedLetters:
is guessing words worth it?
Try only guessing words when there’s only 1 word to guess.
Current: average: 7.913086913086897 Average game time: 0.014154551 sec. real 0m15.641s
Almost Only Letters strat: average: 8.219780219780185 Average game time: 0.014710151 sec. real 0m16.322s
Nope. Guessing words is worth it, apparently. Leave it.
Add it… -v and -vv in use
Same words, different scores sometimes. 5 runs of 15 word list: COMAKER = 12 10 12 25 10 CUMULATE = 9 9 9 9 9 ERUPTIVE = 8 8 8 8 8 FACTUAL = 10 10 10 10 10 MONADISM = 6 6 6 6 6 MUS = 25 25 25 25 25 NAGGING = 4 4 4 4 4 OSES = 4 4 4 4 4 REMEMBERED = 4 4 4 4 4 SPODUMENES = 4 5 5 5 5 STEREOISOMERS = 3 3 3 3 3 TOXICS = 10 11 11 11 11 TRICHROMATS = 5 5 5 5 5 TRIOSE = 11 7 7 8 7 UNIFORMED = 9 10 10 9 10
Suspect it’s due to unordered nature of sets…
- sorted the words before wordStrategy picked one, but that’s not (all of) it.
It guesses different letters sometimes too. GUESS: E R I A T S M K O COMAKER = 9
GUESS: E R I A T S L M K N O C COMAKER = 12
Ah. It’s the collections.Counter I use for letterFreq… That’s unordered.
- see ‘debug output’.
Easy way to sort? sorted(wordSet.letterFreq.most_common, key = lambda lc: abs(lc[1]-target))
Works. How much speed does it cost? How much do I care about stable game scores? Unsorted: average: 7.913086913086897 Average game time: 0.014154551 sec. real 0m15.641s Sorted a-z: average: 8.013986013985999 Average game time: 0.014091464 sec. real 0m15.522s Sorted z-a: average: 7.8011988011987885 Average game time: 0.013920768 sec. real 0m15.491s
So for my 1000 words, z-a is better… 100? unsorted: average: 7.584158415841589 average: 7.910891089108916 z-a: average: 7.198019801980203 a-z: average: 7.584158415841589
All 173529 words? unsorted: average: 7.773973076397922 Average game time: 0.003772665 sec. real 11m0.143s a-z: average: 7.82038633535348 Average game time: 0.003799100 sec. real 11m5.142s z-a: average: 7.740837213597154 Average game time: 0.003757779 sec. real 10m57.319s
So I guess it’s Z-A…
GUESS: E num: 23208 letters: [(‘E’, 15273), (‘S’, 12338), (‘I’, 11028), (‘A’, 10830), (‘R’, 10516), (‘N’, 8545), (‘T’, 8034), (‘O’, 7993), (‘L’, 7946), (‘D’, 5995), (‘U’, 5722), (‘C’, 5341), (‘G’, 4590), (‘P’, 4308), (‘M’, 4181), (‘H’, 3701), (‘B’, 3292), (‘Y’, 2564), (‘F’, 2115), (‘K’, 2100), (‘W’, 1827), (‘V’, 1394), (‘Z’, 611), (‘X’, 504), (‘J’, 412), (‘Q’, 301)] GUESS: R num: 6712 letters: [(‘E’, 6712), (‘R’, 3483), (‘S’, 3466), (‘D’, 2837), (‘I’, 2700), (‘A’, 2424), (‘L’, 2234), (‘T’, 2010), (‘N’, 1785), (‘O’, 1763), (‘U’, 1597), (‘C’, 1405), (‘P’, 1146), (‘H’, 1100), (‘M’, 1023), (‘G’, 924), (‘B’, 892), (‘K’, 596), (‘F’, 581), (‘W’, 561), (‘V’, 403), (‘Y’, 261), (‘Z’, 180), (‘X’, 144), (‘Q’, 114), (‘J’, 113)] GUESS: I num: 1821 letters: [(‘E’, 1821), (‘R’, 1821), (‘I’, 874), (‘A’, 620), (‘L’, 572), (‘T’, 551), (‘S’, 544), (‘O’, 441), (‘U’, 420), (‘N’, 398), (‘C’, 358), (‘P’, 334), (‘D’, 299), (‘H’, 296), (‘M’, 263), (‘G’, 244), (‘B’, 235), (‘K’, 192), (‘F’, 185), (‘W’, 175), (‘V’, 99), (‘Y’, 48), (‘Z’, 44), (‘J’, 27), (‘Q’, 25), (‘X’, 13)] GUESS: A num: 947 letters: [(‘E’, 947), (‘R’, 947), (‘A’, 415), (‘L’, 350), (‘S’, 323), (‘T’, 306), (‘O’, 294), (‘U’, 273), (‘C’, 238), (‘N’, 203), (‘H’, 178), (‘P’, 177), (‘D’, 154), (‘B’, 151), (‘M’, 127), (‘G’, 120), (‘W’, 92), (‘F’, 85), (‘K’, 80), (‘V’, 48), (‘Y’, 37), (‘Z’, 17), (‘Q’, 14), (‘J’, 11), (‘X’, 7)] GUESS: S num: 99 letters: [(‘A’, 99), (‘E’, 99), (‘R’, 99), (‘S’, 26), (‘T’, 26), (‘L’, 25), (‘C’, 20), (‘G’, 20), (‘D’, 19), (‘O’, 17), (‘M’, 17), (‘P’, 16), (‘N’, 15), (‘B’, 12), (‘K’, 12), (‘Y’, 12), (‘H’, 9), (‘V’, 8), (‘F’, 7), (‘U’, 6), (‘W’, 5), (‘Q’, 1), (‘X’, 1)] GUESS: L num: 73 letters: [(‘A’, 73), (‘E’, 73), (‘R’, 73), (‘L’, 21), (‘T’, 20), (‘G’, 17), (‘D’, 17), (‘C’, 15), (‘M’, 15), (‘O’, 14), (‘N’, 14), (‘B’, 11), (‘K’, 10), (‘P’, 10), (‘Y’, 8), (‘H’, 7), (‘V’, 7), (‘F’, 6), (‘U’, 5), (‘W’, 3), (‘X’, 1)] GUESS: D num: 52 letters: [(‘A’, 52), (‘E’, 52), (‘R’, 52), (‘D’, 15), (‘G’, 13), (‘M’, 13), (‘T’, 13), (‘N’, 12), (‘C’, 11), (‘K’, 9), (‘O’, 9), (‘B’, 8), (‘H’, 7), (‘P’, 6), (‘F’, 5), (‘V’, 5), (‘U’, 5), (‘Y’, 5), (‘W’, 3)] GUESS: G num: 37 letters: [(‘A’, 37), (‘E’, 37), (‘R’, 37), (‘G’, 11), (‘N’, 11), (‘M’, 10), (‘T’, 9), (‘C’, 8), (‘K’, 8), (‘H’, 7), (‘O’, 7), (‘B’, 5), (‘P’, 4), (‘V’, 4), (‘U’, 4), (‘Y’, 4), (‘F’, 3), (‘W’, 1)] GUESS: C num: 26 letters: [(‘A’, 26), (‘E’, 26), (‘R’, 26), (‘C’, 8), (‘K’, 8), (‘M’, 8), (‘H’, 6), (‘T’, 6), (‘B’, 5), (‘N’, 5), (‘P’, 4), (‘O’, 3), (‘U’, 3), (‘Y’, 3), (‘F’, 2), (‘V’, 2), (‘W’, 1)] GUESS: K num: 5 letters: [(‘C’, 5), (‘R’, 5), (‘A’, 5), (‘E’, 5), (‘K’, 2), (‘H’, 2), (‘O’, 2), (‘M’, 2), (‘P’, 1), (‘T’, 1)] GUESS: O num: 2 letters: [(‘C’, 2), (‘R’, 2), (‘A’, 2), (‘E’, 2), (‘K’, 2), (‘O’, 2), (‘M’, 1)] GUESS: M num: 1 letters: [(‘C’, 1), (‘R’, 1), (‘A’, 1), (‘E’, 1), (‘K’, 1), (‘O’, 1), (‘M’, 1)] COMAKER = 12
GUESS: E num: 23208 letters: [(‘E’, 15273), (‘S’, 12338), (‘I’, 11028), (‘A’, 10830), (‘R’, 10516), (‘N’, 8545), (‘T’, 8034), (‘O’, 7993), (‘L’, 7946), (‘D’, 5995), (‘U’, 5722), (‘C’, 5341), (‘G’, 4590), (‘P’, 4308), (‘M’, 4181), (‘H’, 3701), (‘B’, 3292), (‘Y’, 2564), (‘F’, 2115), (‘K’, 2100), (‘W’, 1827), (‘V’, 1394), (‘Z’, 611), (‘X’, 504), (‘J’, 412), (‘Q’, 301)] GUESS: R num: 6712 letters: [(‘E’, 6712), (‘R’, 3483), (‘S’, 3466), (‘D’, 2837), (‘I’, 2700), (‘A’, 2424), (‘L’, 2234), (‘T’, 2010), (‘N’, 1785), (‘O’, 1763), (‘U’, 1597), (‘C’, 1405), (‘P’, 1146), (‘H’, 1100), (‘M’, 1023), (‘G’, 924), (‘B’, 892), (‘K’, 596), (‘F’, 581), (‘W’, 561), (‘V’, 403), (‘Y’, 261), (‘Z’, 180), (‘X’, 144), (‘Q’, 114), (‘J’, 113)] GUESS: I num: 1821 letters: [(‘R’, 1821), (‘E’, 1821), (‘I’, 874), (‘A’, 620), (‘L’, 572), (‘T’, 551), (‘S’, 544), (‘O’, 441), (‘U’, 420), (‘N’, 398), (‘C’, 358), (‘P’, 334), (‘D’, 299), (‘H’, 296), (‘M’, 263), (‘G’, 244), (‘B’, 235), (‘K’, 192), (‘F’, 185), (‘W’, 175), (‘V’, 99), (‘Y’, 48), (‘Z’, 44), (‘J’, 27), (‘Q’, 25), (‘X’, 13)] GUESS: A num: 947 letters: [(‘R’, 947), (‘E’, 947), (‘A’, 415), (‘L’, 350), (‘S’, 323), (‘T’, 306), (‘O’, 294), (‘U’, 273), (‘C’, 238), (‘N’, 203), (‘H’, 178), (‘P’, 177), (‘D’, 154), (‘B’, 151), (‘M’, 127), (‘G’, 120), (‘W’, 92), (‘F’, 85), (‘K’, 80), (‘V’, 48), (‘Y’, 37), (‘Z’, 17), (‘Q’, 14), (‘J’, 11), (‘X’, 7)] GUESS: S num: 99 letters: [(‘R’, 99), (‘A’, 99), (‘E’, 99), (‘S’, 26), (‘T’, 26), (‘L’, 25), (‘C’, 20), (‘G’, 20), (‘D’, 19), (‘M’, 17), (‘O’, 17), (‘P’, 16), (‘N’, 15), (‘Y’, 12), (‘B’, 12), (‘K’, 12), (‘H’, 9), (‘V’, 8), (‘F’, 7), (‘U’, 6), (‘W’, 5), (‘Q’, 1), (‘X’, 1)] GUESS: L num: 73 letters: [(‘R’, 73), (‘A’, 73), (‘E’, 73), (‘L’, 21), (‘T’, 20), (‘D’, 17), (‘G’, 17), (‘C’, 15), (‘M’, 15), (‘N’, 14), (‘O’, 14), (‘B’, 11), (‘P’, 10), (‘K’, 10), (‘Y’, 8), (‘V’, 7), (‘H’, 7), (‘F’, 6), (‘U’, 5), (‘W’, 3), (‘X’, 1)] GUESS: D num: 52 letters: [(‘R’, 52), (‘A’, 52), (‘E’, 52), (‘D’, 15), (‘T’, 13), (‘G’, 13), (‘M’, 13), (‘N’, 12), (‘C’, 11), (‘K’, 9), (‘O’, 9), (‘B’, 8), (‘H’, 7), (‘P’, 6), (‘U’, 5), (‘V’, 5), (‘Y’, 5), (‘F’, 5), (‘W’, 3)] GUESS: G num: 37 letters: [(‘R’, 37), (‘A’, 37), (‘E’, 37), (‘G’, 11), (‘N’, 11), (‘M’, 10), (‘T’, 9), (‘C’, 8), (‘K’, 8), (‘H’, 7), (‘O’, 7), (‘B’, 5), (‘P’, 4), (‘U’, 4), (‘V’, 4), (‘Y’, 4), (‘F’, 3), (‘W’, 1)] GUESS: C num: 26 letters: [(‘R’, 26), (‘A’, 26), (‘E’, 26), (‘C’, 8), (‘K’, 8), (‘M’, 8), (‘T’, 6), (‘H’, 6), (‘B’, 5), (‘N’, 5), (‘P’, 4), (‘U’, 3), (‘Y’, 3), (‘O’, 3), (‘V’, 2), (‘F’, 2), (‘W’, 1)] GUESS: H num: 5 letters: [(‘A’, 5), (‘R’, 5), (‘C’, 5), (‘E’, 5), (‘H’, 2), (‘K’, 2), (‘M’, 2), (‘O’, 2), (‘P’, 1), (‘T’, 1)] COMAKER = 25
GUESS: E num: 23208 letters: [(‘E’, 15273), (‘S’, 12338), (‘I’, 11028), (‘A’, 10830), (‘R’, 10516), (‘N’, 8545), (‘T’, 8034), (‘O’, 7993), (‘L’, 7946), (‘D’, 5995), (‘U’, 5722), (‘C’, 5341), (‘G’, 4590), (‘P’, 4308), (‘M’, 4181), (‘H’, 3701), (‘B’, 3292), (‘Y’, 2564), (‘F’, 2115), (‘K’, 2100), (‘W’, 1827), (‘V’, 1394), (‘Z’, 611), (‘X’, 504), (‘J’, 412), (‘Q’, 301)] -----E-; score=1; status=KEEP_GUESSING GUESS: R num: 6712 letters: [(‘E’, 6712), (‘R’, 3483), (‘S’, 3466), (‘D’, 2837), (‘I’, 2700), (‘A’, 2424), (‘L’, 2234), (‘T’, 2010), (‘N’, 1785), (‘O’, 1763), (‘U’, 1597), (‘C’, 1405), (‘P’, 1146), (‘H’, 1100), (‘M’, 1023), (‘G’, 924), (‘B’, 892), (‘K’, 596), (‘F’, 581), (‘W’, 561), (‘V’, 403), (‘Y’, 261), (‘Z’, 180), (‘X’, 144), (‘Q’, 114), (‘J’, 113)] -----ER; score=2; status=KEEP_GUESSING GUESS: I num: 1821 letters: [(‘R’, 1821), (‘E’, 1821), (‘I’, 874), (‘A’, 620), (‘L’, 572), (‘T’, 551), (‘S’, 544), (‘O’, 441), (‘U’, 420), (‘N’, 398), (‘C’, 358), (‘P’, 334), (‘D’, 299), (‘H’, 296), (‘M’, 263), (‘G’, 244), (‘B’, 235), (‘K’, 192), (‘F’, 185), (‘W’, 175), (‘V’, 99), (‘Y’, 48), (‘Z’, 44), (‘J’, 27), (‘Q’, 25), (‘X’, 13)] -----ER; score=3; status=KEEP_GUESSING GUESS: A num: 947 letters: [(‘R’, 947), (‘E’, 947), (‘A’, 415), (‘L’, 350), (‘S’, 323), (‘T’, 306), (‘O’, 294), (‘U’, 273), (‘C’, 238), (‘N’, 203), (‘H’, 178), (‘P’, 177), (‘D’, 154), (‘B’, 151), (‘M’, 127), (‘G’, 120), (‘W’, 92), (‘F’, 85), (‘K’, 80), (‘V’, 48), (‘Y’, 37), (‘Z’, 17), (‘Q’, 14), (‘J’, 11), (‘X’, 7)] —A-ER; score=4; status=KEEP_GUESSING GUESS: T num: 99 letters: [(‘R’, 99), (‘E’, 99), (‘A’, 99), (‘T’, 26), (‘S’, 26), (‘L’, 25), (‘G’, 20), (‘C’, 20), (‘D’, 19), (‘M’, 17), (‘O’, 17), (‘P’, 16), (‘N’, 15), (‘Y’, 12), (‘K’, 12), (‘B’, 12), (‘H’, 9), (‘V’, 8), (‘F’, 7), (‘U’, 6), (‘W’, 5), (‘X’, 1), (‘Q’, 1)] —A-ER; score=5; status=KEEP_GUESSING GUESS: S num: 73 letters: [(‘R’, 73), (‘E’, 73), (‘A’, 73), (‘S’, 20), (‘C’, 18), (‘L’, 17), (‘G’, 16), (‘M’, 15), (‘P’, 14), (‘D’, 14), (‘O’, 13), (‘N’, 13), (‘Y’, 11), (‘K’, 11), (‘V’, 8), (‘B’, 8), (‘H’, 7), (‘U’, 5), (‘F’, 5), (‘W’, 3), (‘X’, 1), (‘Q’, 1)] —A-ER; score=6; status=KEEP_GUESSING GUESS: M num: 53 letters: [(‘R’, 53), (‘E’, 53), (‘A’, 53), (‘M’, 14), (‘L’, 14), (‘D’, 13), (‘G’, 13), (‘C’, 13), (‘N’, 12), (‘O’, 10), (‘K’, 9), (‘Y’, 8), (‘P’, 8), (‘V’, 7), (‘B’, 7), (‘H’, 5), (‘F’, 5), (‘U’, 4), (‘W’, 2), (‘X’, 1)] –MA-ER; score=7; status=KEEP_GUESSING GUESS: K num: 6 letters: [(‘R’, 6), (‘M’, 6), (‘E’, 6), (‘A’, 6), (‘K’, 3), (‘U’, 2), (‘O’, 2), (‘N’, 2), (‘H’, 2), (‘G’, 2), (‘D’, 1), (‘C’, 1)] –MAKER; score=8; status=KEEP_GUESSING GUESS: U num: 3 letters: [(‘M’, 3), (‘K’, 3), (‘E’, 3), (‘A’, 3), (‘R’, 3), (‘U’, 1), (‘O’, 1), (‘N’, 1), (‘C’, 1)] –MAKER; score=9; status=KEEP_GUESSING GUESS: O num: 2 letters: [(‘M’, 2), (‘K’, 2), (‘E’, 2), (‘A’, 2), (‘R’, 2), (‘O’, 1), (‘C’, 1)] -OMAKER; score=10; status=KEEP_GUESSING COMAKER; score=10; status=GAME_WON
Use one instead of 2.
Compact the one to see if it’s faster.
Before: 15: Average game time: 0.040141757 sec. real 0m1.996s 1000: Average game time: 0.014569002 sec. real 0m16.038s After: 15: Average game time: 0.037995275 sec. real 0m1.970s 1000: Average game time: 0.014188456 sec. real 0m15.639s After after: 15: Average game time: 0.034805250 sec. real 0m1.925s 1000: Average game time: 0.012961594 sec. real 0m14.435s
Make pretty!
- To Do [8/8]
- [X] HangmanGame
- [X] GuessFoo
- [X] util
- [X] WordSet
- [X] FrequencyStrategy
- ish
- Saving some for finale
- ish
- [X] hangman.py
- [X] ack TODO
- [X] catch assertion?
- I check game’s status instead.
Doesn’t seem to affect time much, changing that.
Install Python 3.3.0.
Explain options.
Explain how to switch to use file instead of list.
Explain strategy & optimization.
- [X] Spell check README.
- [X] Handle unable-to-guess-word better.
- actually I don’t need to. “Every word you encounter will be a word from the words.txt file.”
- but here’s the code if I want it later:
if len(self.possible) == 0 or self.possible.words == game.getIncorrectlyGuessedWords():
for letter in list(“ETAOINSRHDLUCMFYWGPBVKXQJZ”): if letter not in game.getAllGuessedLetters(): return GuessLetter(letter) el<current if goes here>
- [X] Remove DBG() and timing?
- that aren’t used
- [X] hangman
- [X] FrequencyStrategy
- that aren’t used
- [X] Clean it up.
- [X] TODO
- [X] hangman
- [X] FrequencyStrategy
- [X] template files
- [X] TODO
- [X] Move word lists into subdir.
- data/
- [X] Switch back to word-list
- [X] Send it.
Need some sort of cache decay so memory doesn’t keep going up. All-the-words game takes 600 MB. ../memusg python3 hangman.py -t words.txt words.txt
average score: 7.740837213597154 init took: 01.246516 sec. average game time: 00.003475 sec. total time: 605.927172 sec. memusg: peak=594832
Try set intersections instead of regex/remove for incorrect letters. updatePossibleWords() (just after cache check)
second pre-seed for seedCache:
#
#
Try not updating the letterFreq for guesses with a word set > N.
- Or only updating every other time.
- Or only updating if set has been reduced by more than half.
Switch to Go? Can’t really parallelize this in Python, but it’d be simple to in Go.
None.