Afternoon Apps: Descrumbled

At events like Startup Weekend, you try to build an idea in a weekend. I wanted to see if I could do something even faster. So I bring you Afternoon Apps, where I build an app in a single afternoon.

Descrumbled is an app for solving Boggle puzzles. Boggle is a word game where you have to find words hidden in a grid of letters. The app lets you enter a board and quickly generate all possible words that can be found in the puzzle. It uses the SOWPODS dictionary to see if a word is valid or not.

I was able to build the app in an afternoon because it is very simple. It lets you pick two board sizes, 4×4 and 5×5. Then you can enter the board, press solve, and seconds later you get a list of all the words. Pressing a word will give you the definition thanks to iOS 5’s dictionary integration.

The hard part was actually solving the puzzle. Generating all the possible words in the puzzle and checking them against a 230,000 word dictionary is no trivial task. I’m going to let you in on a little secret. I didn’t write the boggle solver in a single afternoon. I had written it before by working on it a few hours a day for 3 or so days. It was a programming challenge I found online and I tried to do it. It’s actually a lot of fun solving a problem like this. I get to think about tries and binary searches. Things I haven’t actually had to think much about since college. My first stab at it took about 3 minutes to solve a 4×4 puzzle. Since most online Boggle rounds are 1 or 2 minutes, this obviously wasn’t acceptable. I improved my algorithm and now it takes ~1 second to solve a 5×5 puzzle.

So what did I actually do in an afternoon? I built a UI around my boggle solver class. I had to get a C++ class working on the iPhone (which is actually really easy) and build a UI for entering the board. The squares on the board auto advance the cursor through a grid of UITextFields. It also makes sure the board is complete before it tries to solve. Then I had to make a way to clear the board and switch between a 4×4 grid and a 5×5 grid. The word list UI is just a very simple UITableView. When you press a row, it will open up the definition of the word in a¬†UIReferenceLibraryViewController (new in iOS 5).

That’s it. The app is meant to be simple and easy to use. It really is a minimum viable product. I did this as an exercise to see if I could build a simple app and submit it to the app store in an afternoon. I want to keep doing these Afternoon Apps every few weeks. I’d love to see if other people have done similar things and find out how your experience went.

The app should be live any day now. Check it out!

This entry was posted in Afternoon Apps and tagged , , , . Bookmark the permalink.

7 Responses to Afternoon Apps: Descrumbled

  1. tom says:

    Neato! Now you just need to tweak so you can take a picture of the “board” and have it auto-solve. The new point of the game will be, who can write out the results the fastest. :)

  2. Pingback: Afternoon Apps 2: Scrumbled | farp.blog

  3. Pingback: Where does my blog traffic come from? | farp.blog

  4. Howard Katz says:

    Wow, that’s fast! Where did you get your dictionary? I’d *love* to play around with something that large.
    Howard

  5. Randall says:

    I’m pretty sure I find out it on sourceforge but I can’t find the project anymore. Here’s a copy on GitHub https://github.com/stevenklise/RWET_PoeticAutomaton/blob/master/sowpods.txt

  6. Kalle Andersson says:

    Hello.
    I’m working on a similar project for educational purpose (self taught).
    And my algorithm takes about 30 sec to complete, which ain’t good enough.

    I would greatly appreciate if you could tell me which changes you made to make your algorithm take ~1 sec instead of 3 min.
    Maybe even tell the name of the algorithm?

    If you for some reason don’t want to make it public but still want to help out, you can reach me at “Kalle.A-_-@hotmail.com”

    Anyway, impressive :)

    Take care, Kalle.

  7. Pingback: Afternoon Apps: Captionator | farp.blog

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>