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

WPC... geht weiter! -> wpc12

  • J

    Bei mir sieht's ziemlich ähnlich aus.

    volkard und ThomasRiker wechseln sich immer mal ab, ponto ist meist etwas langsamer als beide. kwaart ist ein gutes Stück langsamer, edx fliegt noch lange vorher raus, er zieht nämlich Kopien von der Eingabe. Das ist schnell zu teuer.

    Im Moment schaue ich mal wer in 20 Sekunden die größte Lichterkette knackt. Wenn mir das Ergebnis danach zu knapp ist (das wird es vermutlich bei volkard und ThomasRiker), dann werde ich bei denen wohl mal den Schnitt über 100 große Lichterketten nehmen oder so. Irgendwie muß ich mich ja entscheiden. 🙂

    Btw.: volkard: mit was machst Du diese tollen Grafiken?

    0
  • J

    Jo Ponto ist grad bei ner 120Mio-Kette rausgeflogen.

    0
  • P

    Ich hab hier auch mal Läufe gemacht in 1.000.002 Schritten bis 100.000.000. Alles auf einem P4 mit 2.4GHz und 256RAM, keinen Swap. Der Compiler ist g++ (GCC) 4.0.0 20050220 und compiliert wurde mit g++ -O3 -march=pentium4.

    Es werden zwei Arten von Lösungen verglichen. Einerseits ist State1 und State2 identisch, so dass die Lösung leer sein muss. Andererseits erreicht man State2 nur durch umstellen aller Schalter.

    Es zeigt sich, dass TomasRikers und Volkards Algorithmen schnell die Puste ausgeht. Komischerweise ist auf meiner Maschine meiner auch schneller. Vielleicht hätte ich eher auf den Celeron optimieren sollen.

    Hier die Ergebnisse: http://www.pontohonk.de/wpc/lauf.html

    0
  • T

    @Ponto:
    Das muss ja ewig gedauert haben, diese Tabelle zu generieren.
    Allerdings darfst Du nicht vergessen, dass das nur ganz spezielle und seltene Fälle sind 😉

    @Jester:
    Wenn man es sich leicht machen will, nimmt man einfach die Kürze des Codes als Bewertungskriterium. Vor allem kann man dann 100%ig objektiv sein und kann definitiv sagen, wer der Gewinner ist.

    0
  • P

    TomasRiker schrieb:

    @Ponto:
    Das muss ja ewig gedauert haben, diese Tabelle zu generieren.
    Allerdings darfst Du nicht vergessen, dass das nur ganz spezielle und seltene Fälle sind 😉

    Die Zeiten sind Milisekunden, weshalb es nicht so lange gedauert hat. Hab jetzt einen Lauf eingefügt, wo immer eine Exception fliegt.

    0
  • M

    ich habe meins zwar nicht eingesandt und auch nicht wirklich optmiert. aber könnten ihr meins auch durchtesten?

    void pressButton(const size_t button, vector<bool>& state){
    if(button > 0)
        state[button-1]=! state[button-1];
    state[button]=! state[button];
    if(button + 1 < state.size())
        state[button+1]=! state[button+1];
}

void wpc12_h(std::vector<bool> &state1, const std::vector<bool> & state2, vector<size_t> & actions) {

	size_t button = 1;

	for (; button < state1.size(); ++button) {
		if (state1[button - 1] != state2[button - 1]) {
			pressButton(button, state1);
			actions.push_back(button);
		}
	}

	if (state1[button - 1] != state2[button - 1]) {
		throw Unsolvable();
	}
}

std::vector<size_t> wpc12(const std::vector<bool> & state1, const std::vector<bool> & state2) {

	//probiere erstmal mit pressen
	vector<size_t> alternative1(state1.size()), alternative2(state1.size());
	bool alternative1Available = false;
	try {
		vector<bool> state1Pressed(state1);
		pressButton(0, state1Pressed);
		alternative1.push_back(0);
		wpc12_h(state1Pressed, state2, alternative1);
		alternative1Available = true;
	} catch (const Unsolvable& ) {}

	//probiere ohne pressen und suche beste alternative aus
	try {
		vector<bool> state1Copy(state1);
		wpc12_h(state1Copy, state2, alternative2);
		if (alternative1Available) {
			return alternative1.size() < alternative2.size() ? alternative1 : alternative2;
		} else {
			return alternative2;
		}

	} catch (const Unsolvable& ) {
		if (alternative1Available) {
			return alternative1;
		} else {
			throw Unsolvable();
		}
	}
}

    Gruß mathik

    0
  • J

    TomasRiker schrieb:

    @Jester:
    Wenn man es sich leicht machen will, nimmt man einfach die Kürze des Codes als Bewertungskriterium. Vor allem kann man dann 100%ig objektiv sein und kann definitiv sagen, wer der Gewinner ist.

    Schon, aber ich hab gesagt Kriterium ist speed. Ich denke nen Schnitt über je 10 Ketten der Länge 10000000, 10000001, 10000002 ist das fairste. 🙂

    0
  • T

    Das war auch nicht auf diesen Wettbewerb hier bezogen, sondern auf Zukünftige 😉

    0
  • P

    Ich hab mal meinen Testrunner komplettiert, so dass er auch zufällige Ketten testen kann und diese nach Exception und nicht Exception trennt. Das Testprogramm findet ihr unter http://www.pontohonk.de/wpc/testrunner.C. Die Ergebnisse der Läufe unter http://www.pontohonk.de/wpc/lauf.html

    0
  • P

    mathik schrieb:

    ich habe meins zwar nicht eingesandt und auch nicht wirklich optmiert. aber könnten ihr meins auch durchtesten?

    ...

    Gruß mathik

    Dein Code arbeitet nicht korrekt.

    0
  • P

    Ich hab mal die stark wechselnden Zeiten meines Algrithmus untersucht, wie sie Volkards Graphik und auch meine Zeiten zeigen. Dabei bin ich auf etwas gestossen, was ich mir nicht erklären kann. So sehen die Messergebnisse in einem Bereich aus:

    vor 10452832 Werte um die 128 ms
    10452832 128.156 ms
    10452833 264.206 ms
    nach 10452833 um die 264 ms
    .
    .
    . Werte steigen langsam bis zu 270 ms
    .
    .
    11009888 274.9
    11009889 128.505
    nach 11009889 um die 264 ms

    Im Bereich 10452833-11009888 braucht der Algorithmus ungefähr 270 ms. Davor und danach bewegt er sich bei um die 130 ms. Es gibt noch viele weitere Bereiche, in denen der Algorithmus wesentlich mehr Zeit benötigt, als die Instanzen drumherum. Die Algorithmen von Volkard und TomasRiker zeigen ein ähnliches Verhalten hier nur dort ist die Differenz nicht so hoch. Dort steigt die Laufzeit plötzlich von 180 ms auf 215 ms. Kann sich jemand erklären, was hier passiert?

    0
  • M

    Ponto schrieb:

    mathik schrieb:

    ich habe meins zwar nicht eingesandt und auch nicht wirklich optmiert. aber könnten ihr meins auch durchtesten?

    ...

    Gruß mathik

    Dein Code arbeitet nicht korrekt.

    welcher testfall?

    0
  • J

    So, ich habe die Auswertung fertig:

    1. David Scherfgen
    2. volkard
    3. ponto
    4. edx

    die Codes und ein paar Meßergebnisse gibt's auf wpc.schornboeck.net

    MfG Jester

    0
  • P

    mathik schrieb:

    welcher testfall?

    State1: 010100111
    State2: 011101000

    Falsches Ergebnis: 0 0 0 0 0 0 0 0 0 3 4 7

    0
  • D

    Mathematische Betrachtungen: Paritäten

    Ich gehe wieder von der transformierten Aufgabe aus, den State S = xxxx... auf 0 zu reduzieren.

    Parität: 1, wenn die Anzahl der 1en ungerade ist. 0, wenn die Anzahl der 1en gerade ist.

    3n+2:

    xxxxxxxxx...xxxxx  and
110110110   11011  (110 wiederholend)

    Egal welchen Schalter man umlegt - die Parität ändert sich nicht.
    Die Kette ist genau dann lösbar (auf 0 reduzierbar), wenn die Parität 0 ist. Wenn sie 1 ist, existiert keine Lösung.

    3n:

    xxxxxxxxx...xxxxxx  and
011011011   011011  (011 wiederholend)

    Die Parität lässt sich nur durch den Schalter ganz links ändern.
    Dieser Schalter muss also genau dann betätigt werden, wenn die Parität 1 ist.

    3n+1:

    xxxxxxxxx...xxxxxxx  and
