WPC... geht weiter! -> wpc12

Jester

Jo richtig

ich werd's gleich ändern.

Walli

Noch was...

std::vector<bool> state1 = makeState("10011");
std::vector<bool> state2 = makeState("11100");

wpc12(state1, state2); // sollte eine Exception werfen

Warum Exception. Wenn ich state1[2] umlege, dann sind doch so wie ich das verstanden habe beide gleich...

evilissimo

Hi Walli,

wenn du state[2] bei einem 00000 vector umlegst sieht das so aus:

0 1 2 3 4    <- INDEX
   _|_|_|_|_
   0|0|0|0|0

-> state[2]

   0 1 2 3 4    <- INDEX
   _|_|_|_|_
   0|1|1|1|0

hier noch n beispiel mit gesetzten bits

0 1 2 3 4    <- INDEX 
   _|_|_|_|_
   0|1|0|1|0

-> state[2]

   0 1 2 3 4    <- INDEX 
   _|_|_|_|_
   0|0|1|0|0

Jester

Walli: Dann ist aber das letzt Bit beim ersten noch gesetzt, beim zweiten nicht.

Walli

Jester schrieb:

Walli: Dann ist aber das letzt Bit beim ersten noch gesetzt, beim zweiten nicht.

Ach shit, habe ich übersehen .

Mortal2006

Coole aufgabe ! Bin ich leider zu doof zu...

evilissimo

@ Jester: Hast du mal nen anderen Testfall der länger ist und n ergebnis liefern sollte?

Wäre cool. Weil mit den 2 angegebenen Beispielen sicherzustellen das der Algo korrekt arbeitet, ist etwas schwierig. (IMHO)

MfG

Jester

Ich werd versuchen im Laufe der nächsten Stunden was zu basteln

volkard

eViLiSSiMo schrieb:

@ Jester: Hast du mal nen anderen Testfall der länger ist und n ergebnis liefern sollte?
Wäre cool. Weil mit den 2 angegebenen Beispielen sicherzustellen das der Algo korrekt arbeitet, ist etwas schwierig. (IMHO)

keine garantie auf richtigkeit:

#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <windows.h>
using namespace std;

// Helper für leichten Aufruf. 
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; 
} 

class Unsolvable {}; 
std::vector<size_t> wpc12(std::vector<bool> & state1, std::vector<bool> & state2); 

vector<bool> pressButton(size_t button,vector<bool> in){
	vector<bool> out=in;
	if(button-1>=0)
		out[button-1]=!out[button-1];
	out[button]=!out[button];
	if(button+1<out.size())
		out[button+1]=!out[button+1];
	return out;
}

ostream& operator<<(ostream& out,vector<bool> const& v){
	for(vector<bool>::const_iterator i=v.begin();i!=v.end();++i)
		cout<<*i;
	return out;
}

int main(){
	typedef vector<bool> State;
	queue<State> border;
	map<State,size_t> seen;
	State state=makeState("00000");
	border.push(state);
	seen[state]=1;
	while(!border.empty()){
		State current=border.front();
		border.pop();
		for(size_t i=0;i<current.size();++i){
			State next=pressButton(i,current);
			Sleep(1000);
			if(seen[next]==0){
				seen[next]=seen[current]+1;
				border.push(next);
			}
		}
	}
	for(map<State,size_t>::iterator i=seen.begin();i!=seen.end();++i)
		cout<<i->first<<' '<<i->second-1<<endl;
	cout<<seen.size()<<endl;
}

beachte vor allem mal den fall 10110 2!

Jester

hey, das ist doch schonmal gut.

Irgendwie krieg ich meine Lösung grad nicht zu laufen

evilissimo

volkard schrieb:

beachte vor allem mal den fall 10110 2!

Ja gerade das hat bei mir net funktioniert, jetzt tut es, aber könnte besser sein

bin grade mal bei O(n²)

Jester

Wenn man in volkards Lösung statt std::map<State, size_t> ne std::map<State, std::vector<size_t> > verwendet und sich den Weg da reinspeichert, dann hat man ne Lösung des kompletten Problems.

MfG Jester

na dann werd ich die mal abschicken

Jester

Hab das mal schnell reingabaut. Vielleicht kann's jemand brauchen
Ohne Gewähr.

#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <iostream>
using namespace std;

// Helper für leichten Aufruf. 
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; 
} 

class Unsolvable {}; 
std::vector<size_t> wpc12(std::vector<bool> & state1, std::vector<bool> & state2); 

vector<bool> pressButton(size_t button,vector<bool> in){
	vector<bool> out=in;
	if(button-1>=0)
		out[button-1]=!out[button-1];
	out[button]=!out[button];
	if(button+1<out.size())
		out[button+1]=!out[button+1];
	return out;
}

ostream& operator<<(ostream& out,vector<bool> const& v){
	for(vector<bool>::const_iterator i=v.begin();i!=v.end();++i)
		cout<<*i;
	return out;
}

int main(){
	typedef vector<bool> State;
	queue<State> border;

        map<State,size_t> seen;
	map<State, std::vector<size_t> > ways;
        State state=makeState("00000");
	border.push(state);
	seen[state]=1;
        ways.insert(state, std::vector<size_t>());
	while(!border.empty()){
		State current=border.front();
		border.pop();
		for(size_t i=0;i<current.size();++i){
			State next=pressButton(i,current);
			if(seen[next]==0){
				seen[next]=seen[current]+1;
				border.push(next);

                                // Weg abspeichern
                                ways[next]=ways[current];
                                ways[next].push_back(i);
			}
		}
	}
	for(map<State,size_t>::iterator i=seen.begin();i!=seen.end();++i)
		cout<<i->first<<' '<<i->second-1<<endl;
	cout<<seen.size()<<endl;
}

borg

na toll, da bastel ich mir ne schöne lösung und hier wird nebenbei eine gepostet die wahrscheinlich genau so schnell wie meine ist
können wir nicht zusätzlich auch noch die kleinste lösung kühren? meins ist viel kleiner

Jester

borg: Dir fällt sicher noch einiges ein wo man optimieren kann, oder?

Walli

Also ich hab auch mittlerweile was lauffähiges in das ich aber noch viel Arbeit stecken muss, bevor ich damit einen Blumentopf gewinnen kann. Naja, ist ja noch was Zeit...

volkard

borg schrieb:

na toll, da bastel ich mir ne schöne lösung und hier wird nebenbei eine gepostet die wahrscheinlich genau so schnell wie meine ist

sorry! ich war mir sicher, daß keiner sowas einschickt. aber ich hab jetzt mein posting editiert und was eingebaut, was das prog viel lahmer macht.

borg

öh naja, ganz so wars nicht gemeint ich denke meins ist schon ne ganze ecke schneller :p ist aber schwer einzuschätzen.
wie lange braucht ihr ca. für diese beiden?

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

[] lösung ist sofort da
[] paar sekunden
[] minuten
[] zu lange

Jester

wie lang brauchst Du?

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

WPC... geht weiter! -> wpc12