Solving Boggle (Scramble with Friends) with a Bot!

Headnote

I am always fascinated by Android games, especially puzzle games. This is how it usually works with me and a puzzle game. I start playing them with random friends. They beat me and I beat them on and off. Then I sit and think, this is so monotonic and algorithmic that a human being shouldn't be sitting and doing it. Then I sit with the computer (with my favorite monkeyrunner Jython in it) and try to come up with a simple algorithm for it. Then i plug in the standard monkeyrunner code to actually feed the output of the program back to the device. Then I usually become #1 among my friends in the leaderboard (often even in the global leaderboard) ;-)

This is one such scenario. Zynga's Scramble with Friends has been really popular among my friends off late. So i hit this routine cycle and ended up with a beautiful bot which usually scores a centum (like the one TamBrahm parents force their kids to get in Mathematics).

With that out of the way, let's begin.

Objective of the Game

The game consists of a 4x4 grid of letters. You have to form as many words you can by starting from a letter and by moving to one of the (upto) 8 adjacent letters. Dead simple, but really interesting and addictive.

The first thing needed to solve this is a dictionary of words. I went on the internet and downloaded a plain text dictionary file which had about 170k words in it. Good enough to start with.

Algorithm - Breadth First Search

The number of valid words is usually very limited. In most games, the total number of valid words is usually < 400. So, a simple Breadth First Search (BFS) will do starting with single letter elements and then add the neighbors recursively. One key insight is, if you come across a prefix that never occurs in the dictionary, you can discard that prefix at that point instead of adding it to the traversal queue.

A rough sketch of the algorithm is as follows:

• queue = [all 16 characters]
• while queue is not empty:
• word = head of queue
• if word is in dictionary output it [1]
• for all neighbors adjacent to the last character of word
• new_word = word + neighbor
• if dictionary has words with prefix new_word, add new_word to the queue [2]

That's it. Straightforward implementation of a BFS-like algorithm.

Choice of Data Structure

The key to solving this problem efficiently lies in choosing a good data structure for implementing the dictionary. The dictionary needs to support two major operations. One is looking up if a word exists. This is used for step [1] in the above algorithm. The other operation is, given a prefix, check if there is atleast one word containing that prefix in the dictionary. This is used for step [2] in the algorithm mentioned above.

Array ?

One good looking candidate is using a simple array (note that the dictionary is already sorted for us). Look up can be performed using simple binary search. Prefix checking can also be performed using a modified binary search (if search succeeds, then prefix exists. if search fails, prefix existence can be determined by looking at the bounds in which the search failed). Also, note that the dictionary has ~173k words. So, searching is gonna take log(173k) which is approximately 18 hits in the worst case. This is a totally fair deal.

Trie ?

Another possibility is using the Trie, whose raison-d'etre (very reason for existence) is to implement such dictionaries. The Trie implementation is also fairly trivial (since we require only two major operations apart from Trie construction). In the Trie, both the operations are gonna take as many hits as the length of the word or the prefix being looked up. So asymptotically, both these data structures are more or less similar and we don't have a big advantage in using either one over the other since our output is always gonna be < 400 words.

I decided to go with the Trie. After reading this article about Trie implementations in Python, I decided to quickly write my own implementation of Trie. Also, this made life simpler as I couldn't quickly find any good resources about using external libraries within monkeyrunner.

Implementation Quirks

Since I had already used monkeyrunner a few times before, implementation turned out to be pretty straightforward. The following are a few implementation quirks and nuances that the script deals with:

• Input is manually entered as a raw row-major string of length 16.
• If the same word can be formed by two different combinations, only one combination is actually considered valid. This is overcome by storing a list of already found words in another Trie.
• Even though the script finds smaller words first (because of BFS), it actually starts outputting words of length >= 5 first and then after it has exhausted all the lengthier words, it then outputs the smaller words in the reverse order of length (4,3,2). This is to maximize points in case we don't find time to output all the words.
• The game offers three lifelines. I found the freeze option to be useful to the bot (as each freeze gives you 15 additional seconds of game time). So, the script automatically taps on the freeze lifeline every 30 seconds.
• We also need to store the co-ordinate of each letter in the queue along with the letters themselves in order to simulate the output in the device.
• The co-ordinates are hard-coded for Nexus 7 portrait mode.

Code

The whole implementation can be found here: https://github.com/vickyg3/scripts/tree/master/scramble_bot

Sample Video

Here is the exciting part. This is how it looks like when my bot plays the game:

It's always a very nice feelings to watch you script do such beautiful things.

-Vignesh

Wanna do some good deed? Visit http://www.computerkindness.org (Or look for the banner in the top-right of this page).

Convert your keyboard into an Android game controller!

I have been gifted with a new android phone. It's the big G branded Galaxy Nexus. Its blazingly fast and awesome to use (especially after years of HTC Wildfire usage). Right from day one, i have been really addicted to this game called Temple Runner which wasn't compatible with my old phone.

