[splicecube]

In school we are writing a program that pull a random word from a dictionary. Scrambles it, and then asks the userto input words that can be made out of the 6 letter word. There is also a function in the program called "cheat" that happens when the user enters "c". This is where my problem exists. So for the cheat function I use a for loop nested 6 times to account for every possible combination of 3,4,5,& 6 letter words that can be found out of the 6 letter word that was pulled from the dictionary. It all works fine and dandy, repeats are checked for and should not displayed and all the "cheats" are shown.. The problem is that wayyyyy too many words are showing up. For example lets say I have the word "rumors", an extra word that would display as a "cheat" would be murmur because it would use the 'm' and 'u' twice. How do I make it so that such words are ignored. Can anyone tell me what exactly I am missing to make it function like it should? Thanks in advance />

I have tried blanking out a character after it is checked so it is not checked for again but the program just crashes,
I have also tried swapping the used element with the first and then ignoring the first but it still just crashes.

#include <iostream>

#include <string>

#include <fstream>

#include <cstdlib>

#include <ctime>

using namespace std;


void showBlanks(int num1, int num2, int num3, int num4);

void numerate(char enterArray[][45])
{
     
////THIS IS FOR TEST PURPOSES ONLY. DELETE THIS EVENTUALLY.
//int count=0;
//int number=enterArray.size();
//for (int i=0;i<number;i++)
//{
//  count++;
//    
//}
//cout<<"\n"<<count;
//
//
//
//

}

 bool searchDictionary(char dictionary[][45], char word[],int limit)
{
     int low, mid, high;		// array indices for search

   low = 0;
   high = limit - 1;
   while ( low <= high)  {
      mid = (low + high) / 2;

      // printRow( array, low, mid, high); // display to show progress

      if ( strcmp(word,dictionary[ mid])==0)
      {
     // strcpy(dictionary[mid],"");
      //dictionary[mid]="                                            ";
         return true;
         }
         
      else if (strcmp(word,dictionary[ mid])<0)
         high = mid - 1;
      else
         low = mid + 1;
   }
  return false;         
 }
 
 bool noRepeats(char entered[7],int count)
 {
      int testCount;
       char possible3 [27][4];
   char possible4 [256][5];
   char possible5 [3125][6];
   char possible6 [46656][7]; 
   
    if (strlen(entered)==3) 
    {
       for (int i=0; i<27; i++)   
       {
         strcpy(possible3[i],entered);
           
           for (int j=count-1; j>=0; j--)
           {
          //   cout<<"J is:"<<j<<" ^"<<possible3[j]<<"^ -> "<<"I is "<<i<<" "<<possible3[i]<<endl;
            if (strcmp(possible3[j],possible3[i])==0) return false;
            
            }
           }                                              
           }
                            
     if (strlen(entered)==4)
     { 
        for (int i=0; i<256; i++)   
         {
          strcpy(possible4[i],entered);  
           
             for (int j=count-1; j>=0; j--)
             {
           // cout<<"J is:"<<j<<" ^"<<possible4[j]<<"^ -> "<<"I is "<<i<<" "<<possible4[i]<<endl;
            if (strcmp(possible4[j],possible4[i])==0) return false;
            
            }
           }  
           }
           
      if (strlen(entered)==5) 
      {
      for (int i=0; i<3125; i++)   
         {
          strcpy(possible5[i],entered);  
           
            for (int j=count-1; j>=0; j--){
            //  cout<<"J is:"<<j<<" ^"<<possible5[j]<<"^ -> "<<"I is "<<i<<" "<<possible5[i]<<endl;
              if (strcmp(possible5[j],possible5[i])==0) return false;
              }
           }  
           }
           
       if (strlen(entered)==6) 
      {
      for (int i=0; i<46656; i++)   
         {
          strcpy(possible6[i],entered);  
          
             for (int j=i-1; j>=0; j--){
           //   cout<<"J is:"<<j<<" "<<"^"<<possible6[j]<<"^ -> "<<"I is "<<i<<" "<<possible6[i]<<endl; 
              if (strcmp(possible6[j],possible6[i])==0) return false;
              }
           }  
           }
           
           for (int i=0;i<27;i++)
          // {
        //   cout<<possible3[i]<<endl;
           //testCount++; cout<<testCount<<endl;}
      
    return true;
      }

void twistWord(char scramble[7])
{
     char tempArray[7]={scramble[0],scramble[1],scramble[2],scramble[3],scramble[4],scramble[5]};
     
 srand(time(NULL));
rand();
int n1=0;
int n2=0;
int n3=0;
int n4=0;
int n5=0;
int n6=0;

n1=rand()%6+1;
do{n2=rand()%6+1;}while(n2==n1);
do{n3=rand()%6+1;}while(n3==n2||n3==n1);
do{n4=rand()%6+1;}while(n4==n3||n4==n2||n4==n1);
do{n5=rand()%6+1;}while(n5==n4||n5==n3||n5==n2||n5==n1);
do{n6=rand()%6+1;}while(n6==n5||n6==n4||n6==n3||n6==n2||n6==n1);
//}while (n1!=n2!=n3!=n4!=n5!=n6);

int randArray [7]={n1,n2,n3,n4,n5,n6};

for (int i=0;i<6;i++)
{

   tempArray[i]=scramble[randArray[i]-1]; 
    
}


for (int i=0;i<6;i++)
cout<<tempArray[i];


   
     }

void setWord(){}



void showWords(char wordToUse[],char dictionary[][45],char numLetters3[4],bool blanks)
{
 
//    int arraySize=0;
//    char cheater[arraySize][7];
    int rowCount=-1;
     int testCount=0;
     int count3=0; int count4=0; int count5=0; int count6=0;
   //  int a=0; int b=0; int c=0; int d=0; int e=0; int f=0; 
   int slot=0;
   //  char tempWordArray[];
     char letter1, letter2, letter3, letter4, letter5, letter6; 
    // string check;
    // char blank='a'; 
//cycle through every 3 letter word possibility to find if it is a word
for (int x=0;x<6;x++)   
{
   
  //  cout<<"hi";
    letter1=wordToUse[x];
 
           for (int a=0;a<6;a++)
           {
               
               letter2=wordToUse[a];  
               
           // char temp=  wordToUse[0];
//            wordToUse[0]=wordToUse[a];
//            wordToUse[a]= temp;    
 
                    for (int b=0;b<6;b++)
                    {
  
                        letter3=wordToUse[b];
                       // wordToUse[b]='-';
                        char checkWord3[4]={letter1,letter2,letter3};

                        if (searchDictionary(dictionary,checkWord3,7660)==true)
                        {
                       bool test1= noRepeats(checkWord3,count3);
                        count3++;
                        cout<<test1<<endl;
                       if (blanks==false/*&&test1==true*/)
                              cout<<checkWord3<<endl;            
                                          
                        }
                         
                          for (int c=0;c<6;c++)
                              {
                              letter4=wordToUse[c];
                            //  wordToUse[c]='-';
                              char checkWord4[5]={letter1,letter2,letter3,letter4};
                              if (searchDictionary(dictionary,checkWord4,7660)==true)
                               {
                                bool test2= noRepeats(checkWord4,count4);
                                   count4++;
                                   cout<<test2<<endl;
                                   
                                   if (blanks==false/*&&test2==true*/)
                                   cout<<checkWord4<<endl;            
                                   

                               }
                                   
                                   for (int d=0;d<6;d++)
                                       {
                                        letter5=wordToUse[d];
                                       // wordToUse[d]='-';
                                        char checkWord5[6]={letter1,letter2,letter3,letter4,letter5};
                                        if (searchDictionary(dictionary,checkWord5,7660)==true)
                                           {
                                             bool test3 = noRepeats(checkWord5,count5);
                                             count5++;
                                             cout<<test3<<endl;
                                             if (blanks==false/*&&test3==true*/)
                                             cout<<checkWord5<<endl;            
                                             
                                           }
                                               
                                               for (int e=0;e<6;e++) 
                                                   {
                                                    letter6=wordToUse[e];
                                                  //  wordToUse[e]='-';
                                                    char checkWord6[7]={letter1,letter2,letter3,letter4,letter5,letter6};
                                                    if (searchDictionary(dictionary,checkWord6,7660)==true)
                                                        {
                                                           bool test4=noRepeats(checkWord6,count6);
                                                           count6++;
                                                           cout<<test4<<endl;
                                                           if (blanks==false/*&&test4==true*/)
                                                                 cout<<checkWord6<<endl;            
                                                                
                                                        }
                                                        
                    }
           }
}  
}
}
}

//for (int z=0; z<arraySize; z++)
// cheater[z]= 

cout<<count3<<count4<<count5<<count6<<endl;

if (blanks==true)
showBlanks(count3,count4,count5,count6);
//e//lse 
}

