WPC-Aufgabe (Programmierwettbewerb)

Brutus

Wann denkst du, bist du mit der Auswertung der anderen Aufgabe fertig?

Könntet ihr mal folgendes einbauen, damit man die Ergebnisse überprüfen kann.

class Verifier {
	struct SwapPair {
		size_t p1;
		size_t p2;
	};
	std::vector<SwapPair> swaps;
public:
	void add(size_t p1, size_t p2) {
		SwapPair sp;
		sp.p1 = p1;
		sp.p2 = p2;
		swaps.push_back(sp);
	}

	bool isOK(std::vector<unsigned int> const& weights, u64 calculatedSum) {
		u64 sum = 0;
		std::vector<unsigned int> sorted;
		sorted.resize(weights.size());
		for(size_t i=0;i<weights.size(); i++){
			sorted[i]=weights[i];
		}
		for(size_t s=0;s<swaps.size();s++) {
			unsigned int h = sorted[swaps[s].p1];
			sum+= h+sorted[swaps[s].p2];
			sorted[swaps[s].p1]=sorted[swaps[s].p2];
			sorted[swaps[s].p2]=h;
		}
		if(calculatedSum!=sum) {
			std::cout<<"Error: sum="<<sum<<" calculated="<<calculatedSum<<"\n";
			return false;
		}
		for(size_t t=0;t<sorted.size()-1;t++){
			std::cout<<sorted[t]<<" "<<sorted[t+1]<<" ";
			if(sorted[t]>sorted[t+1]) {
				std::cout<<"Error: pos ("<<t<<"/"<<t+1<<")\n";
				return false;
			}
		}
		return true;
	}
};

Einfach jedes Packetpaar, dass getauscht wird mit add(...) hinzufügen und am Schluss isOK mit der zu sortierenden Liste und dem berechnetem Ergebnis aufrufen.

Volkard ist und bleibt der Godfather of Coding

Glückwunsch.

Jester

Der angegebene Testcode läßt sich nicht gut einbauen, weil wir die Folgen nicht wirklich sortieren (ich zumindest nicht). Es werden nur die nötigen Kosten berechnet. Ich bin mir aber sehr sicher, daß die Implementierungen korrekt sind.

Für kleine Beispiele habe ich auch eine A*-Suche implementiert, die liefert die gleichen Ergebnisse. Allerdings ist sie zu Rechen- und Speicheraufwendig um richtige Beispiele damit durchzurechnen (ist auch etwas ungeschickt implementiert).

Es haben nur 3 Leute mitgemacht?

Jester

Bei der Experten-Aufgabe, ja. Bei der Linienaufgabe genauso.
Ursprünglich hatten sich noch mehr Leute daran versucht, aber nachdem wohl einige Algorithmen fehlerhaft waren haben sich manche entmutigen lassen. Schade eigentlich.

evilissimo

Hast du die Linien Aufgabe denn schon ausgewertet?

BR

Brutus

Nur 3 Leute bei der Linienaufgabe? Hat thomas001 nicht abgegeben? Oder hat ness nicht abgegeben?

Jester

Ups, sind 4 Einsendungen.
Auswertung dazu kommt auch bald.

Jester

Hm, was mach ich nun mit der Streckenaufgabe?

Point origin(0,0);
Point middle(1,1);
Point end(2,2);

Line line1(origin, middle);
Line line2(middle, end);

std::vector<Line> lines;
lines.push_back(line1);
lines.push_back(line2);

cout << wpc_pro(lines) << endl;

Da sind sich die Herren alle einig: 0 soll die Anzahl der Schnittpunkte sein.

Was nun?

Ist 0 das falsche Ergebnis?

Jester schrieb:

Hm, was mach ich nun mit der Streckenaufgabe?
Point origin(0,0);
Point middle(1,1);
Point end(2,2);

Line line1(origin, middle);
Line line2(middle, end);

std::vector<Line> lines;
lines.push_back(line1);
lines.push_back(line2);

cout << wpc_pro(lines) << endl;
Da sind sich die Herren alle einig: 0 soll die Anzahl der Schnittpunkte sein.

Was nun?

Is'n Berührpunkt.

Jester

imho ist das ein Schnittpunkt.
Damit ich aber trotzdem was tun habe werde ich alle Punkte paarweise verschieden wählen. Dadurch kann dieser Fall nicht auftreten.

evilissimo

Lustig :p

Ich bin froh das wir alle das gleiche ergebniss haben *g*

Laut Wikipedia ist es ein Berührpunkt, wenn die erste Ableitung identisch ist (also eine Funktion die andere tangiert). { (1, 0), (1, 1) } { (2, 1), (1, 1) } dürften sich demzufolge beispielsweise schneiden. Wenn die teilnehmenden Programme so etwas sehen, musst du keine paarweise verschiedenen Punkte nehmen.
In jedem Fall würde es mich aber interessieren, ob die Einsendungen so einen Fall erkennen würden.

Jester

Das erkennen sie vermutlich.

Wobei mir nicht klar ist, von welchem Ableitungsbegriff Du sprichst. Wenn ich die Linien senkrecht nach oben mache kannste den normalen Ableitungsbegriff nicht benutzen.

Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?

edit: Wikipedia sagt: ja

Wikipedia schrieb:

Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.

Wikipedia schrieb:

Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.

klingt logisch

evilissimo

http://de.wikipedia.org/wiki/Diskussion:Schnittpunkt

Wikipedia Diskussion schrieb:

Er bezeichnet einen Punkt, in dem sich zwei oder mehrere gerade oder gebogene Linien überkreuzen.

Eine tangentiale Berührung wird im Allgemeinen nicht als Schnittpunkt bezeichnet.

Die scheinen sich da aber auch nicht so sicher zu sein, so wie es aussieht ^^

Jester

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.