We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

Word Generator

MasterThai
MasterThai asked
on
Medium Priority
1,388 Views
Last Modified: 2008-02-20
Ok I'm trying to make a srable word generator but I really don't have a clue on how to start it out.
If anyone would be willing to help me out with a basic program that does this and with some ideas on how to make it faster
Eg if its done with recursion it'd probably be pretty slow

Thanks in adv!
Comment
Watch Question

Did you mean "Scrabble"?  so that you are looking for all possible words using all 7 letters, all words using any 6 out of the 7 letters, any 5 of the 7, etc.?
Mike TomlinsonHigh School Computer Science, Computer Applications, Digital Design, and Mathematics Teacher
CERTIFIED EXPERT
Top Expert 2009

Commented:
Hi MasterThai,

What programming language are you working in here?

I once developed a fast routine in VB.Net using a DAWG:
http://www.wutka.com/dawg.html

First I found a word list I was happy with:
http://www.google.com/search?complete=1&hl=en&q=word+list

Then I built a DAWG structure from the word list.  I didn't do any kind of optimization with it.  I just basically built a nested HashTable system.  The root HashTable had each letter of the alphabet and represented words that begin with that letter.  Then each letter had a HashTable associated with it that represented the second letter in a possible word and so on...

When you start making permutations of all possible tile combinations you can quickly eliminate an entire series of permutations by using the DAWG structure to determine if there are no possible words that can made with that combinations current prefix.

For example, what if your tiles included a "q" and a "z"?  Let's say your tile combination generator is current building permutations that start with "zq"?????.  If the DAWG says that there are no words that begin with "zq" then you can stop making permutations with that series and move on to the next letter.  This is what makes it fast.  This can be determined quickly becuase the HashTable associated with the first letter "z" would not have an entry for "q" indicating that no words begin with "zq".

If you simply made all permutations of the tiles and checked to see if any of those permutations match any WHOLE words in your list, then you may make literally thousands of combinations that could have been avoided altogether with the DAWG approach.

~IM

Author

Commented:
Sorry thought I posted C/C++ I Don't have .Net
So I'm using Dev Cpp
and yeah im trying to make a scrabble word finder
basically I'm looking for something like this right now

Scrabble Word Generator...
Step 1 Get Letters...
Search 7 digit words that have each letter in it
Search 6 ...
Search 5 ...

Take Top 20 (Point Valued Words)
Put in a Text File
ozo
CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
Do you have a dictionary of valid Scrabble words to work from?
Do you have any letters on the board to work around, or double or triple letter of word squares to take into acount?
I'm not trying to make something to play the game I'm just trying to make a program that searches a txt file and finds all the words possible based off the given letters.

CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015
Commented:
#include <ctype.h>
#include <stdio.h>
int value[]={ /* assuming english version */
  1,/*A*/
  3,/*B*/
  3,/*C*/
  2,/*D*/
  1,/*E*/
  4,/*F*/
  2,/*G*/
  4,/*H*/
  1,/*I*/
  8,/*J*/
  5,/*K*/
  1,/*L*/
  3,/*M*/
  1,/*N*/
  1,/*O*/
  3,/*P*/
  10,/*Q*/
  1,/*R*/
  1,/*S*/
  1,/*T*/
  1,/*U*/
  4,/*V*/
  4,/*W*/
  8,/*X*/
  4,/*Y*/
  10,/*Z*/  
};
main(){
  char word[99];
  struct{
    int points;
    char word[9];
  }top20[21];  
  FILE *f=fopen("wordlist","r");
  char *p;
  int i;
  if( !f ){
    perror("worklist");
    exit(1);
  }
  for( i=0;i<20;i++ ){ top20[i].points=0; top20[i].word[0]='\0'; }
  while( p=fgets(word,99,f) ){
    int points=0;
    if( strlen(word)>8 ){ continue; }
    while( isalpha(*p) ){
      points+=value[toupper(*p++)-'A'];
    }
    for( i=19;i>=0 && points > top20[i].points;i-- ){
      top20[i+1] = top20[i];
    }
    if( i<19 ){
      top20[i+1].points=points;
      strcpy(top20[i+1].word,word);
    }
  }
  for( i=0;i<20;i++ ){
    printf("%2d: %s",top20[i].points,top20[i].word);
  }
}

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.