WPC... geht weiter! -> wpc12
-
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!
-
hey, das ist doch schonmal gut.
Irgendwie krieg ich meine Lösung grad nicht zu laufen
-
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 seinbin grade mal bei O(n²)
-
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
-
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; }
-
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
-
borg: Dir fällt sicher noch einiges ein wo man optimieren kann, oder?
-
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...
-
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.
-
ö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
-
wie lang brauchst Du?
-
~5 sekunden
lösung:
0 5 6 9 11 12
-
Jo, die Lösung scheint korrekt zu sein, hab leider grad mein Programm nicht zur Hand.
MfG Jester
-
schade, kann mal irgendwer anders sagen wie lange er dafür ca. braucht
-
Komm doch ins IRC
euIRCnet, #cpp
-
ich bin ein quakenet-junkie, ich glaub mein mirc kann keine 2 netze gleichzeitig
-
borg schrieb:
~5 sekunden
ich mach's noch per hand. ~300 sekunden.
0 5 6 9 11 12
das ist ja gemein. ich kann deine lösung bestätigen, hab aber selber
1 3 4 5 7 10 11 13
raus. also gibt es tatsächlich mehrer lösungen für eine aufgabe und man muss echt dir kürzeste finden.
-
borg schrieb:
ich bin ein quakenet-junkie, ich glaub mein mirc kann keine 2 netze gleichzeitig
doch, es kann.
-
volkard schrieb:
0 5 6 9 11 12
das ist ja gemein. ich kann deine lösung bestätigen, hab aber selber
1 3 4 5 7 10 11 13
raus. also gibt es tatsächlich mehrer lösungen für eine aufgabe und man muss echt dir kürzeste finden.Hehe, hattest Du mir echt so viel Boshaftigkeit zugetraut?