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

WPC... geht weiter! -> wpc12

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

    Jester schrieb:

    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.

    Soll nur die Funktion wpc12 mitgeliefert werden, oder auch noch makeState und sonstiges?

    0
  • M

    Tomas: Jetzt bleibt nur noch die Frage offen, wer 1.000.000 Schalter zu Hause hat 😕 😉

    0
  • V

    Michael E. schrieb:

    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.

    nö.
    schalter 0: unterschiedlich
    schalter 1: unterschiedlich
    schalter 2: gleich
    schalter 3: unterschiedlich
    schalter 4: unterschiedlich
    schalter 5: gleich
    schalter 6: unterschiedlich
    schalter 7: unterschiedlich
    schalter 8: gleich
    schalter 9: unterschiedlich
    schalter 10: unterschiedlich
    schalter 11: gleich
    schalter 12: unterschiedlich
    schalter 13: unterschiedlich

    0
  • J

    Ponto schrieb:

    Soll nur die Funktion wpc12 mitgeliefert werden, oder auch noch makeState und sonstiges?

    Können wir uns darauf einigen, daß ihr wpc12.h included und die die nötigen Deklarationen bereitstellt? Ihr liefert dann nur noch die wpc12-Funktion.

    MfG Jester

    0
  • T

    Also so?

    #include "wpc12.h"
using namespace std;

const char* getName() {return "ich";}
const char* getMail() {return "ich at domain dot de";}

vector<size_t> wpc12(vector<bool>& state1, vector<bool>& state2) {
    // streng geheime Implementierung mit viel h4xx0r-Code
}

    class Unsolvable {}; steht dann in wpc12.h?
    Und die main-Funktion lieferst Du?

    0
  • V

    Michael E. schrieb:

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

    kann jetzt nicht mehr nachvollziehen, welche drei fälle es waren.

    hab dir soeben mein compilat geschickt. bin mal auf messungen gespannt.

    0
Anmelden zum Antworten