"Rate"programm

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