Nested Loops

[BananaBoy]

I am relatively new to C++ (although I've done a fair amount of programming in Visual Basic). I have always found that one of the best ways of learning a subject such as C++ is (having mastered the rudiments) to set yourself a simple project to undertake and learn the various techniques as you progress. Hence, I am trying to write a programme to assist in solving crosswords.
The essence of the programme is for the user to enter the known letters of the word and to insert a '?' (Wild Card) for the letters not known. Then for the first WC characters from a to z are substituted and the output (which will consist of 26 combinations) is stored in an array. Each of the 26 variations is subjected to a similar process whereby the second '? is replaced with a to z; this will output 676 combinations (26 X 26), also stored in an array. This process continues until all the WC's marks have been replaced and the outputs stored, following which the final output is compared, word by word, with with a text file (dictionary) which I have compiled, and any matches are displayed.
Replacing the first WC is simple as it merely involves executing a for loop; the problem is achieving the second and subsequent WC's. As far as I can see, what it involves is constructing a nested loop where the inner loop executes 26 iterations for every one iteration of the outer, which I am sure is possible but I don't know how to do it.
I reproduce a section of the code to try to show what I'm trying to achieve.

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
string word;
string ArrFirst[26]; /// Array for replacement of first WC
string ArrSecond[676]; /// Array for replacement of second WC
string ArrThird[17576]; /// Array for replacement of third WC

char x,y,z; /// Letters to be substituted

int a,b,c; /// Positions of WC's
a=1;
b=3;
c=5;

word="r?d?a?t";

x='a';
for (int i=0; i<26; i++) /// This loop replaces the first WC
{
word[a]=x; /// Replaces the WC with 'a' to 'z'
ArrFirst[i]=word;
x++;
}

y='a';
word=ArrFirst[0]; /// The 1st element of the array – ie 'rad?a?t'
for (int j=0; j<26; j++) Loop to replace the 2nd WC with 'a' to 'z'
{
word[b]=y;
ArrSecond[j]=word; /// Will store 'radaa?t' to 'radza?t'
y++;
}

I hope this makes sense to somebody.

Thanks guys. Your response has been gratifying and has given me a lot to digest. It has also shown me that there's more than one way to skin a cat !!

[JLBorges]

> As far as I can see, what it involves is constructing a nested loop where the inner loop executes
> 26 iterations for every one iteration of the outer, which I am sure is possible but I don't know how to do it.

The depth of nesting of these loops is not known at compile-time; a recursive approach
(where each recursive call implements the next nested loop) would perhaps be the simplest.

Using the same brute-force algorithm which was outlined
(more than five wild card characters would take a lot of time and space; 26^6 == about 309 million):

#include <set>
#include <string>

// return true if candidate is in the dictionary, false otherwise
bool look_up( const std::set<std::string>& dictionary, const std::string& candidate )
{ return dictionary.find(candidate) != dictionary.end() ; }

// return word if there is a match for wild_card, an empty string otherwise
std::string locate_word( const std::set<std::string>& dictionary, std::string wild_card )
{
    static constexpr char wc = '?' ; // wild-card character

    const auto pos = wild_card.find(wc) ; // look for the first wild card character

    // if there are no more wild card characters, look up the candidate word in he dictionary
    // return the candidate word if found, otherwise return an empty string
    if( pos == std::string::npos ) return look_up( dictionary, wild_card ) ? wild_card : "" ;

    else // there is at least one wild card character
    {
        static const std::string alphabet = "abcdefghijklmnopqrstuvwxyz" ;

        for( char c : alphabet ) // for each character in the alphabet
        {
            auto candidate = wild_card ;
            candidate[pos] = c ; // replace the wild card character by a character in the alphabet

            // continue the process recursively: try for a match with the candidate
            const std::string word = locate_word( dictionary, candidate ) ;
            if( !word.empty() ) return word ; // found the word
        }
    }

    return {} ; // no word matches the wild_card, return an empty string
}

http://coliru.stacked-crooked.com/a/47161b3a2c70ce2a

[48T7M4Gy]

I am trying to write a programme to assist in solving crosswords.

Presumably you use one of the many well known wordlists eg
https://github.com/dwyl/english-words or 12dicts which you can 'massage' as a refinement if you want, to include the length of the word and eliminate impossible words (eg hyphenated words, other punctuation and length < 2)

Once that's done the search algorithm can search initially on the length of the word. Then each word of that length is searched on the basis of having a corresponding matching character at the specific location. Wild cards are ignored except to determine known character positions. There is no point 'creating' words from all the combinations in the alphabet by filling in the wild card if the wordlist is reasonably comprehensive.

Also, unless there is some reason for storing the results there is no use for arrays as the results will simply spit out on the screen as they are found.

(Maybe regex is possible??)

[BananaBoy]

Thanks very much for the comments. I'll study them and try to apply ( family here from overseas at present dictates that not too much time spent at the PC). Incidentally, I'd never intended to go as far as 6 Wild Cards; 3 would be good, 4 a luxury !!
On the subject of the dictionary, I've created my own. The length of the word is assessed, then the appropriate file is opened (otherwise, the files become too large and unwieldy).

[48T7M4Gy]

the files become too large and unwieldy

Not really, a common and freely available 22,000 word list is about 1.2 MB. Of course it depends on your processor but a search shouldn't take longer than a few seconds to come up with a set of possibles. The point being, I wouldn't limit myself too much. :)

[48T7M4Gy]

'.' is the standard regex notation, instead of '?'.

#include <iostream>
#include <fstream>
#include <string>
#include <regex>

int main ()
{
    std::string search_word = "...r...m....."; // Note: '.' denotes missing single letter
    size_t length = search_word.length();
    
    std::string file_word = " ";
    
    int count = 0;
    
    std::ifstream word_file ("crossword.txt");
    if ( word_file.is_open() )
    {
        while ( word_file >> file_word )
        {
            if ( std::regex_match ( file_word, std::regex(search_word)) && length == file_word.length())
            {
                std::cout << count << '\t' << file_word << '\n';
                count++;
            }
        }
        
        word_file.close();
    }
    
    else std::cout << "Unable to open file";
    
    return 0;
}

Results:

0	approximately
1	approximating
2	approximation
3	embroilment's
4	engrossment's
5	improvement's
6	microcomputer
7	nourishment's
8	overstimulate
9	quartermaster
10	recruitment's
11	refreshment's
12	shortcoming's
Program ended with exit code: 0

Typical extract from wordlist

tyrants
tyro
tyro's
tyros
u
ubiquitous
ubiquitously
ubiquity
ubiquity's
udder
udder's
udders
ufologist
ufologist's
ufologists
ufology
ufology's
ugh
uglier
ugliest
ugliness

https://msdn.microsoft.com/en-us/library/bb982727.aspx

[JLBorges]

If performance is a design goal, represent the dictionary as a suffix tree. https://en.wikipedia.org/wiki/Suffix_tree

[48T7M4Gy]

#include <iostream>
#include <fstream>
#include <string>
#include <cctype>

int main ()
{
    std::string search_word = "";
    std::string file_word = "";
    int count = 0;
    bool found = true;
    
    // Note: '.' denotes missing single letter
    std::cout << "Please enter a word to search for: ";
    std::cin >> search_word;
    
    std::ifstream word_list ("crossword.txt");
    if ( word_list.is_open() )
    {
        while ( word_list >> file_word )
        {
            found = true;
            
            if(file_word.length() == search_word.length() && file_word.find('\'') == std::string::npos)
            {
                for(size_t i = 0; i < search_word.length() && found == true; i++)
                {
                    if(search_word[i] != '.' && tolower(search_word[i]) != tolower(file_word[i]))
                        found = false;
                }
                
                if (found == true)
                {
                    std::cout << count << '\t' << file_word << '\n';
                    count++;
                }
            }
        }
        
        std::cout << "Number of matches found: " << count << '\n';
        word_list.close();
    }
    else std::cout << "Unable to open file";
    
    return 0;
}

Please enter a word to search for: ...ig..t...
0	ambiguities
1	assignation
2	astigmatism
3	cosignatory
4	denigrating
5	denigration
6	designating
7	designation
8	immigrating
9	immigration
10	indigestion
11	indignation
12	indignities
13	remigrating
14	resignation
Number of matches found: 15
Program ended with exit code: 0