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

WPC... geht weiter! -> wpc12

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

    ThomasRiker: genau so 🙂

    0
  • M
     

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

    Für mich sind die Bits an Stelle 8 unterschiedlich.

    Wohin hast dus geschickt? Hier steht meine EMail-Adresse einen Tag lang, sodass du sie nur noch zu kopieren brauchst:

    [EDIT] weg [/EDIT]

    0
  • ?

    gibts da nen trick bei der ganzen sache??
    habt ihr rekursive oder iterative lösungen?

    mein algo ist mist! O(2^n)!!
    ich glaube ich bin zu dumm für diese aufgabe 😞

    ihr redet von hunderttausend zeichen und mein algo braucht schon bei 50 zeichen mehr als ne minute. das kanns doch net sein??!

    0
  • ?

    Also meiner iteriert nur über die Folge, braucht also lineare Zeit. Das allerdings zweimal, weil ich wegen einem ungelösten Problem noch zwei Durchgänge brauche. Wenn ich den zweiten Durchgang noch wegrationalisieren kann, dann wäre ich bei einfach linearer Komplexität 🙂
    Allerdings bin ich, wie gesagt, nicht 100% sicher, dass der Algorithmus tatsächlich immer die beste Lösung findet, vielleicht ist er für spezielle Fälle auch zu einfach, wer weiß?

    0
  • V

    Michael E. schrieb:

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

    Für mich sind die Bits an Stelle 8 unterschiedlich.

    ja, die lampen sind unterschiedlich.

    ich meine die schalter, die gedrückt werden müssen.

    wenn es zwei lösunen gibt, und bei der einen lösung der schalter 8 nicht gedrückt wird, dann bei der anderen auch nciht.

    0
  • M

    EMail angekommen.

    Meins is seit gestern Abend unverändert, d.h. immer noch verbuggt und unoptimiert.

    Ergebnis:

    wpc12 Michael E.

Minimum:      292
Durchschnitt: 89142

Minimum:      332
Durchschnitt: 88343

Minimum:      304
Durchschnitt: 89066

wpc12 volkard
Minimum:      2120
Durchschnitt: 42743

Minimum:      2112
Durchschnitt: 43326

Minimum:      2120
Durchschnitt: 43913

    Gemessen nach einem Neustart.

    0
  • T

    Vermutung:
    Wenn die Zeichenkettenlänge 3*n+2 ist, dann gibt es entweder zwei Lösungen oder keine. Der Umkehrschluss (Wenn die Zeichenlänge nicht 3*n+2 ist, dann gibt es immer genau eine Lösung) scheint auch zu stimmen.

    0
  • M

    volkard: Kannst du mir bitte auch noch das hier schicken (jeder andere ist natürlich auch eingeladen):

    #include <fstream>
#include <iterator>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
// Hoffentlich hab ich jetzt nichts vergessen :p
using namespace std;

