English word list for solving Jumble puzzle

I’ve been playing around with the iPhone SDK, and decided on a “Jumble Solver” as my first as a good learning project. It’d include a whole bunch of objective C and general programming concepts – Recursion, delegation, Interface builder, inheritence, sqlite.

My general approach was to build a decision tree with the available characters in the jumble, and compare the leaf nodes with an english dictionary. Finding a sqlite database of words … or rather a list of words was really hard. I stumbled upon a word list in text format found at the national puzzle solvers website. To dump that into a database I used the following simple ruby script. You’ll notice I limited the words to less than 7 characters. The search algorithm is n! complexity so limiting the jumble to 7 characters proved optimal performance. :

require ‘sqlite3.rb’

word_list.each do |word|
if word.length <8
db.execute(“INSERT INTO words (word) VALUES (?)”, word.chomp)

2 thoughts on “English word list for solving Jumble puzzle

  1. I cannot understand which process are you referring to. Why the growth of the algorithm would be n! . Now a string with n characters could be permuted in n! ways. You do not need to generate alls the n! permutations of a jumble and then match it with the dictionary.

    What you need is to make the dictionary works and the jumble words in an ordered permutation. That is if say you have a jumble word in a variable str1, and you read a dic word into str2 . what you have to do is sort the characters of str1 and str2 and check if they are the same string. That is because a jumble word has same characters just rearranged in different positions so the increasing sequence of the characters would have the same permutations. Thus the in worst case you would need at most n comparisons to find a match where n in the number of words in the database file.

    Also you can index the words after sorting there characters into a trie, because two jumble word will have the same sorted pattern so they will end up in one branch of the trie, that is a collision. After you have successfully indexed the trie, then you just get the jumble word sort the characters within it and apply it in the trie, if you end up in a leaf then all the collision entries in that leaf are the solutions to the jumber word. In this method the indexing will take some good amount of time, (appx 3secs in my computer for the linux.words file) then after that the searching is instant. Theoretically it will depend on the length of the input word only, as each character is indexed and checked if the path exists in the tree with the sorted input sequence.
    You can find these stuffs in my place: http://phoxis.org/2009/05/28/jumble-word-solver/

    Although the codes have undergone a lot of changes and they are still to be uploaded, but the essence is the same.

  2. similarly you can construct a single player scrabble solver with this engine, be selecting subsets from a handful of characters, and searching in the trie with them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s