The game is very straightforward to play and it involves only 4 different operations. Swipe up, left, right and down. Coming from a strong keyboard background, I was never 100% comfortable with touch interfaces as i was with keyboard. And these 4 operations sounded analogous to the accelerate, brake and turn operations while playing a racing game in the computer keyboard.

That got me thinking, is there a way to make the computer keyboard into a game controller for my Android phone? Turns out its fairly straightforward. In this post i'll explain exactly how to do that.

Ingredients

• Android phone (obviously)
• USB cable connected in debugging mode
• Android SDK installed
• Very very basic python english

There's a tool named monkeyrunner which enables us to send operations from the computer to the phone via a very simple Python API (monkeyrunner tool is a part of Android SDK). A sample code for a controller would look like this:

Code until line 7 is fairly straightforward to understand. The only thing that i would like to explain here is the device object. It is an object of the MonkeyDevice class. This class has all the API methods that you need to use in order to simulate the operations. For example, device.touch(100, 200, MonkeyDevice.DOWN_AND_UP) will simulate a touch event at co-ordinate 100, 200 (with the origin being top left). As simple as that!

You can find the detailed documentation of the monkey device class to know about other methods like drag, type, etc.

The full code which i used for playing Temple Run game is given below:

One point to note is that, the sys.stdin.read(1) line will read one character and wait for the enter key to be pressed. This could be annoying given that you are writing a game controller. In order to avoid the enter key press, if you are on linux run "stty raw" before running this script and if on windows use the getch function in msvcrt module.

-Vignesh

How I hacked an android game with Python and OCR!

Math Workout is a famous android game. In fact, it features in the top 5 of google listings for many math game + android related queries. The objective of the game is very very simple. It will fire simple math questions one after the other and you'll have to tap in the correct answer. Its a race against time among other users of the app in the world.

Here's how the app looks like and a few screenshots of questions:

As you can see, the game is fairly straigtforward. So its the time that you have to beat. A naive approach to that would be having a calculator or a computer near by and feeding in the questions to determine the answer and feeding it back to the phone. Totally manual!

Thats when the programming neurons of my brains started itching me that this could be automated and cheated by some mean. Come on think, think! So i sat on to solve this problem during my weekend and started thinking about ways i could attack this problem.

These are the steps that came into my mind in the first thought:

1. Grab a screenshot of every question
2. Crop the screenshot so that only the question is visible
3. Run the cropped image through an OCR engine
4. Parse the result and evaluate it
5. Identify the co-ordinates of the resulting number and appropriately simulate touch events in the phone

Bummer! Every step looked a bit complex in itself at first sight. Then came along a bit of googling, and voila, i found the perfect tool that i needed to perform steps 1, 2 and 5. It is the monkeyrunner tool that comes along with the Android SDK. It opens up a Python API through which i can grab and crop screenshots, simulate touch events given an (x,y) co-ordinate. Exactly what i wanted.



Now, I have the cropped image that has the question in hand. Next step is to run it through an OCR engine. Again googling told me that ocrad is an useful OCR command line tool that was available as a part of the GNU project. I installed it and found that it cannot process png images. So i had to run the image through a converter before passing it to ocrad. This small piece of shell script helped me accomplish that:


To keep things simple, the shell script is invoked from python using os.popen(). Now, I have the actual expression as a python string. As you can see from the sample screenshots, few questions can be solved by a direct "eval" whereas others require some processing. Basic operations like addition, subtraction, multiplication and division can be solved using "eval". Whereas questions like "10% of 20", "square root of 9" needs some processing. Thats what this following if else block does:



Now that the expression is evaluated and we have the result in hand, all that's left is to go through the result character by character and simulate touch events in corresponding positions in the screen. I managed to identify the co-ordinates of each number in the screen by trial and error and hard coded those values within two functions named getx() and gety() which will take a character and return its corresponding x and y co-ordinates respectively, and the simulation happens. Here is the code snippet:



To orchestrate this whole process and play the game fully automatically other cosmetic additions like coping up with the frame rate of the phone and taking care of screenshot/ocr lags are to be considered. These are handled by minor if conditions and sleeps for very small amounts of time.

The end result is as you see in the below screenshot :-P

Here is a video of how the game looks like when it is being played by my script:

Though these steps seem like computationally a bit expensive, in practice i found them to be really fast. The script was able to answer approximately 2 questions per second (with an explicit sleep of 0.2 seconds between two questions - which leads to 2 questions every 0.8 seconds). A C/C++ program might run faster than this, but i stopped here as i have accomplished what i wanted. Overall it was a fun filled Sunday! :-)

Here is a link to the full source code of the automated script: auto_math_workout.py (you can find ocr.sh from the gist above in this page - rest of the source code is in the link)

Any comments/feedbacks are welcome! :-)

-Vignesh

Scripting vs Programming - Mastering the art of arts!

Why this post?

