"Rate"programm

[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..)