WPC... geht weiter! -> wpc12

Walli

thetrue schrieb:

darf man assembler verwenden?

Was würde es dir bringen? Wahrscheinlich nichts.

Mit SSE 2 könnte ich noch einiges rausholen.

Hab den optimalen Algorithmus schon gefunden und wollte diesem noch den letzten Schliff geben.

borg

Michael E. schrieb:

[EDIT] Bei mir merk ich bei size() = 68 erst beim Faktor 10000 ne Verzögerung. Das ist die erste Version!

ok, ich hab also definitiv einen falschen ansatz

@Jester, kann es sein das man nie die Exception schmeißen muss? ;-))))

volkard

schrieb:

@Jester, kann es sein das man nie die Exception schmeißen muss? ;-))))

mach mal 000 zu 001

000
111
001

volkard

Optimizer schrieb:

000
111
001

ups!

Michael E.

Mist, den Fall hab ich nicht bedacht. Meine Implementation ist lückenhaft

borg

dann macht mal 10011 zu 11100, jesters beispiel. das geht definitiv nicht. sonst ist mein toller suchbaum nicht nur langsam sondern auch kaputt

borg

Michael E. schrieb:

Mist, den Fall hab ich nicht bedacht. Meine Implementation ist lückenhaft

da kommt hoffnung auf bei mir

Michael E.

Gibts eigentlich auch so nen Fall mit size > 3?

Findet euer algorithmus hierfür eine lösung?

wpc12(makeState("011011101011111001"), makeState("101010110110101000"))

bei mir wirft er die Exception.

habe mich vertan

die lösung sollte lauten
0, 6, 7, 8, 9, 10, 14, 15, 17

volkard

Michael E. schrieb:

Mist, den Fall hab ich nicht bedacht. Meine Implementation ist lückenhaft

meine auch. von den 8 fällen mit 3 lampen sind 3 fälle kaputt.

TomasRiker

Ich habe mal ein Testszenario gemacht:

int main() {
	vector<string> tests;

	tests.push_back("10011");
	tests.push_back("11100");

	tests.push_back("011011101011111001");
	tests.push_back("101010110110101000");

	tests.push_back("011011101011111001100");
	tests.push_back("101010110110101000010");

	tests.push_back("01100010101011");
	tests.push_back("10101011011010");

	tests.push_back("010101010");
	tests.push_back("101010101");

	tests.push_back("000");
	tests.push_back("000");

	tests.push_back("000");
	tests.push_back("001");

	tests.push_back("000");
	tests.push_back("010");

	tests.push_back("000");
	tests.push_back("011");

	tests.push_back("000");
	tests.push_back("100");

	tests.push_back("000");
	tests.push_back("101");

	tests.push_back("000");
	tests.push_back("110");

	tests.push_back("000");
	tests.push_back("111");

	for(vector<string>::const_iterator i = tests.begin(); i != tests.end(); i += 2) {
		try {
			cout << wpc12(makeState(*i), makeState(*(i + 1))) << endl;
		}

		catch(Unsolvable*) {
			cout << "[unsolvable]" << endl;
		}
	}

	return 0;
}

Die Ausgabe sollte sein (wenn mein Programm stimmt):

[unsolvable]
0, 6, 7, 8, 9, 10, 14, 15, 17
1, 3, 4, 8, 12, 13, 14, 16, 17, 18, 19, 20
0, 5, 6, 9, 11, 12
1, 4, 7
[empty]
0, 1
0, 1, 2
2
1, 2
0, 2
0
1

volkard

TomasRiker schrieb:

Ich habe mal ein Testszenario gemacht:

ich hab auch eins gemacht.

vector<bool> pressButton(size_t button,vector<bool> in){
	vector<bool> out=in;
	if(button-1>=0)
		out[button-1]=!out[button-1];
	out[button]=!out[button];
	if(button+1<out.size())
		out[button+1]=!out[button+1];
	return out;
}

ostream& operator<<(ostream& out,vector<bool> const& v){
	for(vector<bool>::const_iterator i=v.begin();i!=v.end();++i)
		cout<<*i;
	return out;
}

ostream& operator<<(ostream& out,vector<size_t> const& v){
	for(vector<size_t>::const_iterator i=v.begin();i!=v.end();++i)
		cout<<*i<<' ';
	return out;
}

int main(){
	State state1=makeState("011011101011111001");
	State state2=makeState("101010110110101000");
	cout<<wpc12(state1,state2)<<endl;

	char buf1[]="0000000000000";
	char buf2[]="0000000000000";

	queue<State> border;
	map<State,size_t> seen;
	State state=makeState(buf1);
	border.push(state);
	seen[state]=1;
	while(!border.empty()){
		State current=border.front();
		border.pop();
		for(size_t i=0;i<current.size();++i){
			State next=pressButton(i,current);
			if(seen[next]==0){
				seen[next]=seen[current]+1;
				border.push(next);
			}
		}
	}
/*	for(map<State,size_t>::iterator i=seen.begin();i!=seen.end();++i)
		cout<<i->first<<' '<<i->second-1<<endl;
	cout<<seen.size()<<endl;*/

	do{
		State state1=makeState(buf1);
		State state2=makeState(buf2);
		size_t x1=seen[state2];
		size_t x2=0;
		try{
			x2=wpc12(state1,state2).size()+1;
		}
		catch(Unsolvable){
		}
		cout<<buf2<<' '<<x1<<' '<<x2<<"     \r";
		if(x1!=x2){
			cout<<"\nfehler"<<endl;
			return 1;
		}
		for(char* p=buf2;++*p=='2';*p++='0')
			;
	}while(buf2[sizeof(buf2)-1]=='\0');
}

und meine implemetierung besteht sogar. *freu*

volkard

TomasRiker schrieb:

catch(Unsolvable*) {

ähm. das ist nicht ok. du sollst Unsolvable schmeißen und nicht Unsolvable*.

TomasRiker

volkard schrieb:

und meine implemetierung besteht sogar. *freu*

Meine auch!

volkard schrieb:

ähm. das ist nicht ok. du sollst Unsolvable schmeißen und nicht Unsolvable*.

Ja, hatte "throw new Unsolvable" geschrieben.
Du musst wissen, dass ich Exceptions normalerweise nicht verwende

Nochwas...
Sollen die Funktionen jetzt name() und email() oder getName() und getMail() (so wie in dem gepinnten Thema im "FAQ"-Forum geschrieben) heißen?

volkard

auf welchem compiler wird getestet?

darf man ein

//bitte auskommemntieren, wenn es nicht compiliert
#define MEINCOMPILER

setzen?

Jetzt geht's los. Jetzt wird volkard mit ner hardcore-h4x0r-1337-0p71m1273n Lösung ankommen, gegen die keiner mehr ne Chance hat. Du bist gemein, volkard.

WPC... geht weiter! -&gt; wpc12

WPC... geht weiter! -> wpc12