"Rate"programm

g3bk47

Hallo,
ich habe vor ein Programm zu schreiben, dass ein Wort, das ein Benutzer eingibt, "errät".

Das Programm startet damit, dass ein ein Wort eingegeben wird:

string wort;
cin>>wort;

Dann soll das Programm strings erstellen und diese mit dem Wort vergleichen

string zeichenpool = "abcdefghijklmnopqrstuvwxyz";
int zeichenpoollaenge = zeichenpool.size();
int a,stelle=0,end=0;

string aktuelleswort=" ";

while(end!=1)
{
    for(a=0;a<zeichenpoollaenge;a++)
    {
        aktuelleswort[stelle]=zeichenpool[a];

        if(aktuelleswort == wort)
        {
            cout<<"Das gesuchte Wort ist "<<aktuelleswort;
            break;
            end=1;
        }
    }
aktuelleswort=aktuelleswort+" "; //string um eine stelle erweitern
stelle++;
aktuelleswort[stelle-1]=zeichenpool[0]; //vorletzte Stelle zurücksetzen
}

Mit diesem Code wird allerdings immer nur die letzte Stelle des Strings geändert.
Wäre der Zeichenpool "abc", wäre das Ergebnis also

a
b
c
aa
ab
ac
aaa
aab
aac
aaaa
usw.

Mein Ziel ist es, dass er folgende strings erstellt:

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
usw.

D.h. wenn er mit der letzten Stelle fertig ist (bis z), müsste er ja die Vorletzte um eins erhöhen (von a auf b) und dann wieder die letzte Stelle ändern (von a bis z).
Wenn die vorletzte Stelle dann bis z geändert ist, müsste er die Vorvorletzte um eins erhöhen (von a auf b), die Vorletzte auf a zurücksetzen und die letzte Stelle wieder ändern.
Allerdings weis ich nicht, wie ich dieses Verfahren in Code umsetzten soll.
Ich könnte natürlich noch 19 weitere for-Schleifen um den Haupt-Codeteil machen, um dann halt 20 Stellen zu ändern. Aber das Programm soll mit (theoretisch) unendlich vielen Stellen arbeiten können.
Hat jemand einen Tipp für mich, wie ich dieses Problem elegant lösen kann? Ich hoffe ihr versteht meine Frage

drakon

Spiel mal ein bisschen mit der Länge des Strings und der aktuellen Position rum.
So kannst du auch relativ leicht die Position Links, respektive Rechts verändern.

Phoemuex

Ich würde es so ungefähr machen. Die Implementierung ist zwar nicht ganz elegant, aber es funktioniert.

Das Problem mit den 20 verschachtelten Schleifen wird hier durch Rekursion (eine Funktion, die sich selbst aufruft heißt rekursiv) gelöst.

EDIT: Oh, du wolltest nur einen Tipp, dann lies lieber nicht weiter...

#include <iostream>
#include <string>

using namespace std;

//Diese Funktion führt die Erhöhung durch und verändert dabei auch die
//vorherigen Buchstaben, wenn nötig.
//Der Rückgabewert gibt an, ob der komplette String durchlaufen wurde, also
//ob die Länge erhöht werden muss
bool Increase(string &text, size_t stelle, string const &zeichenpool)
{
   //Wenn auf der Stelle, die man erhöhen will ein durchlauf fertig ist
   if(text[stelle] == zeichenpool[zeichenpool.size() - 1])
   {
      //Ersten Buchstaben an die Stelle schreiben
      text[stelle] = zeichenpool[0];
      //Wenn es noch einen Buchstaben vor unserer Stelle gibt
      if(stelle > 0)
      {
          //diesen erhöhen
          return Increase(text, stelle - 1, zeichenpool);
      }
      else
      {
          return false;
      }
   }
   //Zeichen um eins erhöhen, indem man das momentane Zeichen findet und dann
   //das nächste wählt
   size_t position = zeichenpool.find_first_of(text[stelle]);
   text[stelle] = zeichenpool[position+1];
   return true;
}

int main()
{
   string wort;
   cin >> wort;
   string zeichenpool = "abcdefghijklmnopqrstuvwxyz";
   string aktuellesWort = "a";
   size_t const maxLength = 5; //Oder was auch immer...
   cout << aktuellesWort << "\n";
   while(aktuellesWort.size() <= maxLength)
   {
      //So wie der Rückgabewert von Increase definiert ist, läuft die Scheife solange, bis das Wort verlängert werden muss
      while(Increase(aktuellesWort, aktuellesWort.size() - 1, zeichenpool))
      {
          cout << aktuellesWort << "\n";
          if(aktuellesWort == wort)
          {
              cout << "Erraten!" << endl;
              return 0;
          }
      }
      aktuellesWort += "a";
      cout << aktuellesWort << endl;
      if(aktuellesWort == wort)
      {
          cout << "Erraten!" << endl;
          return 0;
      }
   }
   return 0;
}

Felix

drakon

Ich würde es so ungefähr machen. Die Implementierung ist zwar nicht ganz elegant, aber es funktioniert.

Du hast es erfasst. Deine Rekursion ist eine sehr grosse Schraube im Getriebe..

Fellhuhn

Häßlich aber dafür ohne Rekursion.

#include <string>
#include <iostream>

using namespace std;

