?
Solved

Word Generator

Posted on 2006-03-30
6
Medium Priority
?
1,368 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!
0
Comment
Question by:MasterThai
6 Comments
 
LVL 4

Expert Comment

by:tobydavid
ID: 16332724
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.?
0
 
LVL 86

Expert Comment

by:Mike Tomlinson
ID: 16333385
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
0
 
LVL 2

Author Comment

by:MasterThai
ID: 16333533
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
0
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
LVL 85

Expert Comment

by:ozo
ID: 16338427
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?
0
 

Expert Comment

by:MysticalNeopian
ID: 16353010
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.

0
 
LVL 85

Accepted Solution

by:
ozo earned 495 total points
ID: 16353272
#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);
  }
}
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
We live in a world of interfaces like the one in the title picture. VBA also allows to use interfaces which offers a lot of possibilities. This article describes how to use interfaces in VBA and how to work around their bugs.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question