July 1, 2013

Scrambling Letters

Scrambler

Ever since I saw my first Jumble word puzzle in the newspaper as a child, I’ve always wanted to write an algorithm to solve it. This inkling was lately renewed when I came across the 4 Pics 1 Word puzzle game. I had an idea of the simple brute-force algorithm that could solve the problem, so I went about implementing it in code. You can play with the final version here. I’ve limited it to only search for words that are found in 4 Pics 1 Word to limit the number of possible answers it finds.

The algorithm is easiest to implement recursively. If you know the number of letters in the answer (r), and you have a list of available letters (n), then you simply place one letter at a time in each available spot and exhaust all possible permutations. There are going to be a total of nPr possible permutations. So it’s best to limit it to smaller values of n and r. Once you have all the possible combinations of ‘words’, you can use a dictionary to check which ones of your ‘words’ are actual English words. The dictionary can just be a hash table and you can check if your ‘word’ exists in the table.

The Algorithm

Although the brute-force algorithm is trivial to describe, implementing it properly is another story. I ended up with the following function. The base case occurs when there is only spot remaining in the answer. When this is the case, the function returns a list of all the unused letters that can be placed in that spot. When not in the base case, the function will fill the first available spot with a letter and then recursively find all possible combinations for the remaining spots using the remaining letters. It does this for all possible letters that could take up the first available spot. Here’s the python code for it:

def getWordsRecursive(spot, remainingLetters, numSpots):
    if spot == (numSpots - 1):
        words = []
        for letter in remainingLetters:
            words += [letter]
        return words
 
    words = []
    for i in range(len(remainingLetters)):
        letter = remainingLetters[i]
        suffixes = getWordsRecursive(spot+1, remainingLetters[:i] + remainingLetters[(i+1):], numSpots)
        for suffix in suffixes:
            word = letter + suffix
            words += [word]
    return words

Calling getWordsRecursive(0, 'ABCDEFGHIJKL', 5) will give you all the possible 5 letter combinations that can be created from the letters A-L.

Making it faster

Although this works, it is horribly slow. I didn’t mind it too much at first since I was able to get most answers on my local machine within 0-30 seconds. But when I uploaded this implementation to my shared host server, it was taking over 5 minutes for some queries and my server would automatically kill the process when it took that long. So I set about finding ways of making this faster. One of my first thoughts was implementing the algorithm iteratively since I thought that the deep use of the stack used by the recursive algorithm might be the reason for the server killing the process. But after a little more thought, I realized that I could use the extra knowledge I had about this particular problem domain to make things more efficient while keeping the simple recursive function.

Since I am only interested in finding valid English words, I can use this information to cut the search space drastically. Let’s say that once I have determined all possible combinations for the first 3 letters in the answer, I can check with my dictionary if there are any English words that start with those 3 letters. If there are none, then I do not need to find the remaining possible combinations for those 3 letter combinations. Here’s a python function putting that information to use:

def getWordsFaster(pSpot, pLetters, pNumSpots, substringStart=0):
    if pNumSpots <= 3:
        return getWordsRecursive(0, pLetters, pNumSpots)
 
    firstHalfLen = len(pLetters[:pNumSpots/2])
 
    prefixes = getWordsRecursive(0, pLetters, firstHalfLen)
 
    prefixes = getDictWords(prefixes, substringStart=substringStart, substringLen=firstHalfLen)
 
    words = []
    for prefix in prefixes:
        remainingLetters = pLetters
        for letter in prefix:
            i = remainingLetters.find(letter)
            remainingLetters = remainingLetters[:i] + remainingLetters[i+1:]
 
        suffixes = getWordsFaster(0, remainingLetters, pNumSpots - firstHalfLen, firstHalfLen)
 
        for suffix in suffixes:
            words.append(prefix + suffix) 
    return words

If the number of spots in the answer is 3 or fewer, then I simply resort to the first function since it is fast enough. For more spots, I first get all the possible combinations that could fit in the first half part of the answer using the first function. (The splitting could be made more granular based on how big of an output you are supporting. I have restricted my output to a maximum of 8 letters (not shown here), so just cutting in half was good enough). Then I use the getDictWords() function (also not shown here) to filter out all those combinations that can’t possibly be English words. Now for all the remaining valid combinations, I call this function recursively to return all combinations that start with those valid prefixes. Once I have the final list, I run it again through getDictWords() to get my final filtered list of English words.

 Conclusion

This was a fun little problem to solve that looked deceptively simple, yet wasn’t as trivial to implement as I initially thought it would be. Finding a way to cut down the search space made a drastic improvement in the algorithm speed. Most queries I have tried finish up in under 1 minute on the server now. Try it out for yourself. I also released an Android app that uses this algorithm to help you find answers to the ‘4 Pics 1 Word’ word puzzle game. The app additionally uses OCR to detect the available letters and the number of spots in the answer so the user doesn’t have to input any data at all, but simply provide a screenshot of the puzzle.

June 16, 2013

4 Pics 1 Word Auto Solver with OCR

Have you been playing the popular word puzzle game 4 Pics 1 Word lately, but find yourself stuck? Now you can use my Auto Solver app to quickly provide you with the answer. Simply take a screenshot of the puzzle you’re stuck on and load the screenshot in Auto Solver. Auto Solver will automatically detect the letters available and try all possible combinations to find the answer for you. You will always find the answer with this app.

May 29, 2013

Utility classes for Google Play In-App Billing API v3

droidtocat

I created a GooglePlayInAppBilling GitHub project that extracts the utility classes from the TrivialPlay sample app. The project can be used as a library project in your Android app and makes it easier to work with the billing API. I also found that I had to fix a flag not being reset properly in the utility classes. You can fork the project here.

March 1, 2013

Where to Promote Android Apps

Since Google Play does not feature new apps in the “Just In”/”What’s New” section any more, there is almost no way to get visibility for new apps other than whatever app promotion you can do on your own. So I recently (March 2013) scoured the web to find the best places to promote an Android app. The sites are ordered according to Alexa Rankings. I’m only listing the top sites from my list here. Most of the stuff mentioned here will only likely give your app an initial influx of downloads. To actually have sustainable growth, you’ll have to rely on a kick-ass app with some sort of viral/social component that users will love to talk about and share with others.

App Markets

First, make sure that your app is published in some of the top markets so that it is visible to the largest audience possible:

Android App Review Sites

Probably the best way to get the most eyesballs on your app is to get a popular site to review it. This is easier said than done. Some sites charge for this service, some accept submissions for free. Either way, these sites are bombarded with a constant barrage of app review requests so there is no guarantee that they will actually review your app. The following is a list of sites that are open to receiving app submissions for review:

Forums

Apart from review sites, forums are probably the best way to get a some users to check out your app. The following forums have an area specifically for promoting your apps. Users would usually frequent these forums looking for new gems, but traffic is quite low:

Other Sites that do App Reviews

The following are sites that are known for reviewing apps, but there is no straight-forward method for informing them about your app (sometimes deliberately). However, they do they have contact forms, email addresses or send-a-tip forms that you can use to inform them about your app. I would only suggest using these if you feel like your app is worthwhile enough for them to report on. Take a quick look at their home pages to get an idea of the quality and type of apps they review:

Sites that Promote New Apps

Here are a couple of sites that help promote new apps. It might be easier to get listed here than on the other app review websites. However their Alexa Rankings are very low and you will probably get very few hits from being featured here:

These are a lot of Sites to Register for

Damn straight. I’d suggest using a password manager tool like LastPass to help you create, and more importantly, remember the account information for these sites. Please also try to obey the rules of the sites/forums and do not post material that is considered spam by that site/forum. Also please try to be a good citizen of these sites and try to contribute material or useful forum posts back to the community in exchange for letting them promote your app. That means using an actual email address and logging in later to respond to queries about your app and perhaps engaging in other forms of discussion happening on the site/forum (commenting on threads, giving feedback on other’s apps).

About China

Finally, be aware of Chinese app markets and rampant piracy. Hackers have been known to not only clone your app and post it as their own, but also to switch out AdMob (or other advertising) links to point to their own accounts, hence robbing you of potential revenue. The best course of action is to make sure that your app is already listed in the top Chinese app markets (so the hackers get a package name conflict), or if you already see that your app has been cloned/hacked, then send a copyright infringment request to the organizational entity running the app store. They usually take down the infringing apps quickly. To see if your app is cloned/hacked in a Chinese app store, translate the name of your app into Simplified Chinese using Google Translate and then search the popular Chinese app stores for that string. You can also try searching for your app’s package name.

Updating this List

If I’ve missed out on some awesome site, please post it in the comments. Good luck promoting your app!

January 29, 2013

Gainos Fresh Wallpapers for Android

Gainos Fresh Wallpapers

When I got my Nexus 4 phone, I wanted to take full advantage of the high quality screen and set a gorgeous wallpaper on it. But I realized that no matter what wallpaper I set, I always get tired of looking at it quite quickly. What I really wanted was a new beautiful wallpaper every time I would pick up my phone. And that’s why I created the app Fresh Wallpapers HD. It selects a random photo from Flickr’s Explore stream and sets that as your wallpaper at regular intervals. I have mine set to change every hour.

Never get bored by staring at the same wallpaper over and over again! Get fresh, new photos from Flickr as your wallpaper. You never know what the next image is going to be, but it will be amazing. Set your own time interval to decide how frequently the wallpaper updates.

  • Works well with tablets and phones. For high resolution displays a higher quality image is downloaded.
  • Minimal interface that stays out of your way. Just start the service once and forgot about the app.
  • Choose to download new wallpapers only over wifi to save cellular bandwidth.
  • Choose to change the wallpaper as frequently as every minute to as slow as once every 3 weeks.
  • Images are selected at random from Flickr’s Explore stream. This app is not affiliated with Flickr in any way.

Get it on Google Play

April 5, 2011

PlayBook details from BlackBerry Dev Day Toronto (video)

PlayBook details from BlackBerry Dev Day Toronto (video)

I was in attendance at the BlackBerry Dev Day in Toronto a few days back (31st March 2011). I was mostly interested in finding out more about the BlackBerry PlayBook from a developer’s perspective as I’ve been developing an app for it recently. Here are some notes I made regarding the PlayBook during the talk as well as a video of a live demonstration of the PlayBook’s prowess.

  • ‘Gold’ version of the PlayBook SDK will be released very close to the launch (19th April) and it will have substantially more new features. This makes sense, as the current SDK available to developers lacks some of the functionality that I occassionally see in offical PlayBook demo videos (e.g. the markers at the start and end of text selection) suggesting that they are holding some features back from developers until they are ready to release it (or run out of time and have to release it as is).
  • Ad Services and Payment Services for PlayBook developers will not be available for at launch in the SDKs, but will be added soon after. Payment Service will be there by summer.
  • Similarly, the Analytics service will be made available on the PlayBook some time after its launch. The service will work through WebTrends. This sounded like a very intrusive service for the users, but potentially great for the application developers. If the developer includes this service in the app, it can be switched on by default (without asking user’s permission) if the developer chooses to do so. The service will send data to WebTrends servers. The only way the user can switch this off is by setting the firewall settings on their device to block www.webtrends.com (not very user friendly). Later they said that the user will be notified through the app that the app is trying to connect to WebTrends and they can choose to block it from there, which is slightly more user friendly. However I’m not sure if they meant if the user will be specifically told that the app is trying to connect to WebTrends, or if the app is asking for general internet connectivity permission. Overall, there was a bit of conflicting information regarding this, and it sounded like a bit of a work in progress – I suspect they will modify things to make it easier for the user to manage this before officially making this service available.
  • There is no support for virtual currencies right now, but they are trying to implement it – as soon as they figure out how to deal with some unique accounting issues related to that.
  • All PlayBook apps submitted by 31st March, are likely to be reviewed by the 19th April launch date with 90-100% probability. The app review team is well-oiled and getting better at reviewing apps. I have to personally agree with this. Keeping track of app submissions and approval dates in the Developer Forum suggests that the team is operating much faster now than in the beginning.
  • Push doesn’t exist on PlayBook today, but will come later.
  • Native PlayBook clients for email, calendar, etc will come later. At launch these will only be accessible via the BlackBerry Bridge (which works through Bluetooth).
  • BBM is not in the PlayBook except for through BlackBerry Bridge (for now).
  • They suggested that it might be worthwhile to launch apps in non-North American markets first (e.g. Indonesia, Mexico/Spain) to get some feedback and revenue and then launch in the larger North American market. They also said its worthwhile offering translations into other languages (particularly Bahasa and Spanish).

