WPC... geht weiter! -> wpc12

borg

Michael E. schrieb:

borg: Für einen einzigen Aufruf?

ja, deswegen frag ich. mir kommts auch schrecklich lang vor

Michael E.

Dein Ding kann man doch sicher als Referenz missbrauchen, oder?

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

darf man assembler verwenden?

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*.

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

WPC... geht weiter! -> wpc12