101101101   1011011  (101 wiederholend)

    Die Parität lässt sich nur durch den Schalter ganz links ändern.
    Dieser Schalter muss also genau dann betätigt werden, wenn die Parität 1 ist.

    0
  • V

    Jester schrieb:

    Btw.: volkard: mit was machst Du diese tollen Grafiken?

    ms-excel.
    zuerst schreibe ich ne von excel lesbare tabelle, indem ich starte "wpc12.exe > t.cvs" (dazu hab ich \t im prog als trenner genommen). dann starte ich excel und lade die daten "excel t.cvs". dann drücke ich den button (das smart-icon) "diagramm-assistent". dann suche ich xy-dagramm aus. dann klicke ich auf "fertig stellen", weil alle weiteren fragen des assis unerheblich sind. fertig.

    0
  • M

    Ponto schrieb:

    mathik schrieb:

    welcher testfall?

    State1: 010100111
    State2: 011101000

    Falsches Ergebnis: 0 0 0 0 0 0 0 0 0 3 4 7

    huh...

    was ist der unterschied zwischen:

    vector<size_t> alternative(state1.size());

und 

vector<size_t> alternative;
alternative.reserve(state1.size())

    ?????

    ersteres macht irgendwie nicht das, was ich will...

    könntest du es nochmal versuchen, mit dem folgenden:

    void pressButton(const size_t button, vector<bool>& state){
    if(button > 0)
        state[button-1]=! state[button-1];
    state[button]=! state[button];
    if(button + 1 < state.size())
        state[button+1]=! state[button+1];
}

void wpc12_h(std::vector<bool> &state1, const std::vector<bool> & state2, vector<size_t> & actions) {

	size_t button = 1;

	for (; button < state1.size(); ++button) {
		if (state1[button - 1] != state2[button - 1]) {
			pressButton(button, state1);
			actions.push_back(button);
		}
	}

	if (state1[button - 1] != state2[button - 1]) {
		throw Unsolvable();
	}
}

std::vector<size_t> wpc12(const std::vector<bool> & state1, const std::vector<bool> & state2) {

	//probiere erstmal mit pressen
	vector<size_t> alternative1, alternative2;
	alternative1.reserve(state1.size());
	alternative2.reserve(state1.size());
	bool alternative1Available = false;
	try {
		vector<bool> state1Pressed(state1);
		pressButton(0, state1Pressed);
		alternative1.push_back(0);
		wpc12_h(state1Pressed, state2, alternative1);
		alternative1Available = true;
	} catch (const Unsolvable& ) {}

	//probiere ohne pressen und suche beste alternative aus
	try {
		vector<bool> state1Copy(state1);
		wpc12_h(state1Copy, state2, alternative2);
		if (alternative1Available) {
			return alternative1.size() < alternative2.size() ? alternative1 : alternative2;
		} else {
			return alternative2;
		}

	} catch (const Unsolvable& ) {
		if (alternative1Available) {
			return alternative1;
		} else {
			throw Unsolvable();
		}
	}
}

    habe nur das geändert:

    vector<size_t> alternative1, alternative2;
	alternative1.reserve(state1.size());
	alternative2.reserve(state1.size());

    danach kommt bei dem testfall 3,4,7 raus. ohne diese komische nullen davor...

    Gruß mathik

    0
  • J

    std::vector<size_t> alternative(size) legt einen vector<size_t> mit size Elementen an, die default-initialisiert werden.

    das reserve reserviert nur den Speicher ohne direkt Elemente drin abzulegen.

    0
  • J

    volkard schrieb:

    zuerst schreibe ich ne von excel lesbare tabelle, indem ich starte "wpc12.exe > t.cvs" (dazu hab ich \t im prog als trenner genommen). dann starte ich excel und lade die daten "excel t.cvs". dann drücke ich den button (das smart-icon) "diagramm-assistent". dann suche ich xy-dagramm aus. dann klicke ich auf "fertig stellen", weil alle weiteren fragen des assis unerheblich sind. fertig.

    Okay, dieses Wissen werde ich in die nächste Auswertung mit einfließen lassen. 🙂

    0
  • M

    Jester schrieb:

    std::vector<size_t> alternative(size) legt einen vector<size_t> mit size Elementen an, die default-initialisiert werden.

    das reserve reserviert nur den Speicher ohne direkt Elemente drin abzulegen.

    oh ja, danke.
    hab in letzter zeit zu viel java programmiert... 😉

    könntest du den test-code nochmal posten?

    würde mal gerne schauen, wo meine lösung gestanden hätte...

    Gruß mathik

    0
Anmelden zum Antworten