Here is a video of RIM’s Director of Developer Relations, Mike KIrkup, demoing the PlayBook to an impressed and applauding crowd.

Interesting parts are at:

  • 0:57, when he demonstrates playing an HD video over HDMI with Need for Speed still running in the background (albeit in a paused state).
  • 3:32: running camera and playing Need for Speed at the same time. Need for Speed is controlled by the accelerometer and you can see the camera angles changing in the live thumbnail view as well as the car turning in that direction in the Need for Speed live thumbnail view simultaneously.
  • 5:24: Over The Air (OTA) update mechanism. The device, when first shipped, will ask the users to perform an OTA update before they can start using it.
March 27, 2011

Lessons Learned Working on a Programming Side-Project

The last few months I had been building an app for the upcoming launch of the BlackBerry PlayBook tablet. Its a fairly simple app – a text editor that syncs notes with Dropbox – and consists of about 3000 lines of source code. Now that I have submitted version 1.0 of my app to the BlackBerry AppWorld, I wanted to take a step back and look at my progress, and more importantly, my productivity.

I used the Mercurial Activity Extension to plot out my commits and collect other relevant data. Here is a chart of my commit activity for the duration of the project along with some annotations:

Lessons Learned Working on a Programming Side-Project

I worked on this during any spare time that I got from my full-time job. I first started during the Christmas/New Year’s holidays. This was the most productive, and also the most frustrating time, since I was learning how to do things on a new platform (Adobe AIR + BlackBerry QNX) for the first time. Also RIM had an offer going on for all developers: if the app was submitted before February 1, and accepted, the developer would win a free PlayBook. So initially I was aiming to finish up in about a month.

However, on January 13 I found out that RIM had extended that deadline to March 15. And my productivity suddenly dropped right after. I realized that I didn’t have an excuse for ignoring all the other things in my life that required my attention, so I started dealing with them. Also, work got a bit busier during early February and I generally found myself having less spare time. Anyhow, my activity started picking up again closer to the next deadline. There was another small drop when I discovered that the second deadline had been extended, but I pulled through this one with a determination to finish by the now defunct second deadline. Eventually, I was able to finish slightly past that deadline, and had my first release ready by 22nd March.

Lessons Learned:

  • Deadlines work. But only when they are enforced by some third-party. Self-imposed deadlines have never been effective for me.
  • Life always gets in the way. There’s just no getting around this one.
  • Momentum is important. It’s hard to get back momentum once you lose it. But once you have it, you’re on a roll and much more productive.
  • Social life gets put on the back burner. Devoting your time between a full-time job, a side-project that feels like another full-time job, and taking care of life’s necessities, really doesn’t leave time for anything else.

I didn’t stop there with my analytics. I wanted to dig deeper into the data. So I plotted a chart of my activity per day of the week:

Lessons Learned Working on a Programming Side-Project

The chart is divided into working days and holidays (weekends, Christmas break, New Year’s, Family Day, and an extra day off I took on the Wednesday between Christmas and New Year’s). Surprisingly, my two most productive days of the week are not on the weekend, but they are Tuesday and Friday.

I knew that I had been doing a lot of my coding during the wee hours of the morning, but I wanted to know exactly how much. So I plotted this chart mapping my number of commits done per hour over all days:

Lessons Learned Working on a Programming Side-Project

It looks like 7am is the most productive time of the day for me. There is a reason why I have gravitated towards working in the mornings: there are the least amount of distractions then. Most of the world is asleep and there is little activity on Facebook, Twitter, tech blogs and news websites to distract me. Also, my mind is fresh in the morning and not tired after a full day of work. Luckily, I have a job that is flexible with their work hours, so I was able to shift my working hours to later in the day. Night time was mostly reservered for eating dinner and unwinding by watching a little TV and clicking away at links on sites I frequently visit.

It also looks like I do roughly about the same number of commits on holidays as a do on workdays. Its just that my commits during holidays are spread out more evenly during the day. This makes me wonder if I am more focused and get the same amount of work done, as I would on a full day of a holiday, that I get done in a few hours on a workday. Perhaps I am subconsciously treating the fact that I can’t be too late to get to the office for my job as a  ‘deadline’. And that deadline mentality forces me to get more things done faster. Perhaps I’m one of those people who work better under pressure.

March 26, 2011

How to Chart your Mercurial Commits with the Activity Extension in Windows

How to Chart your Mercurial Commits with the Activity Extension in Windows

The Mercurial Activity extension lets you measure the number of commits done to a Mercurial repository per day and chart it out using Matplotlib.

The installation process was a bit of a doozy on my Windows system, so I wrote this step-by-step guide. The extension uses the Matplotlib library for plotting the chart, so you will need to have that set up inside your Python distribution. The default Python installation I had on my system was v2.7 64-bit, and the default Mercurial client I was using was TortoiseHg (with Mercurial 1.7). However after some tinkering around, I found out that I couldn’t get the extension to work with this sort of setup – mostly because TortoiseHg comes with its own Python distribution in some DLL file inside a library.zip archive and I have no idea how to install a Matplotlib site-package in there.

So this is what worked for me:

  • Get Python v2.6 32-bit (I found this to be the lowest common denominator which would work with all of Numpy (a pre-requisite for Matplotlib), Matplotlib, Mercurial and the Activity extension). For all remaining steps, make sure you are using this distribution of Python and not your default one (if it is different than this one).
  • Download NumPy and install it inside Python 2.6. I ended up getting the latest stable release: NumPy v1.5.1, win32 for python2.6. The installer is an exe file and you can simply run it to correctly install inside your Python 2.6 distribution. Check that NumPy is installed by running the Python 2.6 interpretter and typing this:

import numpy
print numpy.__version__

  • Download Matplotlib and install it inside Python 2.6. I ended up getting v1.0.0, win32 for python2.6. After installation, check from the Python 2.6 interpretter that its correctly installed

import matplotlib
print matplotlib.__version__

  • Download Mercurial for your Python distribution (even if you already have TortoiseHg installed). This is because we need to install Mercurial inside our Python 2.6 distribution whereas TortoiseHg comes with its own custom Python distribution. I ended up getting Mercurial 1.8.1 for Python 2.6 and x86 Windows. After installation, make sure that you can import it from Python 2.6. Also, you should be able to run ‘hg’ from the ‘Scripts’ folder inside your Python2.6 install (default location: C:Python26Scriptshg)

from mercurial import __version__
help(mercurial.__version__)

  • Finally, download the Activity extension itself. I got v1.4. This will unzip to a bunch of python scripts and a README.txt file. As the README instructs, edit your global mercurial settings file and put the following line under the [extensions] heading:

[extensions]
activity = C:\Programs\hgactivity-1.4\activity.py

Of course, set the actual path to where ever you extracted activity.py. If you have TortoiseHg installed, you can gain access to the global mercurial settings file by right-clicking in Windows Explorer, selecting TortoiseHg->Global Settings, and press the ‘Edit File’ button.

  • Now you are ready to actually use the extension. You will have to use it from a command prompt. cd to the root of a mercurial repository and issue the following command:

C:\Python26\Scripts\hg activity

This will create an activity.png file in the current directory. To see all other options available, run ‘hg activity help’.

Finally, I’d like to thanks the authors of this extension for making it available open source. You can modify activity.py to extract different types of data or present it in different ways. In the version of the script I downloaded, the Y-axis labels were switched off by default. You can fix this by editing the line that says

ax.yaxis.set_visible(False)

For other type of edits you’ll probably want to brush up with Python’s datetime class. Have fun! 🙂

December 10, 2010

Blackberry Tablet OS Simulator complains about 64-bit Windows

Blackberry Tablet OS Simulator complains about 64-bit Windows

Hearing about the free Blackberry Playbook offer, I’ve decided to jump on the bandwagon and see what the platform has to offer and how it is to work with. Its running on the Adobe AIR platform, which I am not familiar with at all. I did some Flash and Actionscript development for a project course in university several years back. It wasn’t anything extensive and I haven’t done anything since. I figure its a good chance to look at what’s new out there. However things are not off to a good start. Let me highlight a point with the Tablet Simulator. When you try to install it on a 64-bit Windows machine you get this message:

Win64 not supported

The author of the package you are installing did not include support for this platform

Win64_not_supported

I immediately recognized this as an installer issue since I’ve seen this problem with other softwares. But I was expecting better from a big player like Blackberry. Especially after someone complained about the SDK installer having the same issue a month ago. They did manage to create 64-bit compatible installers for the SDK since I didn’t have any problems installing that. But no one bothered to check the Simulator installer for the same issue. This is not very developer friendly, especially for a company just breaking into the Tablet market and trying to play catch-up with the competition.

I don’t understand how companies can casually overlook 64-bit platforms as they represent the future and many developers have already jumped on board. Its understandable if this was for a consumer product and they didn’t want to support 64-bit systems. But this is a product specifically designed for developers. If you’re not making things easy for your target audience, then you’re doing something wrong.

After some searching I found a post by another developer who came across the same problem. (BTW, there don’t seem to be too many articles about this). I followed his suggestion and opened the installer with 7-zip. Inside there browse to

InstallerDataDisk1InstData

and extract the contents of Resource1.zip. Inside Resorce1 go to

$IA_PROJECT_DIR$installerdata

and the ISO file that we need will be found sitting there. The ISO file is meant to run on VMWare Player. So clearly it has no 32-bit/64-bit architecture issues. Its just the installer that Blackberry couldn’t bother fixing. How stupid is this.

Update: As you can see from the image at the top of the post, I was able to finally get the Simulator running. This just confirms that the Simulator indeed works on 64-bit machines. Its just the installer which doesn’t.

 

December 9, 2010

Doing some Vector Art

For the longest time I’ve been wanting to have a personal avatar that I could use for my profile picture with online services. I didn’t feel comfortable putting up a real picture, but on the other hand I wanted to have something more personal than some arbitrary photo/design.

So recently, I decided to spend some time and create a vector version of my cartoon-self. Since I am not artistically inclined, I decided to use an existing photo of myself as inspiration. I traced the outline of my face from the photo, and continuously used it for reference for contours, colours and gradients. I tried not to make it too realistic in an effort to avoid the uncanny valley.

I find doing such drawings relaxing and it gets the creative juices flowing. I also got to learn a lot about how things work in Inkscape. I particularly love how you can fine tune vector paths to the smallest detail and easily create smooth lines – something I would never be able to do with just my hands using pencil and paper.

Since I use version control for almost everything (including this project), I was able to document the progress of my work. In the end I wrote up a script to fetch all the versions of my image from the first draft to the final image, and created an animation from them showing the progression of the work:

Drawing

My python code for extracting all versions of a file from a SVN repository can be found here. Note that you will need to install the pysvn library for your python distribution for this to work.