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.

[Paul McKenzie]

I think I have this part figured out now. i thought this would be the easy part! Here's what i got:You still need to resolve this, as this is not valid C++:

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

Arrays in C++ must have their sizes defined by a compile-time constant. That code will not compile on a true ANSI C++ compiler. If this is homework, you could get points taken off for utilizing non-standard code.

1) Turn on the ANSI switch for your compiler, so that it flags these as errors.

2) The workaround is to use std::vector<char>

3) Pass strings and other objects by reference or const reference, not by value. Rarely do you need to pass an object by value (functors not withstanding).

4) Even with your illegal code, you have a memory overwrite.

temp[ssize] = '\0'; //

There is no temp[ssize] as arrays are indexed from 0 to n-1.

Here is a rewrite of your code.

#include <vector>
bool check(const string& p, const string& s)
{
bool match;
int count=0;
int ssize= s.size();
std::vector<char> temp(ssize + 1);
//...
}

Everything else stays the same (in terms of compilability, not if you need to change something to get the correct results when you run your program).

Regards,

Paul McKenzie

[veronicak5678]

I have fixed more of the first program, and it is passable. I am more concerned with the second part, since I have never even heard of classes before and am having trouble understanding the concept as explained in my book. How am I supposed to convert my program to one that uses the outline as shown above?

[Paul McKenzie]

I have fixed more of the first program, and it is passable. I am more concerned with the second part, since I have never even heard of classes before and am having trouble understanding the concept as explained in my book. How am I supposed to convert my program to one that uses the outline as shown above?
First get rid of all of those declarations that use an empty []. Those are illegal in C++. If you want a way to declare the array size at runtime, and still have a maintainable program, use std::vector, not arrays.

Second, you need to explain to us what the class is supposed to do, i.e. what is PossibleWord supposed to denote, what is Check() supposed to do with those parameters being passed to it, what is the Scramble() function supposed to do, etc. This is the first step before writing any line of code, and that is to give us what the definition of those functions are (pretend you're writing documentation desribing those functions, parameters being passed to it, etc., not C++ code).

Regards,

Paul McKenzie

[veronicak5678]

I have fixed more of the first program, and it is passable. I am more concerned with the second part, since I have never even heard of classes before and am having trouble understanding the concept as explained in my book. How am I supposed to convert my program to one that uses the outline as shown above?

[potatoCode]

Hello Veronicak5678,

I tried this for myself and it was harder than I thought.
I think you are straying away from your goal...
and I know I wasn't going to post this (sorry Paul),
but I gues you put in lot of efforts and I think you deserve help.

so is this what you really had in mind? no?....
/*Scrambled?***************************************
heck!
*************************************************/

#include <iostream>
#include <string>
#include <map>

#define ON 'F'

using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::multimap;

int main()
{

typedef multimap<string, string>::iterator tdefMapIter;
typedef multimap<string, string>::value_type valType;

// create a storage for comparison
multimap<string, string> wordRoster;
multimap<string, string> scrambleRoster;
tdefMapIter wrIter;
tdefMapIter srIter;

// temporary test values
string tmp1 = "mississipi", tmp1Copy("ZZZZZZZZZZ");
string tmp2 = "imsispssii", tmp2Copy("ZZZZZZZZZZ");
wordRoster.insert(valType(tmp1, tmp1Copy));
scrambleRoster.insert(valType(tmp2, tmp2Copy));
wrIter = wordRoster.begin();
srIter = scrambleRoster.begin();
size_t debugCounter(0);

string::const_iterator strWRIter = wrIter->first.end(); // regular
string::const_iterator strSRIter = srIter->first.begin(); // scrambled


// are theyequal in length?
if(wrIter->first.size() == srIter->first.size())
{
cout << "Two words are equal in length" << endl;

while(strSRIter != srIter->first.end())
{
string::iterator strWRIterFlag = wrIter->second.begin();
/*cout << "Search character: " << *strSRIter << endl;*/

string::size_type pos(0);
while((pos = wrIter->first.find_first_of(*strSRIter, pos)) != string::npos)
{
//skip searched character
if(*(strWRIterFlag + pos) == ON)
{
#ifdef DEBUGFLAG
cout << "\tThe character flag "
<< "at " << pos << " is turned on for this character" << endl;
cout << "\tSearching next character in the string..." << endl;
#endif
++pos;
}

if(*(strWRIterFlag + pos) != ON)
{
strWRIterFlag = (strWRIterFlag + pos);
/*cout << "setting flag...................... at: " << pos << endl;*/
*strWRIterFlag = ON;
++debugCounter;
/*cout << "flag set as: " << *strWRIterFlag << endl;*/
break;
}
strWRIterFlag = wrIter->second.begin(); // reset location pos
}
// search next character
++strSRIter;
}

} // end length-check if
else
cout << "They are NOT equal in length" << endl;

#ifdef DEBUG
// logical answers
cout << "Checking flags..." << endl;
cout << "size of flag map string is: " << wrIter->second.size() << endl;
for(string::iterator strWRIterDisplay = wrIter->second.begin();
strWRIterDisplay != wrIter->second.end(); ++strWRIterDisplay)
{
cout << *strWRIterDisplay << endl;
}
if(wrIter->second.size() == debugCounter)
cout << "Logical check OK" << endl;
else
cout << "There is a logical flaw in this design" << endl;
#endif

// display result
if(wrIter->second.size() == debugCounter)
{
cout << "\n" << srIter->first << " is same as " << wrIter->first << endl;

} else {
cout << "\n" << srIter->first << " has same length, "
<< "but is NOT a scrambled word for " << wrIter->first << endl;
}


return 0;
}

what I did was I took treuss' advice, and it was fairly easy writing pseudo-codes, but doing it with C++ was really hard for me.
(that's why I said it was harder than I thought)

my approach to solution had these criterias:
1. Strings need to be searched individually
2. one string is an exact copy of the other but the order isn't,
which qualifies the same length requirement
3. Only single instance of match per character could happen,
4. Something must indicate the result of the match
(Checking vowels for faster matching was deemed unessessary)

and viola! it was hard but luckily it worked....this time ><

hope this helps

[Paul McKenzie]

Hello Veronicak5678,

I tried this for myself and it was harder than I thought.
I think you are straying away from your goal...
and I know I wasn't going to post this (sorry Paul),Why are you singling my name out here?

The reason why you shouldn't post homework answers is very simple. Please read the FAQ here if you haven't done so already:

http://www.codeguru.com/forum/showthread.php?t=366302

Second, the last thing that CodeGuru needs to be is a "do my homework" site, and the reputation of the board goes down.

Regards,

Paul McKenzie

[potatoCode]

Hey paul,

I read FAQ within a week from the day I joined this forum and I'm doing the best I can do abide by the rules. Just because you have a greater knowledge in coding does't mean you can always make the right decision for every occasion. You might be King solomon here, but not in other apsects of life.

I've read your posts for the past month,
and honestly, all I saw you doing was telling and making those in need of help feel how stupid we are for not knowing the things that so seem easy to you.
And to me, I don't think that's something anyone who's trully worried about the repuation of the forum should do.

remember paul?
I even took your advice and got rid of the old book, and got myself a new book the following day and I sincerely sent you a PM asking your opinions on the book I purchased, That's was about two? weeks ago and I still havn't heard a thing from you. It is your choice that shows your true character, not how much you think you know the right things to do.

you don't know if this a homework,
you don't know how hard he tried before posting,
even if this were a homework,
(and I think you need to read FAQ again to refresh your memory)
it didn't matter to me so I helped,
not because it was the right thing to do,
but it felt like a right thing to do.

don't take it too personal.
just my two cents.

thanks.

[exterminator]

Hey paul,

I read FAQ within a week from the day I joined this forum and I'm doing the best I can do abide by the rules. Just because you have a greater knowledge in coding does't mean you can always make the right decision for every occasion. You might be King solomon here, but not in other apsects of life.

I've read your posts for the past month,
and honestly, all I saw you doing was telling and making those in need of help feel how stupid we are for not knowing the things that so seem easy to you.
And to me, I don't think that's something anyone who's trully worried about the repuation of the forum should do.

remember paul?
I even took your advice and got rid of the old book, and got myself a new book the following day and I sincerely sent you a PM asking your opinions on the book I purchased, That's was about two? weeks ago and I still havn't heard a thing from you. It is your choice that shows your true character, not how much you think you know the right things to do.

you don't know if this a homework,
you don't know how hard he tried before posting,
even if this were a homework,
(and I think you need to read FAQ again to refresh your memory)
it didn't matter to me so I helped,
not because it was the right thing to do,
but it felt like a right thing to do.

don't take it too personal.
just my two cents.

thanks.You cannot imagine the number of people he has been a help to, including me. And as I see it, each of his post in this thread has been a helping one to the OP.

Probably, you started visiting codeguru after you joined and probably you don't visit other forums. Homeworks are a problem. And it is a common understanding among the frequent posters on these forums.

If you bought a book and asked Paul to provide feedback on PM. You should better have done that on the forum itself. Help on PMs is also discouraged as it doesn't help people who might benefit from it. It goes against the idea of public-ness of the forums. Moreover, it is an individual's discretion on what he wants to respond to and what not to. You cannot question that in any circumstances, not here, not anywhere (unless probably there's a legal binding, which isn't the case here).

Regarding your King Solomon comment, that is pathetic of you! How can you say something like that to anyone? Do you know his other aspects of life? And even if you did, what rights do you have to say something like that? You will have to learn some ettiquettes around in here and for other forums. You just don't go saying rubbish everywhere you like.

Now to the point of your response. I did not even look at what you have posted. And I am sure, neither Paul would have or may be not many would have. There might be things that are wrong in there and you are teaching the OP a wrong C++ concept. People discourage homeworks and don't even bother to look at such posts. What if there is a dire need to correct the wrongs in your code? You suffer as well as the OP suffers. Too much hand-holding doesn't let people grow/learn. Wait for the homeworks season (I don't know if it is here already) and you yourself will realize how bad it is. Try helping at specific points, not just throwing the complete solution. Let the OP do the work, since he is the one who is having problems, not you.. right?

[Paul McKenzie]

Hey paul,

I read FAQ within a week from the day I joined this forum and I'm doing the best I can do abide by the rules. Just because you have a greater knowledge in coding does't mean you can always make the right decision for every occasion. You might be King solomon here, but not in other apsects of life. And all I asked you to do is not post homework solutions. Is it that hard to follow the rules?
I've read your posts for the past month,
and honestly, all I saw you doing was telling and making those in need of help feel how stupid we are for not knowing the things that so seem easy to you. Show me these posts.
I even took your advice and got rid of the old book, and got myself a new book the following day and I sincerely sent you a PM asking your opinions on the book I purchased,I rarely look at PM, as the main board is where I focus my answers.
you don't know if this a homework,"Homework" is any work, even if it isn't from a teacher, that asks to solve a very contrived problem, so contrived that it wouldn't be a real-world problem.
even if this were a homework,
(and I think you need to read FAQ again to refresh your memory)What is in the FAQ that I need to refresh my memory of?

The person posting the code needs to solve it themselves. Providing complete solutions causes many problems, not only for CodeGuru, but also the person you're supposed to be helping.

1) That person doesn't learn anything, and instead takes what you give them and hands it in to the teacher or professor. When it comes time to explain the solution, they are at a loss for words. Who is to blame when they get a zero for the assignment, or worse, a failure in the course, and in some places, expulsion for plagiarism?

2) As the FAQ mentioned, teachers do web searches. When they find out that a site named "CodeGuru" is giving out homework answers, who is likely to get reprimanded on this site? Is it you, or is it the site owner? If this were a "warez" type site, then that is one thing. However CodeGuru has become one of the top programming help sites on the Internet, geared towards professional (and good amateur) programmers.

3) You can't find one reputable programming board, either on the Internet or on UseNet, that encourages posting homework answers. Try this:

http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.3

Here is where your post was inappropriate.

Even though the person posted an attempt, you didn't add to their code or change it. What you did was radically made the solution different. Of course, you have to use your own discretion when posting code, but you didn't just suggest using maps, you posted an entire solution using them.

Now, if the original problem were a well-known programming issue that affects all programmers (how do you read data in from a file and store in a container, how do you output data from an array, etc.), and the person posted an attempt, then it can be subjective how much you can post to help them. However, the original problem was a niche homework problem, and it just isn't appropriate or ethical to give entire solutions to these type of questions.

Regards,

Paul McKenzie

[GCDEF]

Hey paul,

I read FAQ within a week from the day I joined this forum and I'm doing the best I can do abide by the rules. Just because you have a greater knowledge in coding does't mean you can always make the right decision for every occasion. You might be King solomon here, but not in other apsects of life.

I've read your posts for the past month,
and honestly, all I saw you doing was telling and making those in need of help feel how stupid we are for not knowing the things that so seem easy to you.
And to me, I don't think that's something anyone who's trully worried about the repuation of the forum should do.

remember paul?
I even took your advice and got rid of the old book, and got myself a new book the following day and I sincerely sent you a PM asking your opinions on the book I purchased, That's was about two? weeks ago and I still havn't heard a thing from you. It is your choice that shows your true character, not how much you think you know the right things to do.

you don't know if this a homework,
you don't know how hard he tried before posting,
even if this were a homework,
(and I think you need to read FAQ again to refresh your memory)
it didn't matter to me so I helped,
not because it was the right thing to do,
but it felt like a right thing to do.

don't take it too personal.
just my two cents.

thanks.

Paul is a regular contributor here and a tremendous asset to the board.

Anybody that's been doing this for a while can tell homework from a real world application.

We don't do homework here, we guide people to finding the solutions on their own.

[angelorohit]

Hi veronicak5678,
The answer to your problem was right in front of you all along. Look at the code you posted in Post#1. The check() routine was:

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++;
}

}

}
................................

Basically, you are iterating over each letter in the possible word (in the outer loop) and checking whether that letter matches any letter in the scrambled word(in the inner loop). Now, what you need to do is eliminate the matching letter from the scrambled word. Set it to a space or some other character that would never occur in any of the words. Once, a match has been found then break out of the inner loop, since that letter in the possible word does not have to be (and should not be) matched again. This is what your code should look like.

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])
{
s[d] = ' ';
count++;
break;
}

}

}
Note that this isn't the most efficient way to solve the problem but it fits the bill and get's the job done. Hope this helps.

EDIT: Some early optimizations (exercise for you):-
1. Check whether the lengths of the scrambled and possible words are the same, before even entering the loop.
2. If a letter in the possible word goes unmatched throughout the scrambled word, then there is no reason to continue looping. Return false immediately in such a case. ie; if p[i] goes unmatched after completely going through the inner d loop, return false.

[exterminator]

OP's method is O(N^2).
This one is good and simpler. 1) Sorting would be of the order of O(NlogN) and 2) comparison would be O(N).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).Sorry, for insert into multimap, the order would be O(NlogN).

[potatoCode]

I'll be more careful next time.
sorry if my post made any of you upset.

let's move on!