int main(){

    cout << "Zu erraten: ";
    string target;
    cin >> target;

    for(int i = 1; i <= target.length(); i++){
	string current(i, 'a');

	while(true){	    
	    if (current == target){
		cout << "Found: " << current << endl;
		return 0;
	    }

	    int raise = i - 1;
	    bool raised = false;
	    while(raise >= 0){
		if (current[raise] != 'z'){
		    current[raise]++;
		    raised = true;
		    break;
		}else{
		    current[raise] = 'a';
		    raise--;
		}
	    }
	    if (!raised){
		cout << "Not found with length " << i << endl;
		break;
	    }
	}
    }
}

Phoemuex

drakon schrieb:

Ich würde es so ungefähr machen. Die Implementierung ist zwar nicht ganz elegant, aber es funktioniert.

Du hast es erfasst. Deine Rekursion ist eine sehr grosse Schraube im Getriebe..

Bei den ganzen Ausgaben wird das der Performance auch nicht mehr viel tun

EDIT: Wenn man die Ausgaben entfernt ergibt sich ungefähr ein Faktor 2 Laufzeit zu Fellhuhns Code. Allerdings benutze ich ja auch noch den Zeichenpool

Fellhuhn

Mit Zeichenpool, immernoch ohne Rekursion. :p

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int main(){

    string chars = "abcdefghijklmnopqrstuvwxyz";

    cout << "Zu erraten: ";
    string target;
    cin >> target;

    for(int i = 1; i <= target.length(); i++){
	string current(i, chars[0]);
	vector<unsigned int> current_idx(i, 0);

	while(true){	    
	    if (current == target){
		cout << "Found: " << current << endl;
		return 0;
	    }

	    int raise = i - 1;
	    bool raised = false;
	    while(raise >= 0){
		if (current[raise] != chars[chars.length()-1]){
		    current_idx[raise]++;
		    current[raise] = chars[current_idx[raise]];
		    raised = true;
		    break;
		}else{
		    current[raise] = chars[0];
		    current_idx[raise] = 0;
		    raise--;
		}
	    }
	    if (!raised){
		cout << "Not found with length " << i << endl;
		break;
	    }
	}
    }
}

Machine

Soeinen einfachen Brute-Force Algorithmus findest du zu Hauf im Netz. Such doch mal ein bisschen bei Google.

Tachyon

Edit: Hier mal eine Version, die nicht funktioniert: :p

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()

{
    char base_set[] = "abcdefghijklmnopqrstuvvxuz";
    std::string str = "hallo";

    std::vector<char> input(str.begin(), str.end());
    std::vector<char> compare(input.size());
    do
    {
        std::copy(base_set, base_set + compare.size(), compare.begin());
        if(std::equal(input.begin(), input.end(), compare.begin()))
        {
            std::cout << "Found sequence: " << std::string(compare.begin(), compare.end()) << '\n';
            break;
        }
    }while(std::next_permutation(base_set, base_set + 26));

}

Fellhuhn

Tachyon schrieb:

...

Abgesehen von den beiden Tippfehlern in der Zeichenfolge funktioniert es auch nicht.

Tachyon

Fellhuhn schrieb:

Tachyon schrieb:

...

Abgesehen von den beiden Tippfehlern in der Zeichenfolge funktioniert es auch nicht.

Tipfehler okay, aber wieso funktioniert es nicht?

Okay, stimmt. next_permutation gibt das net her...

drakon

Zugegeben die Rekursion ist sehr verlokend.

Sehr unintuiver Code:

std::string pool = "abcdefghijklmnopqrstuwxyz";
	std::string word (3,' ');

	std::string::reverse_iterator it = word.rbegin ();
	std::string::iterator pit = pool.begin ();

	while (true)
	{
		if ( pit == pool.end () )
		{
			*it = *(pool.begin());
			++it;
			if (it == word.rend ())
				break;
			if( (*it) != ' ')
			{
				pit = std::find (pool.begin(),pool.end(),*it);
				++pit;
			}
			else
				pit = pool.begin();
			continue;
		}

		*it = *pit;	

		if ( it == word.rbegin () )
		{
			++pit;
		}
		else
			it = word.rbegin ();

		std::cout << word << "\n";
	}

Aber mir ist noch eine andere sehr geschickte Implementierung eingefallen. Habe jetzt gerade nur keine Zeit die zu schreiben. Spätestens Morgen werde ich die aber posten.

Fellhuhn

@drakon:

Funzt nicht. Da kommen nicht alle Strings vor.
Lass mal laufen und grep nach zb "naf".

drakon

Fellhuhn schrieb:

@drakon:

Funzt nicht. Da kommen nicht alle Strings vor.
Lass mal laufen und grep nach zb "naf".

Hmm. Also ich finde da alles, oder wie meinst du das?
Wenn ich da in der Schleife eine Bedingung mache und abbreche dann funktioniert das..

Sorry, dass es so lange gedauert hat, aber ich konnte am Freitag nicht mehr ins Netz..

Aber hier noch die kürzere Version:

void alg_3 (std::string pool , int digits )
{
	for ( int i = 0; i < pow (static_cast<float>(pool.size ()),digits) ; ++i)
	{
		int nr = i;
		std::string out = "";

		while ( nr )
		{
			out = pool[nr%(pool.size())]+out;
			nr/= pool.size ();
		}
		std::cout << out << "\n";
	}
}

Was aber nicht heisst, dass der schneller ist. Ich habe es mal ein bischen getestet und es ist herausgekommen, dass dieser Algorithmus bei kleineren Zahlen recht viel schneller sein kann, also mein erster, aber bei einem grossen "pool" länger hat. (Siehe Modulo in der inneren Schlaufe + Division. Liegt wahrscheinlich daran, habe aber hier keinen Profiler, um das zu bestätigen..)

&quot;Rate&quot;programm

"Rate"programm