Jumble Solving Utility

• Download demo project - 635 Kb
• Download source - 2.80 Kb

Introduction

This program finds all the words in the dictionary that can be created from a jumbled word.

Background

I've never been excellent at solving Jumbles, mainly because my vocabulary doesn't include some of the odd-ball words they like to use. A Jumble is a word problem that can be found in newspapers and on some websites like jumble.com. A basic Jumble problem is a bunch of letters that form a word when re-arranged. The solution to the problem is an anagram of the original jumbled word, Ex. lbujme -> jumble. This program will take the bunch of letters and give a list of any words (found in the dictionary) that can be formed from those letters.

Using the code

To use the code in your own application just include trie.cpp and trie.h to your project source, and #include "trie.h" when you want to use the class.

A very simple use of the class CTrie:

//Create the List
CTrie* List = new CTrie();

//Add a word to the List
List->AddWord("jumble");

//Get a vector of words from the List
vector<CHAR*>* all = List->GiveWords("lbujme");

//Output the results
if (all && !all->empty())
{
    vector<CHAR*>::const_iterator vai;
    int cnt = 0;
    for (vai = all->begin(); vai != all->end(); vai++, cnt++)
        cout << cnt + 1 << " " << *vai << endl;
}
else
    cout << "none" << endl;

Algorithm Outline

My algorithm uses the basis that the same number of any letter must occur in a word as the given jumbled word for the word to be formed from the jumbled word. In other words lbujme has: 1 B, 1 E, 1 J, 1 M, 1 L, 1 U, and jumble has: 1 B, 1 E, 1 J, 1 M, 1 L, 1 U. These are the same therefore you can make jumble out of lbujme. The data structure of my algorithm uses a binary tree. The tree starts off with the root node which contains a list of all the words with zero occurrences of the letter 'a'. The root node then can have left and right pointers. The left pointer points to the node with zero occurrences of the letter 'a' and zero occurrences of the letter 'b'. The right pointer points to the node with one occurrence of the letter 'a'. This can be expanded generally to say that going left in the tree means you move to the next letter. To go right means you add an occurrence of the current letter.

History prior to CodeProject

The first time I wrote my Jumble solving program was about five years ago. It took about five minutes to find all the possible words for a bunch of six letters. Eight letters I estimated would take half a day. I never did find out how long it took. Also the original program was written in Turbo Pascal; I could say that was the reason for the slow algorithm but must blame the programmer.

The original algorithm was to arrange the bunch of letters in all there possible combinations (including repeats of letters) and check if it was a word. For a six letter word this gives us 6^6 = 46656 words to check. Not too bad but I was also scanning the dictionary file every single time to check if the word existed or not. This was the major bottleneck, so I read all the words into memory once, and scanned the list. This improved the search time considerable but was still incredibly slow for eight bunches of letters. Also the basis of my algorithm was a whole lot of if statements, making expanding to anything beyond eight letters tedious at best.

I eventually improved the algorithm to remove repeats of letters. This meant that instead of 6^6 = 46656 words to check I had to check 6! = 720 words. A vast improvement. Years passed...and I decided to code the Jumble program again, this time in C++ :). I did exactly the same algorithm and still came across a huge barrier when using words greater then size of eight. The problem sat in the back of my mind and a new algorithm popped into my head. I could count the number of times a letter occurred in the jumbled set of letters and count the number of times a letter occurred in a word and compare the two. This worked wonders and improved the algorithm drastically. But, I had no nice data structure for finding if a word belonged to a certain jumbled set.

University courses gave me trees, from which my jumble tree was born. Now the program takes a few seconds to load up and a few to shut down but searching is 26 pointers away (in the worst case). I've cleaned up the code, separated it into classes and posted it here. Obviously this program is pointless with this web site but has been an adventure thus far. I'm sure improvements can still be made, and look forward to feedback.

Possible Future Updates

Implement a Directed Acyclic Word Graph [DAWG] structure to save memory, and time stepping through structure.
Test other algorithms.

History

• 8 November 2003 - v1.0
  First public release

• 2 December 2003 - v1.1
  Changed class and file names
  Changed return type of GiveWords() to vector<CHAR*>*
  Added .NET Demo Project