Click here to Skip to main content
Click here to Skip to main content

Jumble Solving Utility

, 9 Nov 2005
Rate this:
Please Sign up or sign in to vote.
This program finds all the words in the dictionary that can be created from a jumbled word.

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++ Smile | :) . 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

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

greba
Web Developer
Canada Canada
No Biography provided

Comments and Discussions

 
Generala simpler algorithm Pinmemberpeatrick29-Aug-07 11:13 
GeneralThanks greba :) Pinmemberrzs4-Mar-07 4:45 
GeneralAnagrams generation PinmemberGirish Mahadevan2-Jan-07 19:12 
GeneralRe: Anagrams generation Pinmembergreba3-Jan-07 3:04 
GeneralRe: Anagrams generation(greb) PinmemberGirish Mahadevan3-Jan-07 18:16 
QuestionPort to CSharp? PinmemberDoncp22-Dec-06 8:08 
AnswerRe: Port to CSharp? PinmemberDoncp24-Dec-06 12:32 
GeneralSimple Addition for BIG Improvement PinmemberHumble Programmer9-Nov-05 21:27 
Generalfile version Pinmemberwrax29-Oct-05 1:49 
GeneralRe: file version Pinmembergreba9-Nov-05 7:32 
Generalnice Pinmemberwrax28-Oct-05 5:02 
GeneralI once had a similar program... PinsussFredrik6-Nov-04 12:11 
GeneralThats Wonder!!! PinmemberBalkrishna Talele16-Feb-04 23:41 
GeneralCan't compile in VC7 PinmemberArt Friesz2-Dec-03 6:00 
GeneralRe: Can't compile in VC7 Pinmembergreba2-Dec-03 20:36 
GeneralAnagram Solver PinmemberBruce Duncan26-Nov-03 18:40 
GeneralNotes from a pedant. PinmemberIain Clarke26-Nov-03 0:16 
GeneralAnagram vs. Jumble Pinmembergreba26-Nov-03 15:53 
GeneralRe: Anagram vs. Jumble PinmemberJoe Nellis29-Nov-03 6:25 
GeneralA very similar problem PinmemberJoe Nellis25-Nov-03 15:55 
GeneralRe: A very similar problem Pinmembergreba26-Nov-03 15:59 
GeneralRe: A very similar problem Pinmembertreenef8-Jan-05 3:20 
GeneralRe: A very similar problem Pinmembertreenef8-Jan-05 3:24 
GeneralRe: A very similar problem Pinmembergreba10-Jan-05 3:42 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140709.1 | Last Updated 9 Nov 2005
Article Copyright 2003 by greba
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid