WPC... geht weiter! -> wpc12

[Jester]

volkard schrieb:

0 5 6 9 11 12

das ist ja gemein. ich kann deine lösung bestätigen, hab aber selber
1 3 4 5 7 10 11 13
raus. also gibt es tatsächlich mehrer lösungen für eine aufgabe und man muss echt dir kürzeste finden.

Hehe, hattest Du mir echt so viel Boshaftigkeit zugetraut?

[Michael E.]

borg: Für einen einzigen Aufruf?

[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!

[thetrue]

darf man assembler verwenden?

[Walli]

thetrue schrieb:

darf man assembler verwenden?

Was würde es dir bringen? Wahrscheinlich nichts.

[thetrue]

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

[Gast]

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?

[proKKer]

Findet euer algorithmus hierfür eine lösung?

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

bei mir wirft er die Exception.

[proKKer]

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