print all possible 5 letter words using recursion-CodePudding

I pass in a string, "--pl-" into the function, wordle. I would like the function to return a set of strings with all possible 5 letter words with 'p' as 3rd letter and 'l' as 4th letter. This would mean that the set would return 26^3 different strings.

I am trying to use recursion to do this but am not sure how to.



#include <iostream>

#include <algorithm> 
#include <map>
#include <set>
// #include "wordle.h"
// #include "dict-eng.h"
using namespace std;

// MOST UP TO DATE


// Add prototypes of helper functions here


// Definition of primary wordle function
set<string> wordle(string& in, string& floating, set<string>& dict){
    set<string> possibleList;
    int length = in.length();
    

    // iterate over each letter
    
    for(int i = 0; i<length;i  ){

        // only if -
        
        if (in[i] == '-'){
            
            for(int j = 97; j<=122; j  ){
                in[i]=char(j);
                possibleList.insert(in);
            }
            set<string>::iterator itr;
            for (itr = possibleList.begin(); itr != possibleList.end(); itr  )
            { 
                auto S = *itr;  //copy of *iter
                wordle(S, floating, dict);  //use S
            }
        }
    }
    // if we reach here, that means that we now have all possibilities in the set
    
    return possibleList;
} // end of function
    
    
int main(){
    
    string in = "--pl-";
    string floating = "ae";
    set<string> dict;
    // set with 6 strings, should only return 2 of these
    dict.insert("joshua"); // same
    dict.insert("phone"); //diff
    dict.insert("apple"); //same
    dict.insert("aepll"); //same
    dict.insert("eapll"); //same
    dict.insert("ae"); // diff
    
    set<string> finalSet = wordle(in, floating, dict);
    cout << "got here" << endl;
    set<string>::iterator itr;
    for (itr = finalSet.begin(); itr != finalSet.end(); itr  )
    { 
        cout << *itr << endl;
    }
    
    
    return 0;
    
    // how this works:
    // take all possible strings of the form of size n
    // then remove all requirements not met 
    
}

What is happening is that it prints the following:

got here a-pl- b-pl- c-pl- d-pl- e-pl- f-pl- g-pl- h-pl- i-pl- j-pl- k-pl- l-pl- m-pl- n-pl- o-pl- p-pl- q-pl- r-pl- s-pl- t-pl- u-pl- v-pl- w-pl- x-pl- y-pl- z-pl- zapl- zbpl- zcpl- zdpl- zepl- zfpl- zgpl- zhpl- zipl- zjpl- zkpl- zlpl- zmpl- znpl- zopl- zppl- zqpl- zrpl- zspl- ztpl- zupl- zvpl- zwpl- zxpl- zypl- zzpl- zzpla zzplb zzplc zzpld zzple zzplf zzplg zzplh zzpli zzplj zzplk zzpll zzplm zzpln zzplo zzplp zzplq zzplr zzpls zzplt zzplu zzplv zzplw zzplx zzply zzplz

CodePudding user response：

I ignored the floating and dict parameters. Here is an iterative (non-recursive) solution that you can start from:

#include <vector>
#include <string>

std::vector<std::string> combine(
  const std::vector<std::string>& acc, const std::string& next) {
  std::vector<std::string> result;
  for (const auto& x: acc) {
    for (auto y: next) {
      result.push_back(x   y);
    }
  }
  return result;
}

std::string symbols = "abcdefghijklmnopqrstuvwxyz";

std::vector<std::string> wordle(const std::string& in) {
  std::vector<std::string> result{""};
  for (auto c: in) {
    result = combine(
      result,
      c == '-'? symbols : std::string(1, c));
  }
  return result;
}

The you call it with your pattern, e.g. wordle("---pl-").

CodePudding user response：

The problem in your code is that you do not use the results of the nested recursive call in wordle. In other words, when you fill the possibleList at "level 0", you then have nested calls of wordle, but it is useless currently, cause eveything it does - it does just inside it. That's why you get the result you described.

In particular, this happens:

At level 0 you fill the list with variations like "a--pl-", "b--pl-", ..., "zzzplz" etc, and collect them in possibleList. And no matter that you have recursive calls, your possibleList is still the same at level 0, and it is returned later - that's what you get as the result.

Also, you need to change the way you iterate through different variants. In general words, it could be such (sorry for not giving exact code in C - haven't used if for ages):

You first search for the first occurance of _ in your string, remembering it's position.
Then you iterate through all possible chars, and substitute this _ with a new char, making a copy of the string.
With each new character, you then make a nested call with that new string. You could also pass the current position, so it will know where to start exactly, but that's more an optimisation.
The nested call will return you a set of combinations. Which you need to merge with a set at your current level.
You then return your accumulated set.

Note that you don't need to iterate through all _ in a string explicitly in your method, because it will be done recursively: each new level finds it's own first _ in the string.

UPD: Pseudo-code

FUNCTION wordleRecursive(str, start=0):
  possibleList = []
  foundPlaceHolder = False
  
  FOR (i=start; i<str.length; i  ):
    IF str[i] == '_':
      foundPlaceHolder = True
      FOR (j=97; j<122; j  ):
        newStr = copy(str)
        newStr[i] = char(j)
        nestedList = wordleRecursive(newStr, i   1)
        possibleList = merge(possibleList, nestedList)
      
      // We need to find only first occurance
      BREAK 

  // This is needed if the substring does not contain "_" anymore
  // in this case we need to return the list with a single item,
  // Containing the str itself.
  IF NOT foundPlaceHolder:
    possibleList = [str]

  RETURN possibleList