An Anagram Solving Bot In Python

This article will detail how I made a bot in Python that can solve web-based anagram games. I wrote it for people with at least a beginner's grasp of Python and programming languages. I originally wrote it for a joint blog my friend and I were starting but it never got started. It is half a tutorial, half a 'look what I did!' post.

Any experienced developer knows that before you can run a program with an interface of bells and whistles, it is best to write a command-line version; reduce the problem to a command, and it becomes an algorithm. Therefore, before I made the bot itself, I wanted to make a method that solves anagrams, as many times as I wanted, whenever I wanted.

So given a string and a list of all valid words (something like Unix's /usr/share/dict/words), the function would return a list of all words that can be made from that letters in the string.

Looking around for examples of this method, everything I found was either too complicated or not written well, so I thought, "I could surely do this myself!" This is how I went about it.

I started with the method header:

def matches(anagram, wordlist, min=3):

The min variable will, by way of the ensuing code, prevent the method from returning words that are less than 3 letters. This is by default; the number changes if you call matches(myString, myList, #), where # is the custom minimum.

The general algorithm I eventually came up with was:

def matches(anagram, wordlist, min=3):
　for each word in wordlist:
　　temp_anagram = anagram # a sample of the anagram to use for this word
　　is_a_match = True # assume word can be created from anagram
　　for each letter in word:
　　　if temp_anagram does not contain character:
　　　　is_a_match = False
　　　else:
　　　　temp_anagram = temp_anagram with the letter removed
　　if (is_a_match) and (length of word is more than or equal to min):
　　　add word to running list of match words
　return the list

And the resulting Python code became:

def matches(anagram, wordlist, min=3):
　solutions = []
　for line in [l.strip().lower() for l in wordlist if not "'" in l]:
　　sample = anagram
　　match = True
　　for char in list(line):
　　　if char not in sample:
　　　　match = False
　　　else:
　　　　sample = sample.replace(char, '', 1)
　　if match and len(line) >= min and not line in solutions:
　　　solutions.append(line)
　return solutions

The third line is a list composition:

[l.strip().lower() for l in wordlist if not "'" in l]

which does three things to the wordlist before for-looping over it: excludes all words that contain an apostrophe, strip the words of any whitespace and the beginning/end, and put the words in lower-case. All of these things make it easier and/or faster to exclude words that are not matches to the anagram, which is literally what this method is doing. The rest of the code should be self-explanitory after following the psuedocode above; the only addition to the algorithm is the "and not line in solutions", which makes sure there are no duplicates in the solutions list.

Now that I had this method, I had to think of a way to make the bot type each word into the box on the browser's screen. Luckily, I had already made a bot that plays the popular flash game QWOP, so I knew how to do this with Python: using the little-known Python module virtkey. With virtkey, you can do things like:

v = virtkey.virtkey()
v.press_unicode(13)
time.sleep(0.01)
v.release_unicode(13)

This is equivalent to pressing the return key. I generalized it as a function:

def hit_key(unicode_val):
　v.press_unicode(unicode_val)
　time.sleep(0.01)
　v.release_unicode(unicode_val)

Where v was declared as a global variable earlier (v = virtkey.virtkey())

So the bot's essential algorithm became, at first:

create a dictionary (in this case from text files)
get an input string from the user
words_to_type = matches(input_string, dictionary)
for word in words_to_type:
　for each character in word:
　　hit_key(character)
　hit_key(13) # 13 is unicode for carriage return aka the enter button

But wait! There was a GUI issue. What if the bot typed a word that the online anagram game disagreed with? In certain cases, the word wouldn't disappear: it would stay in the text box, and we couldn't have that. What if the bot typed "NERO" and the online game disagreed, leaving "NERO" in the input box? The bot might happily type the next word, creating "NERONOR", and press enter again, and chaos ensues and nothing is won.

The only solution I saw was an inefficient yet effective one: to backspace for every character in the typed word, just in case.

Case 1: the typed word, with length n, is valid according to the online game, and it disappears from the textbox. The bot backspaces n number of times in an empty textbox, no harm done.

Case 2: the typed word is rejected, and remains in the textbox. The bot backspaces over it, and it was as if nothing was ever amiss.

The actual code was the following:

for c in list(w):
　print 'Backspacing...'
　time.sleep(0.01)
　hit_key(8)

The number 8 is unicode for the backspace. The time.sleep(f), if you haven't already figured/googled it out, pauses the program for f amount of seconds. The pauses are to fool online games' bot detections. Play too fast, and it's obvious you're a bot.

I am reluctant to post the entirety of the code. To post it in an easy-to-use script is to lower the bar. It is my belief that, while I am inventing ways of cheating, I deserve to be considered a winner for being able to find a way to cheat. There is certainly a difference between writing a bot and using one.

And surely, the skills required to write a successful bot are more important than the skills required to successfully unscramble anagrams.