The line of difference between a script and a program has become very blurry these days to the extent that these terms are used interchangeably. Though there is no hard and tight way to theoretically define what a script is and say how it is different from a program, if you have done a lot of programming and if you are a person who loves to automate things, then you can definitely realize the clear line of difference between scripting and programming. In this article, I try to give my views on what scripting is, how it differs from programming, etc. (Whole of this article just represents my view and there is a good chance that some of it may be wrong).

What is a script?

A script is just a small piece of code, usually written in a non-traditional programming language (like bash or perl) that is used to get a job done. Well, sure you can’t see much of how it differs from the definition of a "program". That is what i try to explain on the due course of this article.

How does it differ from a program?
As i said earlier, there is no concrete set of rules to distinguish a script and a program. The main deciding factors are:

• the purpose with which its developed
• the design mechanism underwent on due course of development, and
• the person who uses it

Scripts are generally very specific to their task. They just do what is to be done, nothing more or nothing less. Whereas programs generally have a broad scope. They are more sophisticated and usually do much more than what they are supposed to do. This is the difference with respect to the first point.

Scripts generally don’t follow any design. Scripts are usually just written, with no design in mind whatsoever. Even if they are complex, they aren’t designed with care and concern. Whereas programs on the other hand are designed to work with a proper flow and fault tolerance. Scripts are usually used by programmers themselves internally, whereas programs are full fledged tools that are used by everyone from geeks to laymen. To state an example, Facebook is a "program" and if you build something that will scrape data off facebook in the format you want, then that could be a "script".

Scripting is usually considered as programming as a part of developing an actual program. For example, the recent android patent issue says Google used a "script" to clean up all the comments and other stuff from the kernel header files. So, scripts can be generally categorized as utility functions that helps you making your "program" development easier.

What’s a scripting language?

Again, a scripting language is a programming language that is generally non-traditional. Scripting language usually provides constructs for doing things in the quickest way possible rather than in the most efficient way possible (For e.g. most of the scripting languages usually have a sort() function to sort the data. Though they may not be the most efficient implementation of sorting data, it gets the job done without fuss). Another aspect is that scripting languages are usually interpreted and not compiled. This gives the assurance that the script dies if anything goes wrong, the script starts over all again, taking advantage of the fact that scripts need not provide any atomicity over what they do.

Uses of scripting

I love automating things i do and hence scripting is a very essential part of my online life. Scripts can help your online life get much easier and better. For example, i have various little chrome content scripts (google chrome’s equivalent of greasemonkey scripts) that helps me make my day-to-day browsing easier and more productive. Also, i extensively use sed and awk scripts to browse through log files generated by the programs i develop. I even have scripts that help me check if there are new episodes of my favorite TV Serials (BBT, HIMYM) available for download and alert me.

When it comes to automating day to day online tasks, scripting is your swiss army knife. You can accomplish things quickly and in the way you want them to be.

Scripting as an art

We all know that programming is more of an art than a science. Developing a perfect program is close to impossible. But scripting too is an art that can aid you in making your programming life much better. Learning a scripting language at the beginning may seem weird, but once you get used to the constructs, it will really be a cake walk and you will find it a lot useful to have it as one of your assets.

To sum up..

Scripting and programming always go together. Scripting aids in automating things that will make a program better than what it is now. Though only a beginner, my humble piece of advice to every programmer out there is "Never hesitate to automate things. You learn a lot while automating silly things! So next time when you come across a silly problem in your work or in your project, try to tackle it with a quick utility script rather trying to fix it manually!"

-Vignesh

Why Computer Science should not be taught with Python!

Every Computer Science student begins his academic travel with the first stop being C. It is really a good language to begin with and it helps the student to grasp the fundamentals of how a computer program works. And (atleast in India) most of the Computer Science courses just revolve around C/C++ almost the entire of the curriculum. All the laboratory classes usually mandates the student to develop programs in C/C++ or Java in some cases.

Any student who has worked for a reasonable amount of time with a language like Python or Ruby will be against this system. He will be frustrated in writing tens of lines of C code when the same can be accomplished in very few lines in Python. I have a strong opinion that this should not be the case and undergraduate courses should insist on students using C/C++ as their primary language on the academic curriculum side.

C is a programming language that requires very verbose form of writing programs which will be highly helpful in learning and understanding the underlying concept thoroughly. Consider an example of quick sort. It is a single line of code in Python. But what does the student really understand out of that single line? Whereas when you write the same thing in C, it really forces you to understand the algorithm line-by-line, thereby making the student more knowledgeable about the actual working of the algorithm rather than just getting the thing done. Getting things done is top priority in an industry. But when it comes to academia, learning the underlying working is more important than getting things done.

Another good example would be writing a simple socket program. In python its a maximum of ten lines. Whereas in C you work very closely (almost with actual system calls) and hence you thoroughly understand the whole process of how a socket connection works.

More the abstraction, better the survival. This definitely holds good, but not when you are undertaking a course to become a computer engineer. Abstraction is good once you have completed the learning process. But when you are in the learning process, less abstraction is more helpful in making a student better.

-Vignesh