void showBlanks(int num1, int num2, int num3, int num4)
{
      cout<<num1<<endl;
       cout<<num2<<endl;
        cout<<num3<<endl;
         cout<<num4<<endl;
     for (int a=0; a<num1; a++ ){
        // cout<<num1<<endl;
      if (a%3==0)
      cout<<"\n"<<"___"<<" ";
      else
      cout<<"___"<<" ";
      }
      
      for (int b=0; b<num2; b++ ){
        //   cout<<num2<<endl;
      if (b%3==0)
      cout<<"\n"<<"____"<<" ";
      else
      cout<<"____"<<" ";
      }
      
      for (int c=0; c<num3; c++ ){
        //   cout<<num3<<endl;
      if (c%3==0)
      cout<<"\n"<<"_____"<<" ";
      else
      cout<<"_____"<<" ";
      }
      
      for (int d=0; d<num4; d++ ){
       //    cout<<num4<<endl;
      if (d%3==0)
      cout<<"\n"<<"______"<<" ";
      else
      cout<<"______"<<" ";
      }
      cout<<endl<<endl;
}

//void cheat(){}
    
 
void displayIntro()
{
cout<<" hello there"<<endl;
         
     }
     
void static displayBoard(int letters3found, int letters4found, int letters5found, int letters6found,
                  char arrayFor3s[][4],char arrayFor4s[][5],char arrayFor5s[][6],char arrayFor6s[][7])
{
// for (int count =0; count < letters3found; count++)
//     {
//     strcpy(letters3[count],"___");
//     if (count%3==0)
//     cout<<"\n"<<letters3[count]<<" ";
//     else 
//     cout<<letters3[count]<<" ";
//     }   
}

int main ()

