WPC... geht weiter! -> wpc12

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.

Sgt. Nukem

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

volkard

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.

volkard

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.

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

volkard

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.

Ponto

Hier auch nochmal Code, der Testcases erzeugt und diese vergleichen kann. Eine Datei mit 100 größeren Testfällen findet sich unter: -- DELETED --

Falls mein Algorithmus korrekt rechnet, sind diese auch in Ordnung. Nach dem Entpacken kann die Datei dem Tester übergeben werden. Das Format ist einfach. Zuerst kommt State1 dann State2 und dann die Größe des Ergebnisses. -1 bei Unsolvable. Zum Testen muss man nur wpc12 einfügen und die Testdatei übergeben.

./a.out testcases

Da es mehrere Lösungen gleicher Länge und auch verschiedene Anordnungen geben kann, ist der Code zum Checken des ganzen Ergebnisses auskommentiert.

#include <vector> 
#include <string> 
#include <iostream> 
#include <fstream>

class Unsolvable {}; 

std::vector<bool> makeState(std::string const& state) 
{ 
   std::vector<bool> res; 
   for(size_t index = 0; index<state.length(); ++index) 
   { 
      res.push_back(state[index]=='1'); 
   } 
   return res; 
} 

std::ostream & operator<<(std::ostream & out, std::vector<bool> & v)
{ 
    for(std::vector<bool>::iterator iter = v.begin(); iter != v.end(); ++iter) 
        out << *iter; 
    return out; 
}

std::vector<size_t> wpc12(std::vector<bool> & a, std::vector<bool> & b)
{ 

} 

void run_test(std::vector<bool> & a, std::vector<bool> & b)
{
   std::cout << a << " " << b;
   try {
      std::vector<size_t> res = wpc12(a, b);
      std::cout << " " << res.size();
//      for (std::vector<size_t>::size_type i = 0; i != res.size(); ++i) std::cout << " " << res[i];
      std::cout << std::endl;
   } catch (Unsolvable &) {
      std::cout << " -1" << std::endl;
   }
}

void random_test(std::vector<bool>::size_type maxlen)
{
   std::vector<bool>::size_type len = rand() % maxlen + 3;

   std::vector<bool> state1(len);
   std::vector<bool> state2(len);

   for (std::vector<bool>::size_type i = 0; i != len; ++i)
   {
      state1[i] = rand() % 2;
      state2[i] = rand() % 2;
   }

   run_test(state1, state2);
}

void rerun_tests(char const * filename)
{
   std::ifstream file(filename);
   while(file) {
      std::string state1;
      std::string state2;
      file >> state1;
      file >> state2;

      int size;
      file >> size;

      if (!file) break;

      try {
         std::vector<bool> state1v = makeState(state1);
         std::vector<bool> state2v = makeState(state2);

         std::vector<size_t> res = wpc12(state1v, state2v);
         if (size != res.size()) {
            std::cout << "Test failed. Wrong result size: " << state1 << " " << state2 << " " << size << std::endl;
            std::cout << "Expected: " << res.size() << std::endl;
            exit(0);
         }
//          for (std::vector<size_t>::size_type i = 0; i != res.size(); ++i) {
//             int pos;
//             file >> pos;
//             if (pos != res[i]) {
//                std::cout << "Test failed" << std::endl;
//                exit(0);
//             }
//          }

      } catch (Unsolvable &) {
         if (size != -1) {
            std::cout << "Test failed. Task is solvable:" << state1 << " " << state2 << " " << size << std::endl;
            exit(0);
         }
      }
   }
}

int main(int argc, char ** argv)
{
   if (argc != 1) {
      rerun_tests(argv[1]);
   } else {
      for(int i = 0; i != 100; ++i) {
         random_test(100000);
      }
   }
}

Sgt. Nukem

Optimizer schrieb:

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

*chr*

Sgt. Nukem schrieb:

volkard ist der zeckensack* des C++-Forums!

* (aus dem 3DCenter)

Ich habe mich gestern auch mal dran versucht. Noch nicht ganz ausgereift, aber zumindest kommt er bei den geposteten Tests schon mal auf das richtige Ergebnis. Und für eine Kette mit einer Länge von ca. 500 hat er auch sofort eine Lösung parat, ohne Wartezeit. Natürlich weiß ich da nicht mehr, ob es die schnellste Lösung ist
Wer sich eine richtig lange Kette zum Testen basteln will, nehme einfach diesen Fall:

state1 = makeState("01100010101011");
state2 = makeState("10101011011010");

und kopiere die Kette und füge sie beliebig oft aneinander. Das Resultat ist netterweise immer lösbar...

Michael E.

volkard schrieb:

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.

8 Fälle? Ich würd eher sagen 64.

volkard

Michael E. schrieb:

volkard schrieb:

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.

8 Fälle? Ich würd eher sagen 64.

8 sagte ich, weil ich beim testen immer jedes muster nach 000 zu bringen versuche.

kann auch 24 von 64 sagen.

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

WPC... geht weiter! -> wpc12