Unscrambler - DIFFICULT!

[itayz]

Hello ! I know this isn't the most clear post but I would really appericiate your help on this;

So, I'm trying to create an unscrambler in the most simple way possible - doesn't have to be short as long as it has simple commands.

So here are my questions ;
how can I create a 'database' of words without seperately declaring them (int word1, word2...etc)?

For example;
cin >> WordToUnscramble
Lets say the word I want to unscramble is 'rraecel'(This word is 'clearer', or 'reclear' when unscrambled)

The program proceeds to seperate the letters from 'rraecel' into R R A E C E L and saves their value, and searches the database I talked about earlier, and searches for words with the same values.

Lets say both words "clearer" and "reclear" are in the database I created, the program see's that they both contain the values of R R A E C E L - and PRINTS both of them.

so the final product would look like :
cout<< "Insert word \n";
cin << WordToUnscramble; // player inserts the word rraecel
{
program
}

cout << "Possible solutions are << X << endl;
cout << Y ;
// X is going to print out clearer, Y is going to print out reclear


ANY help appericiated!

[tntxtnt]

one way to do it is for each permutation p of WordToUnscramble, check if p is in dictionary. dictionary is just a std::set<std::string>.

another faster way is use std::map<std::string, std::vector<std::string>> as dictionary. When loading dictionary, sort each word alphabetically, ex. "clear" would become "acelr", then insert it into your dictionary, use the alphabetical word as key and insert the list of words as value. When looking WordToUnscramble, sort it alphabetically, then just return dictionary[alphabeticallyWordToUnscramble];. (you may want to check if it exists in dictionary before returning it)

[Stewbond]

Here's what I'd do:
1. Download a database.

At this FTP: ftp://ftp.cerias.purdue.edu/pub/dict/dictionaries/ you have words.english.z which is just a text file which contains 26880 English words.

2. Open the file
std::ifstream fin("words.english");

3. Read the file:

std::vector<std::string> m_dictionary;
std::string line;
while (std::getline(fin, line) )
  m_dictionary.push_back( line );

4. Ask the user for a set of letters:

std::cout << "Enter some letters:";
std::string letters;
std::getline( std::cin, letters );

5. Sort the letters before searching:
std::sort( letters.begin(), letters.end() );

6. check if the word is in the database. if true, print. then shuffle the letters for the next permutation:

do
{
  for (std::vector<std::string>::iterator it = m_dictionary.begin(); 
                                      it != m_dictionary.end(); ++it)
    if (*it == letters)
      std::cout << letters << std::endl;
} while ( std::next_permutation( letters.begin(), letters.end() ) );

Note that there are MUCH faster ways to search for a word, but I iterate through the entire database on every permutation for simplicity here.

[Smac89]

The permutations idea made me remember a similar answer I gave yesterday. Read this link:

http://stackoverflow.com/a/10745675/2089675

So if you simply hash the unscrambled string, you can easily find it in a database by either straight linear search where you try to find a string that matches the hashed value of the unscrambled string (this will be O(N)). Or you can already have the strings in your database already be in a hashmap then lookup is reduced to O(1).

Good luck

[itayz]

THANKS for the comments ,

Can you guys help me start simply with a program that simply counts the amount of letters in a word?

ie I type in 'recal'
it'll count 5 letters?
also, if it can count how many of each letters there are
ie I type in recaler - it has 2 Rs, 2 Es, and 1 of C, A and L, how do I get my program to get that information?

[Stewbond]

Count letters in a word

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include <iostream> #include <string> int main() { int freq[26] = { 0 }; std::string word; std::cout << "enter some letters: "; std::cin >> word; std::cout << word << " has " << word.size() << " letters\n"; for (int i = 0; i < word.size(); i++) freq[ toupper(word[i]) - 'A' ]++; for (int i = 0; i < 26; i++) if (freq[i] != 0) std::cout << char(i+'A') << ": " << freq[i] << std::endl; }

animal animal has 6 letters A: 2 I: 1 L: 1 M: 1 N: 1