{
    char wordToUse[45];
    bool blanks=true;
    char entry;
    int letsFound3=0;
    char blank3[4]="___";
    char blank4[5]="____";
    char blank5[6]="_____";
    char blank6[7]="______";
    

    
// letters3= new char[10];

// for (int count =0; count < dynamo; count++)
//     {
//     strcpy(letters3[count],blank3);
//     if (count%3==0)
//     cout<<"\n"<<letters3[count]<<" ";
//     else 
//     cout<<letters3[count]<<" ";
//     } 
     
 // ={"___"};
////for (int count=0;count<dynamo; count++)
// letters4= new char[10];
// // ={"____"};
// letters5= new char[10];
// // ={"_____"};
// letters6= new char[10];
 // ={"______"};


    displayIntro();
    int letterCount;
    
    char words[7660][45];
    ifstream dictionary("dictionary.txt");

    srand(time(NULL));
    int n = 0;

    while(dictionary >> words[n])

    {
        n++;
    }
    
    rand();


do{
    int r = rand() % 7660;
    //wordToUse= words[r];
    strcpy(wordToUse,words[r]);
    
} while ((strlen(wordToUse))!=6);
  cout<<wordToUse<<endl;
  twistWord(wordToUse);
 
 //system("pause"); 
  
  //***********cout<< "word: " << wordToUse << "\n";
  
//Splitting the String into a char array
//char splitString[6];

//for (int i=0;i<=6;i++)
//{
//    splitString[i]=output[i];
//    cout<<splitString[i]<<endl;
//}

  cout<<endl<<endl;
//  displayBoard(w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,w12,w13,w14,w15,w16,w17,w18,w19,w20,w21,w22,w23,w24,w25,w26);          
showWords("trucks",words,blank3/*,letters4,letters5,letters6,*/,true);

cout<<"Possible commands are:"<<endl;
cout<<"    x  to exit the game"<<endl;
cout<<"    t  to twist the letters into a different order"<<endl;
cout<<"    s  to set the word to letters of your choosing"<<endl;
cout<<"    c  to cheat, displaying all words"<<endl<<endl;
cin>>entry;



if (entry =='x') /*closes the program*/;
else if (entry=='t') /*twistWord();*/;
else if (entry=='s') setWord();
else if (entry=='n') numerate(words);
else if (entry=='c')
{
showWords("trucks",words,blank3/*,letters4,letters5,letters6,*/,false);
cout<<"hi";
}

cout<<endl<<endl; 
system("pause");
    


}

[Skydiver]

Not directly related with your problem, but find an indent style that you like, and apply it consistently. It was very hard to read your code, and frankly I just gave up because of the poor formatting of the code. If your are going to present that much code, you'd want to present it in a readable format for others to be able to read and understand easily.

[splicecube]

Skydiver, on 18 March 2013 - 06:45 PM, said:

Not directly related with your problem, but find an indent style that you like, and apply it consistently. It was very hard to read your code, and frankly I just gave up because of the poor formatting of the code. If your are going to present that much code, you'd want to present it in a readable format for others to be able to read and understand easily.

