From: Christopher Winslett Date: 2007-07-10T07:23:22+09:00 Subject: [QUIZ][SOLUTION] Hangman (#130) -- Guesser Class --------------060900030106070401040809 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit My "Guesser" class will guess the letter and the position based on the words that are "x" characters in length. It will suggest a particular letter in a particular position that has the highest frequency. It will filter out words based on characters known in a particular position and characters known not to be in a particular position. It can find almost all words within 20 guesses and many is less than 10; I've found that words of 6 characters in length are typically the toughest to discover with the position and character guessing method. Once it filters down to one word it will return the word in a string. If it doesn't have a word that matches, it will begin guessing based on random character guesses from the first unknown position. Note: I did use Unix command "egrep" to quickly parse the word database. You can fix that in the "load_database" method. Example Usage based on the term "writhe" # # # @known = string of characters; "-" is the wildcard # @unknown = array of array of letters that letters # that have been ruled out # @file = Dictionary File - one word per line # # require 'guesser' guess = Guesser.new(:known => "------", :unknown => [[], [], [], [], [], []] :file => "words.txt") guess.list.length # Total Words search from with six characters guess.guess # Returns a guess of [letter, position] [:s, 5] # position is based on an index of 0 # I've found the best guess to be "s" # for the last character because it rules out # all plurals guess.list.length # The method "guess" created a list of words from the 11153 # database. # All the words are 6 characters in length. # Not necessary, just showing you how it filters down # the words guess.create_regex # Returns the Regexp used to find the word /^.{5}$/ # Not necessary, just for example purposes guess.unknown = [[], [], [], [], [], ["s"]] # Insert an "s" to signify # that it is not # in that position of the # word. guess.guess # Filters the words and guesses again [:e, 4] # guess.list.length # Filtered by the method "guess" to have fewer words. 7045 # Notice 4108 words did not have the last letter "s" guess.create_regex # Returns the Regexp used to find the list /^.{4}[^s]$/ # guess.unknown = [[], [], [], [], ["e"], ["s"]] guess.guess [:e, 5] guess.list.length # Guess filters out 2400 more words based on the # Regexp 4568 # Note that the "list" is a filtering list and cannot # be recreated in full # once it has been filtered. That was a conscious # decision to preserve resources. guess.create_regex # Not necessary, just shows for example purposes. /^.{4}[^e][^s]$/ guess.known = "-----e".split(//) # Must be submitted as an array. # Converts the string "-----e" into an # array # Probably need to fix this in the # class guess.guess [:l, 4] Eventually (16 guesses down the road), once the word is filtered down it would look something list this: guess.unknown = [["s", "t"], ["l", "o"], [], ["i", "a", "u", "o", "e", "n", "r"], ["e", "l", "i", "u"], ["s"]] guess.known = "---the".split(//) guess.create_regex /^[^st][^lo].{1}[t][h][e]$/ guess.guess "writhe" --------------060900030106070401040809 Content-Type: application/octet-stream; name="guesser.rb" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="guesser.rb" Y2xhc3MgR3Vlc3NlcgogIGF0dHJfYWNjZXNzb3IgOmxlbmd0aCwgOmtub3duLCA6bGlzdCwg OnVua25vd24sIDpub3Rfd29yZHMgCgogIGRlZiBpbml0aWFsaXplKGFyZ3MpCiAgICBAbGVu Z3RoID0gYXJnc1s6a25vd25dLmxlbmd0aCAKICAgIEBrbm93biA9IGFyZ3NbOmtub3duXS5z cGxpdCgvLykKICAgIEB1bmtub3duID0gYXJnc1s6dW5rbm93bl0gCiAgICBAbm90X3dvcmRz ID0gW10KICAgIEBmaWxlID0gYXJnc1s6ZmlsZV0gfHwgIndvcmRzLnR4dCIgICAgCiAgZW5k CgoKICBkZWYgZ3Vlc3MKICAgIEBsaXN0Lm5pbD8gPyBsb2FkX2RhdGFiYXNlIDogZmlsdGVy CgogICAgaWYgQGxpc3QubGVuZ3RoID4gMQogICAgICBsZXR0ZXJfYXJyYXkgPSBjb25zdHJ1 Y3RfbGV0dGVyX2FycmF5IAoKICAgICAgQGxpc3QuZWFjaCB7IHwgd29yZCB8IHdvcmQuc3Bs aXQoLy8pLmVhY2hfd2l0aF9pbmRleCB7IHwgbGV0dGVyLCBpbmRleCB8IGxldHRlcl9hcnJh eVtpbmRleF1bbGV0dGVyLnRvX3N5bV0gKz0gMSBpZiBsZXR0ZXIgPX4gL1tBLVphLXpdLyB9 IH0KCiAgICAgIGJlc3RfZ3Vlc3MgPSBBcnJheS5uZXcKCiAgICAgIGxldHRlcl9hcnJheS5l YWNoX3dpdGhfaW5kZXggZG8gfCBsZXR0ZXJzLCBpbmRleCB8CiAgICAgICAgbGV0dGVyID0g bGV0dGVycy5zb3J0X2J5IHsgfCBsZXR0ZXIsIHZhbHVlIHwgdmFsdWUgfS5yZXZlcnNlLmZp cnN0CiAgICAgICAgYmVzdF9ndWVzcyA8PCBbbGV0dGVyWzBdLCBAa25vd25baW5kZXhdID09 ICctJyA/IGxldHRlclsxXSA6IDBdCiAgICAgIGVuZAoKICAgICAgbGV0dGVyX2d1ZXNzID0g YmVzdF9ndWVzcy5zb3J0X2J5IHsgfCBndWVzcywgbnVtYmVyIHwgbnVtYmVyIH0ubGFzdAog ICAgICBbbGV0dGVyX2d1ZXNzWzBdLCBiZXN0X2d1ZXNzLnJpbmRleChsZXR0ZXJfZ3Vlc3Mp XQogICAgZWxzaWYgQGxpc3QubGVuZ3RoID09IDEKICAgICAgQGxpc3RbMF0KICAgIGVsc2UK ICAgICAga2V5ID0gQGtub3duLmluZGV4KCItIikKICAgICAgbGV0dGVyID0gbmlsCgogICAg ICBsb29wIGRvCiAgICAgICAgbGV0dGVyID0gcmFuZG9tX2NoYXIKICAgICAgICBicmVhayBp ZiBAdW5rbm93bltrZXldLmluZGV4KGxldHRlcikubmlsPwogICAgICBlbmQKCiAgICAgIFts ZXR0ZXIsIGtleV0KICAgIGVuZAogIGVuZAoKICBkZWYgZmlsdGVyCiAgICByZWdleCA9IGNy ZWF0ZV9yZWdleAogICAgQGxpc3QgPSBAbGlzdC5kZWxldGVfaWYgeyB8IGl0ZW0gfCAhKGl0 ZW0gPX4gcmVnZXgpIH0KICBlbmQKCiAgZGVmIGNvbnN0cnVjdF9sZXR0ZXJfYXJyYXkKICAg IGxldHRlcl9hcnJheSA9IEFycmF5Lm5ldwogICAgMC51cHRvKEBsZW5ndGgtMSkgZG8gfCBp IHwKICAgICAgbGV0dGVyX2FycmF5W2ldID0gSGFzaC5uZXcKICAgICAgKCJhIi4uInoiKS50 b19hLmVhY2ggeyB8IGtleSB8IGxldHRlcl9hcnJheVtpXVtrZXkudG9fc3ltXSA9IDAgfQog ICAgICAoIkEiLi4iWiIpLnRvX2EuZWFjaCB7IHwga2V5IHwgbGV0dGVyX2FycmF5W2ldW2tl eS50b19zeW1dID0gMCB9CiAgICBlbmQKICAgIGxldHRlcl9hcnJheQogIGVuZAoKICBkZWYg Y3JlYXRlX3JlZ2V4CiAgICByZWdleCA9ICcnCiAgICB1bmtub3duX2xlbmd0aCA9IDAKICAg IEBrbm93bi5lYWNoX3dpdGhfaW5kZXggZG8gfCBsZXR0ZXIsIGluZGV4IHwKICAgICAgaWYg bGV0dGVyID09ICItIgogICAgICAgIGlmIEB1bmtub3duW2luZGV4XS5sZW5ndGggPT0gMAog ICAgICAgICAgdW5rbm93bl9sZW5ndGggKz0gMQogICAgICAgICAgcmVnZXggPDwgIi57I3t1 bmtub3duX2xlbmd0aH19IiBpZiBpbmRleCArIDEgPT0gQGtub3duLmxlbmd0aCAgJiYgdW5r bm93bl9sZW5ndGggPiAwCgllbHNlCgkgIHJlZ2V4IDw8ICIueyN7dW5rbm93bl9sZW5ndGh9 fSIgaWYgdW5rbm93bl9sZW5ndGggPiAwCiAgICAgICAgICByZWdleCA8PCAiW14je0B1bmtu b3duW2luZGV4XS5tYXAgeyB8IGxldHRlciB8IGxldHRlciB9fV0iCgkgIHVua25vd25fbGVu Z3RoID0gMAoJZW5kCiAgICAgIGVsc2UKICAgICAgICByZWdleCA8PCAiLnsje3Vua25vd25f bGVuZ3RofX0iIGlmIHVua25vd25fbGVuZ3RoID4gMAogICAgICAgIHJlZ2V4IDw8ICJbI3ts ZXR0ZXJ9XSIKCXVua25vd25fbGVuZ3RoID0gMAogICAgICBlbmQKICAgIGVuZAoKICAgIGlm IEBub3Rfd29yZHMgJiYgIEBub3Rfd29yZHMubGVuZ3RoID4gMAogICAgICBbUmVnZXhwLm5l dygiXiN7cmVnZXh9JCIpXSA8PCBSZWdleHAubmV3KCJeKCN7QG5vdF93b3Jkcy5qb2luKCd8 Jyl9KSQiKQogICAgZWxzZQogICAgICBSZWdleHAubmV3KCJeI3tyZWdleH0kIikKICAgIGVu ZAogIGVuZAoKICBwcml2YXRlCiAgZGVmIHJhbmRvbV9jaGFyKCBsZW49MSApCiAgICAgIGNo YXJzID0gKCJhIi4uInoiKS50b19hCiAgICAgIGNoYXIgPSAiIgogICAgICAxLnVwdG8obGVu KSB7IHxpfCBjaGFyIDw8IGNoYXJzW3JhbmQoY2hhcnMuc2l6ZS0xKV0gIH0KICAgICAgcmV0 dXJuIGNoYXIKICBlbmQKCiAgZGVmIGxvYWRfZGF0YWJhc2UKICAgIEBsaXN0ID0gYGVncmVw ICN7Y3JlYXRlX3JlZ2V4LnNvdXJjZX0gI3tAZmlsZX1gLnNwbGl0KC9cbi8pIAogIGVuZApl bmQK --------------060900030106070401040809--