WPC... geht weiter! -> wpc12

Jester wird wohl schlau genug sein und ne gute Aufgabe stellen.

dali

Morgen (Freitag, 3.3.05) geht's weiter mit Aufgabe 12!

Ähm Freitag ist der 4.3.05 (Oder meine Uhr stimmt nicht)

Jester

Ich hab mich zumindest redlich bemüht eine Aufgabe zu finden, die in ein paar (wenigen) Stunden lösbar ist.

Jester

Die Aufgabe ist jetzt da.

Walli

Sieht interessant aus . Hoffentlich finde ich im Laufe der Woche Zeit sie zu lösen.

Ich glaube du hast einen klitzekleinen Fehler in makeState... Sollte es nicht state[index]=='1' statt state[index]==1 heißen?

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

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

WPC... geht weiter! -> wpc12