[#define]

There is a function to find permutations.

next_permutation

[splicecube]

#define, on 18 March 2013 - 08:56 PM, said:

There is a function to find permutations.

next_permutation

Yea I cant use that...

[Adak]

You have the word "rumors", and need all the possible words that can be made from r u m o r s.

Simple! />/>

Sort the letters in order (say ascending, but it doesn't matter):
morrsu

Now do the same for your six letter words, and any that match, are your answer.

Insertion sort is the fastest small item sorter on the planet - an excellent snippet of code for it, is linked to on the right hand side of this page in the C++ snippets area.

If you want to find the matching words real fast, make a pre-sorted second dictionary of words that like morrsu, are already sorted - then use a binary search - amazing speed.

Just matched up 91,300+ words with a dictionary using a binary search - every word was found.

Elapsed time: 0.016 seconds!!

Just using one process, on one core.

You do NOT need to make up all permutations of a word!! You do NOT need to make up ANY permutations of words, except this one sorted instance.

This post has been edited by Adak: 19 March 2013 - 12:17 AM

[baavgai]

splicecube, on 18 March 2013 - 08:28 PM, said:

I have tried blanking out a character after it is checked so it is not checked for again but the program just crashes,

Sounds like a reasonable solution. Rather than blanking out the chars in the string, make a second array that you can mark found without messing with the first.

One of the big problems with your code is that you have six on the brain. Everything is focused on that fixed size. What if the size in seven, or four? How much of your program would you have to rewrite?

There's a lot of magic numbers in there. 7660? Is that the number of words in the file or the number of words you expect? You actually count the number of words read, in the very descriptive variable n, but you then ignore it. Why 45 for word size? Why aren't you using std::string and std::vector?

[Adak]

Doesn't sound like a reasonable solution to me!

Splicecube, how many words are in your list of words?

Once, I had to make this search for a word jumble REALLY fast, so here's what I did.

*I wrote a little program to separate words out of the main word list, into their own smaller files, according to their length: 1words.txt, 2words.tx, 3words.txt, etc.

This is 2words.txt:

Quote

be
by
do
eh
go
ha
he
hi
ho
id
if
in
is
it
me
my
no
of
oh
ok
on
or
ow
ox
pi
re
so
to
um
up
us
we

Then I wrote the function to alphabetize each word, and write it out to another file: 2wordsSrt.txt, 3wordsSrt.txt, etc.

Now, when I received a word to look for all the jumbles, I used strlen() to get it's length (say 6), opened the 6wordsSrt.txt file, and found all the matches. There is a binary search change you can make so it always finds the first match - which makes it simple to read all the rest of the matches, using a while() loop.

Report the results, and close the file, and you're done.

This eliminates a lot of the time you'd spend 1) looking for all the 6 letter words in a large word list, and 2) sorting them to see if they matched that of the goal word.

It may not seem all that fast, but it is, because you're almost done with the race, before it starts.

[Skydiver]

LOL! Adak's version of rainbow tables! /> Sacrificing space, and precompute time for speed of lookup time later.

The only downside is that if ever the starting dictionary is ever swapped out, then the "rainbow tables" need to be recomputed to match the new dictionary because it will either return words that are not in the dictionary, or fail to find new words that were added to the swapped in dictionary.

This post has been edited by Skydiver: 19 March 2013 - 03:29 PM

[Adak]

Yeah, I guess so!

If you use Insertion sort, you'd be surprised how quickly the entire word list (mine is about 93,300 words), can be processed this way. I haven't timed it, but it's just a few seconds.

[splicecube]

Adak, on 19 March 2013 - 02:38 PM, said:

Doesn't sound like a reasonable solution to me!

Splicecube, how many words are in your list of words?

I have 7660 words in my list, and thank you so much for you help! But you see when I submit this program the only txt file the instructor can access is the dictionary he provided. And about your other post it works really well but only with 6 letter combinations. Like for example if I have the word "rodent" I would rearrange it to "denort" (alphabetically). Then lets say the word "rod" was found out of the combinations of r,o,d,e,n,t. rod would be rearranged to "dor" just be compared to the first three letters of "denort". And since "dor" and "den" arent the same, the program ignore a bunch of the valid words. By the way I have to find 3,4,5, & 6 letter combinations which I account for in my nest for-loops

[Adak]

What I suggested won't work for what you want, clearly. Hmmmm....

I have an idea, but I'll have to play with it a bit and see if it's good -(in C - I don't program in C++).

Not due tonight I hope?

[Skydiver]

Adak: I have a question about post #6. You said:

Quote

Then I wrote the function to alphabetize each word, and write it out to another file: 2wordsSrt.txt, 3wordsSrt.txt, etc.

Does that mean that it in 2words.txt you have "no" and "on", that 2wordsSrt.txt will only end up with "no" after you "alphabetize" each word? Or will the file end up with two entries of "no" in it? And irregardless of whether you have one or two entries in 2wordsSrt.txt, how to you reconstitute that both "on" and "no" are legal words?

Anyway, it's more of tangential question since the OP can't use your solution anyway unless he builds the sorted word list in memory at runtime each time.

[Adak]

It wouldn't work for the OP, who's looking for all the subsets being permuted and checked, as well.

The words in the array used a struct member with the index of the word, and yes, there would need to be two no's in it - but they'd have different index numbers in their struct members.

Not to hijack a thread, but now that I'm infected from D.I.C, how do I get this javascript bad actor, off my PC? It's annoying, at best.

[Skydiver]

Since the OP is using C++, and unless the teacher specifically said they needed to implement their own permutation generator, why not just use std::next_permutation() to generate all the permutations?

http://www.cplusplus...xt_permutation/

Of course, the OP will have to generate the subsets himself before using the built in permutation generator.

This post has been edited by Skydiver: 19 March 2013 - 09:19 PM