int main()
{
	ifstream file("testfaelle.txt");
	vector<string> zeile;
	istream_iterator<string> iin(file), eof;
	copy(iin, eof, back_inserter(zeile));

	for(vector<string>::iterator i = zeile.begin(); i != zeile.end(); i+=2)
	{
		vector<size_t> result = wpc12(makeState(*i), makeState(*(i+1)));

		*(i+1) += "\n";
		for(vector<size_t>::iterator j = result.begin(); j != result.end(); ++j)
		{
			stringstream str;
			str << *j;
			string buffer;
			str >> buffer;

			*(i+1) += buffer + " ";
		}
		*(i+1) += "\n\n";
	}
	ofstream out("testfaelle.txt");
	copy(zeile.begin(), zeile.end(), ostream_iterator<string>(out, "\n"));
}
    0
  • V

    Michael E. schrieb:

    volkard: Kannst du mir bitte auch noch das hier schicken

    morgen oder so. will erst nochmal am speed drehen.

    0
  • ?

    TomasRiker schrieb:

    💡 Bin jetzt bei 1.000.000 Zeichen in durchschnittlich 63 ms!

    Hui, das ist schnell, da komme ich nicht einmal annähernd hin. Da werde ich wohl noch an der Speed-Schraube gewaltig drehen müssen 🙂

    Habt ihr übrigens mal versucht, wie groß bei euch der Geschwindigkeitsunterschied zwischen dem in der Aufgabe vorgegebenen vector<bool> und alternativem vector<char> ist? vector<bool> als Pseudo-Container fügt ja schließlich auch zusätzliche Operationen hinzu. Bei mir mit mingw-gcc 3.2 ist der Unterschied bei ca. 90000 Zeichen immerhin von 53ms auf 31ms...

    0
  • L

    ich habe gelesen, dass man den vector<bool> möglichst vermeiden sollte, da er sich nicht wie ein STL-Container verhält...

    0
  • ?

    Das ist das, was ich meine. vector<bool> ist weder ein Container, noch ist er ein vector. Er ist ein fehlgeschlagenes Experiment...
    In dieser Aufgabe funktioniert er trotzdem, aber er ist auf Größe, nicht auf Geschwindigkeit optimiert. Der Geschwindigkeitsunterschied zwischen vector<bool> und vector<char> bei dieser Aufgabe hängt aber von der STL-Implementierung ab, deswegen habe ich interessehalber mal gefragt 🙂

    0
  • D

    Mathematische Betrachtungen, Nummer 1

    (1) Wir stellen fest, dass die Schalter sich wie XOR-Operationen mit Bitmuster (0+)111(0+) (bzw. am Anfang und Ende ein offensichtlich leicht anderes Bitmuster) verhalten.

    (2) (Kommutativität) Es folgt, dass die Reihenfolge, in der die Schalter betätigt werden, egal ist.

    (3) (Eindeutigkeit) In der optimalen Lösung wird kein Schalter mehr als 1 mal betätigt (Bitmuster XOR Bitmuster = 0).

    (4) Sei Z(k) der im k-ten Zug betätigte Schalter und N die Gesamtzahl der benötigten Züge.

    (5) Sei M(k) das Bitmuster des k-ten Schalters.

    (6) Sei S1 das Eingangsmuster und S2 das Ausgangsmuster.

    (7) (Reduktion) Wir suchen eine Zugfolge Z(k) mit S1 XOR(i=1..N) M(Z(k)) = S2.
    Dies kann man offensichtlich reduzieren auf:
    (S1 XOR S2) XOR(i=1..N) M(Z(k)) = 0.

    (8) Wenn eine Zugfolge existiert, die S1 in S2 transformiert, dann es gibt auch eine optimale Zugfolge Z mit der Eigenschaft:
    Z(1) < Z(2) < ... < Z(n)
    Im Folgenden sei Z diese Zugfolge.

    (9) Seien die Bits von 1 bis N angeordnet wie die Schalter. Das Bit an der Stelle k sei Bit(k).

    (10) Wird der Schalter Z(k) betätigt, dann darf nach der Ausführung kein Bit b < Z(k) mehr gesetzt sein, denn es gilt Z(k) < Z(k+1).

    (11) Es gilt also
    (11.1) Z(1) = 1 oder
    (11.2) Z(1) = j+1 mit Bit(j) = 1 und OR(i=1..j-1) Bit(i) = 0 (kein Bit kleiner j ist gesetzt, aber j ist gesetzt).

    (12) Dies ist die hier schon öfter erwähnte Aufspaltung in 2 lineare Fälle.

    0
  • D

    Mathematische Betrachtungen, Nummer 2:
    Bitmuster der Länge 3n

    ... sind immer auf 0 reduzierbar.

    Beweis durch vollst. Induktion:

    Für n=1 ist die Behauptung wahr.

    Nun schliesse ich von n auf n+1:

    Das Teilmuster von Bit 1 bis 3n lässt sich nach Induktionsvoraussetzung auf lauter Nullen bringen. Wir erhalten 0{3n}(0|1){3}
    Für (0|1){3} = 000 | 111 | 011 | 100 sind wir schnell durch betätigen der letzten 2 Schalter fertig.

    Die Fälle (0|1){3} = 001 | 010 | 101 | 110 reduzieren wir durch die letzten 2 Schalter auf 001 und erhalten: 0{3n+2}1

    (000)(000)(000)..., (110)(000)(000)..., (001)(000)(000)..., (000)(110)(000)...

    So kommt man irgendwann bei (000)(000)(000)...(111) an. Fertig.

    0
  • ?

    Jetzt sind wohl alle sehr beeindruckt. 🕶 👍

    0
Anmelden zum Antworten