3. WPC... geht weiter! -> wpc12

WPC... geht weiter! -> wpc12

  • ?

    000
    111
    001

    0
  • V

    Optimizer schrieb:

    000
    111
    001

    ups!

    0
  • M

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

    0
  • B

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

    0
  • B

    Michael E. schrieb:

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

    da kommt hoffnung auf bei mir 🤡

    0
  • M

    Gibts eigentlich auch so nen Fall mit size > 3?

    0
  • ?

    Findet euer algorithmus hierfür eine lösung?

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

    bei mir wirft er die Exception.

    0
  • ?

    habe mich vertan

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

    0
  • V

    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.

    0
  • T

    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
    0
  • V

    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*

    0
  • V

    TomasRiker schrieb:

    catch(Unsolvable*) {

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

    0
  • T

    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?

    0
  • V

    auf welchem compiler wird getestet?

    darf man ein

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

    setzen?

    0
  • ?

    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. 😉 🤡

    0
  • S

    Optimizer schrieb:

    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. 😉 🤡

    Etwas ähnliches hab' ich auch eben gedacht... 🤡

    0
  • V

    Optimizer schrieb:

    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. 😉 🤡

    nein. meine lösung ist bereits stabil.
    es ist ganz allein die frage, ob ich das feature ausnutzen darf, daß beim g++ ein

    size_t size=state1.size();
size_t result[size]

    erlaubt ist.
    ich müßte es mit #ifdef wegpacken und ein

    size_t size=state1.size();
size_t *result=new size_t[size];

    dagegenhalten, um standardkonform zu sein.

    ich rechne nämlich mit einer fürchterlich knappen entscheidung, wo 20 leute fast den selben suchbaum durchlaufen.

    aber hat sich bei mir erledigt. ich trage die kosten für ein nutzloses new[]. ich komme nämlich auf unter O(n^2.3) und da kann man in einer sekunde schon ganz schön viele zahlen rotzen. da ist das new[] nicht mehr schlimm.

    0
  • V

    Sgt. Nukem schrieb:

    Optimizer schrieb:

    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. 😉 🤡

    Etwas ähnliches hab' ich auch eben gedacht... 🤡

    mich ehrt euer vertrauen.
    aber dafür wurden ja drei medallien eingeführt. ich kann unmöglich alle drei kriegen.
    und mal ehrlich, ich bin weder h4x0r noch l337. im geigentiel. ich sage immer wieder, daß ich die asm-hacker aus dem spiele-forum bei enorm vielen problemfällen mit standard-c++ fürchterlich plattmache. ganz ohne l337. nur mit mathe und ein paar algos und datenstrukturen.
    und sowas wie algos und datenstrukturen könnt ihr euch auch fein selber einfallen lassen. ihr sollt es sogar. das war die aufgabe.
    und für die, die sowas toll finden ist wpc wirklich eine gute übung. mit der zeit wird man besser und bald macht man die l337 h4x0rs platt, wie sich das gehört.

    0
  • ?

    Du hast doch mal nen eigenen Allokator geschrieben, taugt der für diesen Fall nicht?
    Amsonsten: volkard for president! 👍

    0
  • V

    Optimizer schrieb:

    Du hast doch mal nen eigenen Allokator geschrieben, taugt der für diesen Fall nicht?

    schon längst gelöscht, weil der suboptimal war.

    Amsonsten: volkard for president! 👍

    thx.

    0
Anmelden zum Antworten