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

WPC... geht weiter! -> wpc12

  • J

    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;
}
    0
  • B

    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 👍

    0
  • J

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

    0
  • W

    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... 😉

    0
  • V

    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. 👍

    0
  • B

    ö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

    0
  • J

    wie lang brauchst Du?

    0
  • B

    ~5 sekunden

    lösung:
    0 5 6 9 11 12

    0
  • J

    Jo, die Lösung scheint korrekt zu sein, hab leider grad mein Programm nicht zur Hand.

    MfG Jester

    0
  • B

    schade, kann mal irgendwer anders sagen wie lange er dafür ca. braucht 😕

    0
  • J

    Komm doch ins IRC 🙂

    euIRCnet, #cpp

    0
  • B

    ich bin ein quakenet-junkie, ich glaub mein mirc kann keine 2 netze gleichzeitig 🤡

    0
  • V

    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.

    0
  • V

    borg schrieb:

    ich bin ein quakenet-junkie, ich glaub mein mirc kann keine 2 netze gleichzeitig 🤡

    doch, es kann.

    0
  • J

    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?

    0
  • M

    borg: Für einen einzigen Aufruf? 😮

    0
  • B

    Michael E. schrieb:

    borg: Für einen einzigen Aufruf? 😮

    ja, deswegen frag ich. mir kommts auch schrecklich lang vor 🤡

    0
  • M

    Dein Ding kann man doch sicher als Referenz missbrauchen, oder?

    [EDIT] Bei mir merk ich bei size() = 68 erst beim Faktor 10000 ne Verzögerung. Das ist die erste Version!

    0
  • ?

    darf man assembler verwenden?

    0
  • W

    thetrue schrieb:

    darf man assembler verwenden?

    Was würde es dir bringen? Wahrscheinlich nichts.

    0
Anmelden zum Antworten