WPC... geht weiter! -> wpc12

d-f-g

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.

volkard

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.

mathik

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

Jester

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.

Jester

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.

mathik

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

Ponto

Mathik, nun scheint es korrekt zu laufen, aber nicht besonders schnell.

Sgt. Nukem

Jester schrieb:

So, ich habe die Auswertung fertig:

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

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?
Ist das die Ehre des Gewinners?!?

Jester

der Code enthielt eine Funktion const char* getName();

Ich habe die Namen aus den Ausgaben meines Testprogramms kopiert. Das gibt eben aus was derjenige da reingeschrieben hat.

btw.: volkard heißt volkard

Sgt. Nukem

Jester schrieb:

btw.: volkard heißt volkard

Also ich tippe eher auf "Volkard".

volkard

Sgt. Nukem schrieb:

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?

wieso behauptest du, ich würde nicht real volkard heißen?

Sgt. Nukem

volkard schrieb:

Sgt. Nukem schrieb:

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?

wieso behauptest du, ich würde nicht real volkard heißen?

Weil kleingeschriebene Eigennamen genau wie "Jesus" und Co. in Deutschland verboten sind.

volkard

Sgt. Nukem schrieb:

volkard schrieb:

Sgt. Nukem schrieb:

Wieso wird von David der Realname verraten, von den anderen aber nicht?!?

wieso behauptest du, ich würde nicht real volkard heißen?

Weil kleingeschriebene Eigennamen genau wie "Jesus" und Co. in Deutschland verboten sind.

"volkard" ist großgeschrieben, das siehst du bloß nicht, weil auf dem übertraungsweg von mir bis zu dir ein paar der besonders irrelevanten daten verloren gehen.

mathik

Ponto schrieb:

Mathik, nun scheint es korrekt zu laufen, aber nicht besonders schnell.

stimmt, habe das selber mal mit euren implementierungen verglichen.
so faktor 2 - 3 langsamer.
aber danke.

gruß mathik

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

WPC... geht weiter! -> wpc12