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

WPC... geht weiter! -> wpc12

  • ?

    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
  • P

    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);
      }
   }
}
    0
  • S

    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)

    0
  • ?

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

    0
  • M

    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.

    0
  • V

    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.

    0
  • T

    kwaart schrieb:

    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 🙂

    Warum weißt Du das nicht?
    PS: Mein Algorithmus schafft momentan Zeichenkette mit einer Länge von 90000 innerhalb von 30 ms! 🙂

    0
  • M

    Ich bin 3x so schnell. Aber ich hab immer noch die Lücke.

    0
  • ?

    [quote="TomasRikerWarum weißt Du das nicht?
    PS: Mein Algorithmus schafft momentan Zeichenkette mit einer Länge von 90000 innerhalb von 30 ms! :)[/quote]

    Öh, naja, weil ich nicht mathematisch bewiesen habe, dass mein Algorithmus auf jeden Fall die schnellste Lösung erwischt. Er tut das in den Testfällen mit überschaubarer Länge, wo ich das noch überblicke, und ich glaube, dass er korrekt arbeiten müsste, aber das ist ja kein Beweis 🙂 Bei 500 oder gar 90000 Lampen werde ich jedenfalls sicherlich nicht ausprobieren, ob ich noch auf eine schnellere Lösung komme 😉

    0
  • V

    TomasRiker schrieb:

    PS: Mein Algorithmus schafft momentan Zeichenkette mit einer Länge von 90000 innerhalb von 30 ms! 🙂

    klasse. und wie schnell ist dein prozessor?

    0
  • V

    ich vermute mal: es gibt für jedes state-paar maximal zwei lösungen. falls beide lösungen existieren, dann gleichen sie sich an den den schaltern 2, 5, 8, ..., 3*n+2 und an den anderen schaltern unterscheiden sie sich.

    0
  • T

    volkard schrieb:

    TomasRiker schrieb:

    PS: Mein Algorithmus schafft momentan Zeichenkette mit einer Länge von 90000 innerhalb von 30 ms! 🙂

    klasse. und wie schnell ist dein prozessor?

    Ein 486er mit 100 MHz.

    0
  • M

    volkard: Hat bei dir eigentlich auch 000 -> 001, 100 und 111 nicht geklappt?

    TomasRiker: Ou, da hab ich ein anderes Kaliber. P IV 2,6Ghz

    Wenn du willst, kannst du mir ja mal dein kompiliertes Programm (keine Angst, ich kann kein Assembler 😉 ) schicken mit folgendem Test:

    // Bitte nie Unsolvable werfen, stattdessen nen leeren vector<size_t>

unsigned int random()
{	// voellig verkorkste Funktion :o]
	return ((rand() + rand() + rand() + rand() + rand() + rand()) % 1000);
}

vector<bool> invent(unsigned int size)
{
	vector<bool> result;
	for(; size; --size)
		result.push_back(random() % 2);

	return result;
}

#pragma warning(push) 
#pragma warning(disable:4035) 
unsigned __int64 rdtsc() 
{ 
	__asm rdtsc; 
} 
#pragma warning(pop)

std::ostream& operator << (std::ostream& OutputStream, const __int64 nNumber) { 
    char szBuffer[25]; 
    sprintf(szBuffer, "%I64d", nNumber); 
    OutputStream << szBuffer; 
    return OutputStream; 
} 

int main()
{
	unsigned __int64 min=0-1, average=0, time;

	try
	{
		int d = 10000;    // Anzahl Durchlaeufe
		for(int i = 0; i < d; ++i)
		{
			srand(i);

			unsigned int size;
			do
			{
				size = random();
			}
			while(size < 3);

			vector<bool> state1 = invent(size);
			vector<bool> state2 = invent(size);

			time = rdtsc();		
			vector<size_t> result = wpc12(state1, state2);
			time = rdtsc() - time;
			if(time < min)
				min = time;
			average += time;

			/*for(vector<size_t>::iterator i = result.begin(); i != result.end(); ++i)
				cout << *i << "\n";*/
		}
		cout << "Minimum:      " << min << "\n";
		cout << "Durchschnitt: " << average/d;
	}
	catch(Unsolvable &e)
	{
		cout << "Unsolvable";
	}
}

    EMail: the punkt michael punkt e ät gmail punkt com

    0
  • T

    Das mit dem 486er war nur ein Witz *g*
    Ich hab einen Athlon XP 3000+, also keine Angst.

    0
  • M

    Puh 🙂

    0
  • M

    volkard schrieb:

    ich vermute mal: es gibt für jedes state-paar maximal zwei lösungen. falls beide lösungen existieren, dann gleichen sie sich an den den schaltern 2, 5, 8, ..., 3*n+2 und an den anderen schaltern unterscheiden sie sich.

    Nö, bei

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

    gibt es mindestens zwei Lösungen

    0 5 6 9 11 12
1 3 4 5 7 10 11 13

    und die achte Stelle unterscheidet sich.

    0
  • T

    💡 Bin jetzt bei 1.000.000 Zeichen in durchschnittlich 63 ms!

    0
  • J

    Wow, hier tut sich ja richtig was 🙂

    Eine Einsendung hab ich übrigens schon erhalten.
    Bitte achtet darauf, daß ihr keinen unnötigen Code wie ne eigene main mitliefert.
    Sonost muß ich jede Einsendung vorm testen nochmal anfassen. Und das dürfte bei der regen Beteiligung durchaus anstrengend werden.

    0
  • J

    Achja und die Namen für die Funktionen die Name und eMail zurückliefern bitte nach Möglichkeit so wie's in der FAQ beschrieben ist. 🙂
    Ich ändere mein Posting gleich noch auf dem wpc-Board.

    MfG Jester

    0
Anmelden zum Antworten