Need help with comparison algorithm

[veronicak5678]

I need to write program that inputs a scrambled word and compares it against a pre-determined list of words. I am first checking for length, then if a match is found, sending them to a function to compare the letters. I can't seem to get the loops right. Here is what I have so far:

Code:
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

bool check(string, string);

int main()
{

    string scrambled;
    string PossibleWord [13]={"will", "check", "it", "against", "list", "and", "return", "hello", "True", "or", "False", "Swap"};
    cout << "Please enter scrambled word: ";
    cin >> scrambled;
    for (int i=0; i<13; i++)
    {
        if (scrambled.size()==PossibleWord[i].size())
        {
           if (check(PossibleWord[i], scrambled))
       	   {
                cout<< "the word is " <<  PossibleWord[i]<<endl;
                break;
           }
        }
        else
           cout<< "the word is not found"<<endl;
    }   
    system ("pause");
}

bool check(string p, string s)
{
        bool match;
        int count=0;
        int psize= p.size(), ssize= s.size();
        for (int i=0; i< psize; i++)
        {
            for (int d=0; d< ssize; d++)
            {
                if (p[i]==s[d])
                {
                    cout << "Match with possible's "<< p[i] << " and scrambled's " << s[d]<< endl; 
                     count++;
                }
             
            }
              
        }
        cout << "Count is "<< count <<endl;
        if (count==psize)
        {
               match=true;
               return match;
        }
        else
                match=false;
                return match;
}

I would love any suggestions on how to make this work!

[treuss]

Hi there,

it looks to me, like you haven't really figured out the algorithm how to check, if a scrambled word matches the original. I assume finding that algorithm is part of the excercise, so I advise you to take some pen and paper, write down "hello" and "olelh" or "codeguru" and "odugerco" and systematically find out if one is a scramble of the other. Once you've done that, write down the algorithm in words, post it here or implement it yourself.

[potatoCode]

Hi there,

it looks to me, like you haven't really figured out the algorithm how to check, if a scrambled word matches the original. I assume finding that algorithm is part of the excercise, so I advise you to take some pen and paper, write down "hello" and "olelh" or "codeguru" and "odugerco" and systematically find out if one is a scramble of the other. Once you've done that, write down the algorithm in words, post it here or implement it yourself.

I was going to try out this exercise and post the code because it sounded like a good one for a newbie like me,
but then I decided not to because the advice given here is brilliant and perhaps the best "help" that I have seen given to people like us.

[Paul McKenzie]

I was going to try out this exercise and post the code because it sounded like a good one for a newbie like me,

Also, do not post answers to questions that are obviously homework questions.

Regards,

Paul McKenzie

[GNiewerth]

I can actually think of two solutions (well, three, but the third one isn´t serious):

#1
Count all letters of both the scrambled and the possible descrambled word. If both consists of the same amount of letters you have found the solution.

#2
Check if the scrambled and possible descrambled word have the same length. If they have, make a copy of the descrambled word and iterate over all letters of the scrambled word. Remove the current letter from the descrambled copy until all letters are processed. If the copy is empty at the end you found the descrambled word.

#3 (don´t take this serious)
generate all permutations of the input and compare each permutation to the possible descrambled word. Return the word that matches an permuation.

[treuss]

#4 Descramble the scrambled word. If it works return true, else return false.

[GNiewerth]

#5
Use a hash function that creates an unique hash depending on the input letters (independent of their position). Calculate the hash for both the scrambled and descrambled word and compare both hashes.

#6
Sort both the scrambled and descrambled word´s letters and compare the sorted words.

[veronicak5678]

Thanks to everyone who answered. here is what i have so far:

#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;

bool check(string, string);

int main()
{
    bool match;
    string scrambled;
    string PossibleWord [13][13]={"will", "check", "it", "against", "list", "and", "return", "hello", "True", "or", "False", "Swap"};
    cout << "Please enter scrambled word: ";
    cin >> scrambled;
          for (int i=0;i<13;i++)
          {
              if (scrambled.size()==PossibleWord[i][0].size())
              {
                   match=(check(PossibleWord[i][0], scrambled));
       	           if (match)
                   {
                      cout << "Match!\n";
                      break;
                   }
              }
          }
          system ("pause");
          
}

bool check(string p, string s)
{
     bool matched;
     int count=0;
     int ssize= s.size();
     char temp[ssize];
     temp[ssize]='\0';
     for (int r=0;r<ssize;r++)
     {
         temp[r]=s[r];
     }
     for (int i=0; i<ssize; i++)
     {
            for (int d=0; d< ssize; d++)
            {
                if (temp[i]==p[d])
                {
                   << temp[i]<< endl;
                   temp[i]='\0';
                   ++count;
                }
            }        
            cout <<" count = "<< count << endl;
     }
     if (count==ssize)
     {      
               cout<< "the word is " <<  p <<endl; 
               matched=true;

     }
     else
               cout<< "The word is not found.\n"<<endl;
               matched=false;
               return matched;
}

I am trying to compare each letter and count the number of times they match. if the number of matches equals the word length, I assume the word is matched. There are still some problems with the loops. The program crashes now and i can't see why.

[GCDEF]

int ssize= s.size();
char temp[ssize];
temp[ssize]='\0';


Several problems there.

[GNiewerth]

I am trying to compare each letter and count the number of times they match. if the number of matches equals the word length, I assume the word is matched. There are still some problems with the loops. The program crashes now and i can't see why.

The program does not even compile, so how can it crash?

[veronicak5678]

I think I have this part figured out now. i thought this would be the easy part! Here's what i got:

#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
bool check(string, string);
int main()
{
    bool match;
    string scrambled;
    string PossibleWord[12]={"will", "check", "it", "against", "list", "and", "return", "hello", "True", "or", "False", "Swap"};
    cout << "Please enter scrambled word: ";
    cin >> scrambled;
          for (int i=0;i<13;i++)
          {
              if (scrambled.size()==PossibleWord[i].size())
              {
                   match=(check(PossibleWord[i], scrambled));
              }
              if (match)
              {      
               cout<< "Match!\nThe word is " << PossibleWord[i] << ".\n"; 
               break;
              }
          }
          system ("pause");
}

bool check(string p, string s)
{
     bool match;
     int count=0;
     int ssize= s.size();
     char temp[ssize];
     temp[ssize]='\0';
     for (int r=0;r<ssize;r++)
     {
         temp[r]=s[r];
     }
     for (int i=0; i<ssize; i++)
     {
            for (int d=0; d< ssize; d++)
            {
                if (temp[i]==p[d])
                {
                   temp[i]='\0';
                   count++;
                }
            }        
     }
     if (count==ssize)
     {      match = true;
              return match;

     }
     else
               match=false;
               return match;
}

Step 2 in my asignment is to modify this to use a class called "scramble" that looks like this:

class Scramble
{
private:
string PossibleWord[];
int size;
bool Check (string T,string S){} // Is this the word?
public:
Scramble (string List[], int Size); // constructor
string Descramble(string Scrambled); // the game player
};

I am also supposed to make a "driver"? Does that just refer to the main()?

[Lindley]

Yes, a driver is just a main() function in this context.

[exterminator]

OP's method is O(N^2).

#6
Sort both the scrambled and descrambled word´s letters and compare the sorted words.

This one is good and simpler. 1) Sorting would be of the order of O(NlogN) and 2) comparison would be O(N).

#5
Use a hash function that creates an unique hash depending on the input letters (independent of their position). Calculate the hash for both the scrambled and descrambled word and compare both hashes.

This one is even better. With maps, this one would be 1) order of insert into multimap O(logN) and 2) comparison of multimaps O(N).

With unordered_multimap (which is what you are suggesting - hash implementations, right?), 1) order of inserts O(1) (worst case O(N)) and 2) comparison O(N).

[treuss]

I think I have this part figured out now.

You think so? Your current code prints out that "abc" is a scramble of "will".

I can only repeat my advice: Write the algoritm in English first, then translate to C++.

[GCDEF]

You think so? Your current code prints out that "abc" is a scramble of "will".

I can only repeat my advice: Write the algoritm in English first, then translate to C++.

You're right. That check algorithm makes no kind of sense. He still has the problem with the temp buffer allocation and initialization too.