473,580 Members | 2,946 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

string combination algorithm for a "word descrambler"

Greetings.

I'm working on a program that will "descramble " words. Think of a word
scramble game where there is a list of characters, and several blank
spaces to denote the word(s) that you are to come up with from the list.
i.e.(* denotes a space): _ _ _ _ _ * _ _ _ _ _ _

characters: .hwodlelrlo

answer: hello world.

So, implemented as a c/c++ program, you would have something like:
<begin pseudo-c code>
char letters[11] = {'.','h','w','o ','d','l','e',' l','r','l','o'} ;

char PossibleWordOne[100][5];
char PossibleWordTwo[100][6];
//WordOneLength = 5;
//WordTwoLength = 6;
/* Ultimately, the goal is to not know the number of words or their
lengths or even the scrambled characters before execution, but this will
work for the example. I got the 100 because there should be no way of
getting more than 100 possible 'real' words*/
/* In order to make sure the combination of characters is a real word,
verify() will check it against a word list and return True or False Swap
will be a simple function (I hope it'll be simple anyways) that will swap
the characters into the next combination.*/

Permu()
{
static int counter = 1;
static int possibles = 0;
while (counter != 11!) /* Since there are 11! possible combinations */
if (!(Verify(Swap( letters*))
{ counter++;
Permu();
}
else
{
PossibleWordOne[possibles][] = letters*;
possibles++;
counter++;
Permu();
}

<end pseudo-c code>

Well, what do guys think? Any suggestions or sample code would be greatly
appreciated. In order to optimize performance, I would like to load the
word list directly into memory, and preferably have the words categorized
by length. This way, I can find the possible words for the longest word
first, and then go to the next longest. For example, let's say that I find
two possible combinations for the five-letter word. Then, I can seperate
them into two cases to find the four-letter word. Each case would have a
char array with 5 less chars than the original, which should make it a lot
faster to find the second word. Then let's say that only case two turns up
a possible combination for the four letter word. case one could then be
disguarded and you could move on to the next word... and on and on.
Anyways, that's what I've got so far... Like I said any suggestions would
be greatly appreciated.

Thanks,
Gaines

Jul 22 '05 #1
3 6008
"gdogg1587" <NO*********@SP AMearthlink.net > wrote in message
news:fb******** *************** *******@localho st.talkaboutpro gramming.com...
Greetings.

I'm working on a program that will "descramble " words. Think of a word
scramble game where there is a list of characters, and several blank
spaces to denote the word(s) that you are to come up with from the list.
i.e.(* denotes a space): _ _ _ _ _ * _ _ _ _ _ _

characters: .hwodlelrlo

answer: hello world.

So, implemented as a c/c++ program, you would have something like:
<begin pseudo-c code>
char letters[11] = {'.','h','w','o ','d','l','e',' l','r','l','o'} ;

char PossibleWordOne[100][5];
char PossibleWordTwo[100][6];
//WordOneLength = 5;
//WordTwoLength = 6;
/* Ultimately, the goal is to not know the number of words or their
lengths or even the scrambled characters before execution, but this will
work for the example. I got the 100 because there should be no way of
getting more than 100 possible 'real' words*/
/* In order to make sure the combination of characters is a real word,
verify() will check it against a word list and return True or False Swap
will be a simple function (I hope it'll be simple anyways) that will swap
the characters into the next combination.*/

Permu()
{
static int counter = 1;
static int possibles = 0;
while (counter != 11!) /* Since there are 11! possible combinations */
if (!(Verify(Swap( letters*))
{ counter++;
Permu();
}
else
{
PossibleWordOne[possibles][] = letters*;
possibles++;
counter++;
Permu();
}

<end pseudo-c code>

Well, what do guys think? Any suggestions or sample code would be greatly
appreciated. In order to optimize performance, I would like to load the
word list directly into memory, and preferably have the words categorized
by length. This way, I can find the possible words for the longest word
first, and then go to the next longest. For example, let's say that I find
two possible combinations for the five-letter word. Then, I can seperate
them into two cases to find the four-letter word. Each case would have a
char array with 5 less chars than the original, which should make it a lot
faster to find the second word. Then let's say that only case two turns up
a possible combination for the four letter word. case one could then be
disguarded and you could move on to the next word... and on and on.
Anyways, that's what I've got so far... Like I said any suggestions would
be greatly appreciated.


I've written a similar program before, just for a laugh. To determine the
"legal" words that one can make, there's a simple, efficient approach that
doesn't take too much time to implement. Simply scan the entire list of
"legal" words, testing if it is a subset of the scrambled letters. This
tends to be pretty quick (virtually instantaneous on my machine), as there
are only around 180,000 words in the English language. Then, for each word
you can make that is of an appropriate length, examine each pair (or
whatever size tuple) to see if, together, they "use up" all of the scrambled
letters. Of course, you may have multiple correct answers. For other
programs, it may pay to try to do something "smarter", but, in my
experience, nothing fancy is required for a program like this. However, it
might get out of hand if you had a lot of letters that could make many
words, and there are many words in the sentence.

--
David Hilsee
Jul 22 '05 #2
Hmm... That's a pretty good idea. 18,000 is a lot less than 11! And a whole
lot less than 100!. And, I could categorize the word list by length of word
to make it even faster! That's great! Thanks.

Jul 22 '05 #3
Hmm... That's a pretty good idea. 18,000 is a lot less than 11! And a whole
lot less than 100!. And, I could categorize the word list by length of word
to make it even faster! That's great! Thanks.

Jul 22 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
13559
by: The Roys | last post by:
Hi Im doing something wrong in quitting the Word.Application in my VB program. I have General Declarations Dim AppWord As Word.Application Form_Load() Set AppWord = CreateObject("Word.Application")
4
16157
by: Microsoft | last post by:
I'm trying to display a word document inside a web page, but everytime I do I get this error: Error Type: Microsoft VBScript runtime (0x800A0046) Permission denied: 'CreateObject' Does anybody know the correct way to do this? I don't want to link to a document, but rather display a word file inside the asp page.
3
5335
by: Greg Andora | last post by:
Hello, I've had an ASP page that worked for at the minimum for a year and now it is acting very odd and I need some help to fix it. What my page does/did is creates a Word.Application object and a new document from a template. It then proceeds to fill in a bunch of the information on the word document using bookmarks and data from a database....
2
10232
by: MaxiWheat | last post by:
Hi, I am using a software that uses MS Word to create PDF files. When I try to run the sample code (ASP 3.0), I get an error on this statement : Set oWord = Server.CreateObject("Word.Application") That error says : The call to Server.CreateObject failed while checking permissions. Access is denied to this object.
1
4605
by: Petar Popara | last post by:
I did everything as Kevin Yu explained here: http://tinyurl.com/9tw6c but it doesn't work. :( I'm using WinXP Pro SP2 and latest IE. I don't have Office 2003 installed. What should I do?
4
7998
by: Darryl Kerkeslager | last post by:
Below is a section of the code I use to open Word with late binding, insert text at the selected bookmarks, and make Word visible. Everything works fine. However, I also have some Word check boxes, that I cannot figure out how to make 'checked'. I am not allowed to alter the layout of the form; it must be a check box. Up until now, I have...
2
3173
by: Claus - Arcolutions | last post by:
I got a word document as a stream, and I want to get the text from the word document. But I cant seem to find anything to use for that purpose. The "Microsoft office ?.object" com reference, only include functionality to read from a file (as far as I know). I looked a little on the structure of the document, but it doesnt seem to have any...
5
1428
by: Filip De Backer | last post by:
hi everyone, I want a textbox with word layout. And than save this text to a field in a sql server. how can I do that? thanks for the answers Filip
1
1462
by: Shar Shar | last post by:
Hi All, Actually I want to use "Word.ApplicationClass" class for opening a word file. And do following things, 1) Open word file. 2) Insert text in bookmark field. 3) Print resultant file as pdf. Has anyone solution how can I do this programmatically in C#.
0
7854
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
8296
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
0
8157
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6533
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
5349
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3790
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3806
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2295
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1394
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.