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.

Apps availble on Apple’s iOS but not on Android

For someone switching from an Android to an iPhone/iPad, they may be interested in exploring what the Apple app ecosystem has to offer that’s missing on Android. A lot of companies and developers still release their new titles to iOS first. Also iOS apps tends to feature more experimentation with design and other creative aspects of the user experience. Here are some such titles:

(Also check out the List of Essential Apps for iOS)

Apps: Not only do apps try to experiment with new designs, but the best ones react playfully to the user touches and gestures

  • Clear – gesture-based to-do list 
  • Paper by FiftyThree – drawing app
  • Tweetbot – twitter client
  • Solar : Weather – gesture-based weather
  • Star Walk – augmented reality star charts and constellations
  • Yahoo Weather
  • Summly – news app
  • Sparrow – mail client

Games: I find that there is not only a wider selection of games on iOS, but also ones with distinct artwork and controls. Here are some stand-out examples:

  • Badlands
  • Tengami – not out yet, but here’s a trailer
  • Clash of Clans
  • Ms. Splosion
  • Mittens

There are continuously new amazing games coming out. I would recommend getting the TouchArcade app to keep on top of them.

Things you can do on Android that aren’t possible on iOS

android-collection

For someone switching from an iPhone/iPad to Andriod, they are interested in knowing what sort of apps are unique to Android that they can take advantage of. Here are a few:

(Also check out the List of Essential Apps for Android)

Full suite of Google apps: Not all Android devices may come with Google’s suite of apps. So make sure you have all the essential ones:

  • Google Search – includes Google Now, and on-device app search
  • GMail
  • Calendar
  • Maps
  • Street View on Google Maps
  • Chrome Browser
  • Hangouts
  • Google Play Music
  • YouTube
  • Google Chrome to Phone

Custom Keyboards: I would recommend the Google Keyboard which allows you to swipe your finger across the keyboard to input text.

Widgets: Newer versions of Android include lock-screen widgets which I find more useful than home-screen widgets. Dashclock Widget is a nice one to try out.

Files: Android gives you access to all the files on your device, so its easier to manage them instead of having to go through iTunes’ awkward app-specific file transfer system. Here are some useful apps in this category

  • ES File Explorer
  • Dropbox (the Android version lets you edit text files, a feature missing from the iOS version)
  • some text editor like Jota Text Editor to edit any text file on the device
  • Adobe Reader

Wallpaper Apps: Innovative apps like Gainos Fresh Wallpapers are available on Android which can automatically update your wallpaper from the most popular stream on Flickr at regular intervals. You can also find a wide swathe of Live Wallpapers apps like GyroSpace 3D and Ditalix as well as regular Wallpapers apps that give you a wide selection of static wallpapers to choose from.

Screensaver: Newer versions of Android come with a screensaver functionality called Daydream. You can set the device to display this when it is docked. Daydream functionality comes baked into apps you have on your device. E.g. Gainos Fresh Wallpapers will show you a stream of popular photos from Flickr. Flipboard shows you latest news stories. You can also turn your device into a photo frame by showing pictures from your device’s Gallery. Or you could keep it simple and just display the time.

Launchers: To completely change the look and feel of your home screen, you can replace the Launcher with a custom one. I haven’t tried any custom Launchers myself, but some of the popular names I’ve heard are Nova Launcher and GO Launcher EX.

Essential Apps for iPhone, iPad and Android

App Wall© Long Zheng

Friends who get a new iPhone, iPad or Android device often ask me what apps to get on their new device. So I’ve compiled a list of the essential apps that are available on both systems. I chose these apps because I feel this collection will allow new users to experience the magical feeling that they are thirsty for from their new gadget.

Also check out the things you can do on Android but not on iOS as well as apps available on iOS but not Android.

  • Google Essentials
    • Google Search – particularly for Google Now and Google Googles (reverse image search)
    • Google Maps
    • Chrome Browser
    • YouTube
  • Social
    • Facebook
    • Yelp
    • Twitter
    • Skype
    • LinkedIn
    • SoundCloud – audio clips from musicians, news networks, etc
    • Vine – share short animated clips
    • Grooveshark – personalized internet radio
    • Last.fm – personalized internet radio
    • Google+
    • Cinemagram – share short animated clips
  • Photos
    • Instagram
    • Pinterest
    • Pixlr Express – simple photo editing
    • Google Goggles – reverse image search
  • Reading
    • Pocket – offline reading
    • Flipboard – news feeds
    • Pulse – news feeds
    • Kobo/Kindle – books
    • Zinio – magazines
  • Food
    • Urbanspoon
    • Foodspotting
    • Epicurious Recipe App
    • OpenTable
  • Music
    • SoundHound – record a clip of music to find out which song it is
    • Songza
  • Movies
    • Flixster
    • Netflix
  • Text/Notes/Documents/Files
    • Evernote
    • Dropbox
    • Skitch
    • Google Drive
  • Location
    • Around Me
    • some transit apps specific to your city
  • Optical
    • Layar – augmented reality
    • Word Lens – real-time translations from camera’s live feed
    • any QR code scanner (e.g. ScanLife for iOS, QR Droid for Android)
  • Utilities
    • Google Translate – quick access to translate
    • any Flashlight app

Games

Don’t download all these games at once, because then they will just sit on your device and you will forget to ever open them up and then after a while just forget why you downloaded it at all. I’d suggest to download and try out 1-2 games per day and only look for something new from this list when you get tired of what you already have.

  • Physics-based
    • Angry Birds franchise
    • Cut the Rope franchise
    • Wimp: Who Stole My Pants
    • Crayon Physics
    • Paper Toss
  • Endless
    • Fruit Ninja
    • Temple Run franchise
    • Doodle Jump
    • Tiny Wings (try Tiny Bird on Android)
    • Jetpack Joyride
    • Super Mega Worm
  • Social
    • Draw Something
  • Puzzles
    • Where’s My Water
    • Pudding Monsters
    • Candy Crush Saga
    • Tangram
  • Platformers
    • Wind-up Knight
    • Vector
    • Spell Sword
    • Megatroid
  • Word Games
    • 4 Pics 1 Word
    • Scramble
    • Words with Friends
  • Music Games
    • Tap Tap Revenge
  • Tower Defense
    • Kingdom Rush
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.

April 27, 2013

Migrating blog away from Posterous

I’m in the middle of migrating away this blog from the Posterous service which is getting shut down. Please excuse the appearance of the site, as well as any broken links, during the migration. Things should be back to normal within 24 hours.

Update: Wow, this is taking much longer than I thought. Should be done shortly though.

Update 2: All done! Things should be back to normal now. I’ve tried to keep the design similar to what it was at Posterous and all old links should still be working. Let me know if you do find any broken links or if any elements are out of place. Thanks!

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

October 27, 2012

How to Suck at Acquiring New Customers – Audible.com

How to Suck at Acquiring New Customers - Audible.com

Just had the worst sign up and getting started experience at Audible.com. I find out of an offer from the Tech News Today podcast for a 1 month free membership and 1 free book. So I decide to sign up thinking it will be a quick 5-10 minute thing. 1 hour later, I am writing a blog post about the horrible experience setting this service up.

The actual sign-up process is quite streamlined. They ask you to set up an Amazon account. I was expecting to setup some sort of account so that’s not bad. Then even though your checkout total is $0, they want you to fill out credit card information. Ok, I understand because they are selling a monthly subscription. So I’ll do that.

But to actually start listening to your first book, is a whole different story. They don’t have a web-app, so you have to download some client. I wanted to listen to the audio books when doing chores around the home, so I decided to download the Windows client. During installation, the client wants me to close all my Chrome windows. I find this really annoying whenever an application asks me to do this because I always have something going on in my browser windows. Anyway, I reluctantly close all Chrome windows. The installation finishes and the application starts up. There’s a button to go to my Online Library where I can go to get books.

So I’m back on the website now. I decide to buy Game of Thrones as my first free book. Oh but wait, I have to pay $22.05 for this book! What happened to my first free book? After some looking around I realize that the 1 free book is based on the fact that they gave me 1 free ‘credit’ when I signed up. And the site claims that:

a very small number of audiobooks and other titles are valued at more than one credit

The Game of Thrones book is priced at 2 credits (as well as every other book in that series). To be fair, some of the other books I looked at, including popular titles like The Hobbit and The Hunger Games, were priced at 1 credit each.

Anyway, I decided to get The Hunger Games in the end. Now its added to my Online Library, and there is a button to download the book. But clicking on the button tells me that I don’t have the Windows client installed and that I need to download it. Even though I clearly have it installed and running! After getting frustrated, I call up Customer Service who direct me to switch off the ‘Software Verification’ setting in my online account because they don’t have good support for Google Chrome. Its awesome that you can’t find this information on their help pages.

So I hang up with Customer Service and am finally ready to have my computer read out my audio book to me. But no, it wants me to Activate my client before I can use it (even though it let me download books without activation). Still, this would be fine, except that it doesn’t actually accept my valid username and password! Hats off to Audible for making it really easy for me to give away my credit card information but making it nearly impossible for me to get the service I want, while pretending to be a legitimate business.

The Audible iPhone app worked fine – I was able to download and listen to books. But the Windows client would just not let me activate it. I called up Customer Service again, and they had no clue what was wrong. The only thing that I could think up was that I had an extraordinarily long password. I mentioned that to Customer Service and they said that it shouldn’t have any effect. Also I was able to log into the website and the iPhone app using this password. After getting no where with Customer Service, I hung up and decided to change my password to a shorter one. Lo and behold, suddenly I was able to activate the client. What a horrible bug to have, and be completely oblivious to its existence.

The only good thing was that I was able to change my password back to the long one after activation and the client kept working.

Great job Audible! You make me seriously doubt if I want to renew my membership next month.