WPC... geht weiter! -> wpc12

Jester

Hallo,

der WPC lebt!

Ich werde die Aufgabenstellung für den 12. WPC morgen abend 20:00 auf wpc.schornboeck.net posten. Die Abgabe ist dann am Freitag drauf wieder bis spätestens 20:00.

Ich würde mich über rege teilnahme freuen.

MfG Jester

-------------------------------------

WPC heißt: weekly programming contest

zu gewinnen gibt es: Anerkennung, Ruhm und Ehre, außerdem ne Menge Spaß!

Michael E.

Walli

Wenn die Aufgabe diesmal nicht zu umfangreich ist bin ich auch dabei, denke ich.

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

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

WPC... geht weiter! -> wpc12