![]() The anagram dictionary creator takes about a half a second on my machine. Print "Dictionary loading time:",(time()-t)įoundwords = set(findwords(rack, anadict)) If len(set(word) - lets) = 0 and len(word) > 2 and len(word) """ Lets = set('abcdefghijklmnopqrstuvwxyz\n') The first makes the anagram dictionary and the second is the actual scrabble cheating program.Īnagram dictionary creator code f = open('/usr/share/dict/words') I implemented the algorithm in two parts. Performing a binary search is O(log(N)) so this will be very fast. For a 7-letter rack, there is a maximum of 120 unique scrabble-valid combinations of the letters. Then I can just take combinations of the rack letters and do a binary search for each one in the anagram dictionary to see if there is a match. ![]() For the example I'm using the entry would be aekst skate takes Each entry has the sorted version of the sorted version of the anagrams and then the anagrams themselves. I created an anagram dictionary as a text file with the format where on each line constitutes an entry. For instance, 'takes' and 'skate' are anagrams of each other because they are both equal to 'aekst' when sorted. An anagram dictionary takes each word in a dictionary and groups them if they are anagrams. Since what you are really doing is looking for anagrams, it makes sense to use an anagram dictionary. With the three changes above, the code was about 3x faster from my simple tests. Which, even without the changes in the previous step, is faster than what you currently have. Return all( [unt(letter) >= unt(letter) \ I changed it to the following: def spellable(word, rack): However, this has to be accompanied by a change to spellable. However, I found it was even faster to just check if the first letter of the word was in the rack before calling spellable: rackset = frozenset(rack) The purpose of using the sets at all was to weed out a lot of the ones that don't have any shot at all and thereby give a speed-up. However, you are also getting a pretty major slow down from making a set out of every word. Next, Ferran suggested a variable for the rack set, which is a good idea. Of course, you could just create your own dictionary beforehand from the original that removes those that aren't valid: those that aren't the right length or have letters outsize of a-z. Also, there could be a problem with the last word in the list because it probably won't have a new line at the end of it, but on my computer the last word is études which won't be found with our method anyway. Remember that word is unstripped of new line characters in my comparisons. It eliminates words that are too long or short before we get too far in the process. This gives the biggest improvement of all of my suggested changes. Return (word.strip() for word in open(filename) \Īnd call it as words = word_reader('/usr/share/dict/words', len(rack)) Without going too far from your basic code, here are some fairly simple optimizations:įirst, change your word reader to be: def word_reader(filename, L): Scored = ((score_word(word), word) for word in words if set(word).issubset(set(rack)) and len(word) > 1 and spellable(word, rack)) Words = word_reader('/usr/share/dict/words') I've tried to optimize it as much as I know how (using generators instead of list comprehensions made a big difference), and I've run out of ideas. Right now it's taking about a second on a list of about 200K words. I have no real need to improve it, it's just for fun.
0 Comments
Leave a Reply. |