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

WPC... geht weiter! -> wpc12

  • 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
  • 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
Anmelden zum Antworten