12,303,271 members (82,380 online)
Add your own
alternative version

150.4K views
2.6K downloads
29 bookmarked
Posted

# 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++ . 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

 Web Developer Canada
No Biography provided

## Comments and Discussions

 First Prev Next
 a simpler algorithm peatrick29-Aug-07 11:13 peatrick 29-Aug-07 11:13
 Thanks greba :) rzs4-Mar-07 4:45 rzs 4-Mar-07 4:45
 Anagrams generation Girish Mahadevan2-Jan-07 19:12 Girish Mahadevan 2-Jan-07 19:12
 Re: Anagrams generation greba3-Jan-07 3:04 greba 3-Jan-07 3:04
 Re: Anagrams generation(greb) Girish Mahadevan3-Jan-07 18:16 Girish Mahadevan 3-Jan-07 18:16
 Port to CSharp? Doncp22-Dec-06 8:08 Doncp 22-Dec-06 8:08
 Re: Port to CSharp? Doncp24-Dec-06 12:32 Doncp 24-Dec-06 12:32
 Simple Addition for BIG Improvement Humble Programmer9-Nov-05 21:27 Humble Programmer 9-Nov-05 21:27
 file version wrax29-Oct-05 1:49 wrax 29-Oct-05 1:49
 Re: file version greba9-Nov-05 7:32 greba 9-Nov-05 7:32
 nice wrax28-Oct-05 5:02 wrax 28-Oct-05 5:02
 I once had a similar program... Fredrik6-Nov-04 12:11 Fredrik 6-Nov-04 12:11
 Thats Wonder!!! Balkrishna Talele16-Feb-04 23:41 Balkrishna Talele 16-Feb-04 23:41
 Can't compile in VC7 Art Friesz2-Dec-03 6:00 Art Friesz 2-Dec-03 6:00
 Re: Can't compile in VC7 greba2-Dec-03 20:36 greba 2-Dec-03 20:36
 Anagram Solver Bruce Duncan26-Nov-03 18:40 Bruce Duncan 26-Nov-03 18:40
 Notes from a pedant. Iain Clarke26-Nov-03 0:16 Iain Clarke 26-Nov-03 0:16
 Anagram vs. Jumble greba26-Nov-03 15:53 greba 26-Nov-03 15:53
 Re: Anagram vs. Jumble Joe Nellis29-Nov-03 6:25 Joe Nellis 29-Nov-03 6:25
 A very similar problem Joe Nellis25-Nov-03 15:55 Joe Nellis 25-Nov-03 15:55
 Re: A very similar problem greba26-Nov-03 15:59 greba 26-Nov-03 15:59
 Re: A very similar problem treenef8-Jan-05 3:20 treenef 8-Jan-05 3:20
 Re: A very similar problem treenef8-Jan-05 3:24 treenef 8-Jan-05 3:24
 Re: A very similar problem greba10-Jan-05 3:42 greba 10-Jan-05 3:42
 Last Visit: 31-Dec-99 18:00     Last Update: 30-May-16 19:05 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.160530.1 | Last Updated 9 Nov 2005
Article Copyright 2003 by greba
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid