WPC-Aufgabe (Programmierwettbewerb)

[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?

[Der Dumme]

Ist 0 das falsche Ergebnis?

[Gast]

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*

[Gast]

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.

[concretewall026c]

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.

[evilissimo]

Jester schrieb:

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

Ich sag ja net das mein algo richtig ist. Ich hab nur das erwähnt was auf Wikipedia zu dem Thema noch gesagt wird.

[Gast]

Jester schrieb:

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

Die Funktion dieser Linie bildet auf eine 2dimensionale Ebene ab und nimmt Parameter t. Eine allgemeine Kurve halt, in diesem Fall zweidimensional, wovon man ohne Probleme den Vektor der partiellen Ableitungen bilden kann.

Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?

edit: Wikipedia sagt: ja

Ich denke nicht, dass du das aus diesem Satz folgern kannst. Genausogut kann der Satz eine Gegenüberstellung von Schnitt- und Berührpunkt sein. Nimm dir mal ne Parabel x² und sieh dir die X-Achse an. Schneidet sie die Parabel? Ich würde sagen nein.

Jester schrieb:

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

Finde ich korrekt.

[Jester]

Optimizer schrieb:

Ich denke nicht, dass du das aus diesem Satz folgern kannst.

Da steht doch, was ein Schnittpunkt ist, nämlich ein gemeinsamer Punkt. Und ein Berührpunkt ist ein gemeinsamer Punkt der...

Ergo: Berührpunkt ist Schnittpunkt.

@Ableitung: Und ich kann Dir ohne Probleme zwei Parametrisierungen meiner Strecke mit unterschiedlichen Ableitungen angeben.
Was Du wahrscheinlich haben willst ist lineare Abhängigkeit des Gradienten... und nichtmal das ist hinreichend. Zusätzlich müßten wir noch Parametrisierungen ausschließen, deren Gradient 0 werden können. Aber sag, ist das nicht ein bißchen viel des Guten für so nen einachen Begriff?

Nach der einen Definition ist ein Berührpunkt ein Schnittpunkt, also geht das erste Beispiel schief. Nach der Definition aus der Diskussion ist ein Schnittpunkt ein Punkt in dem sich die Strecken kreuzen. Das tun sie im zweiten Beispiel aber nicht.

Ich kann doch nicht jedesmal Optimizer fragen, ob er das jetzt gerade als Schnittpunkt empfindet oder nicht.

[evilissimo]

Testest du es trotzdem noch ( aber dann nur mit kreuzenden Linien )?

BR

evilissimo

[Jester]

Ja, ich nehme die Endpunkte paarweise verschieden. Dann kann die Situation nicht auftreten. Ich hab mich die letzten Tage viel mit der Boardsuche auseinandergesetzt und bin daher nicht mit der Auswertung weitergekommen. Mal sehen, vielleicht setze ich mich nachher nochmal dran.

[Jester]

So, jetzt bin auch dazu gekommen, die zweite Aufgabe auszuwerten.

Eine Lösung muß leider ausgeschlossen werden.
Das Programm von Ness arbeitet fehlerhaft, bei diesem Beispiel wird kein Schnittpunkt erkannt:

Strecke1: (-21.8, -2.1) - (10.5956, -10.7854)
Strecke2: (-44.4, -35.5) - (21.6849, 18.6791)

Wer möchte kann sich mit folgendem Code die Situation in GNU Octave visualisieren. Es handelt sich auch nicht um einen Randfall oder sowas, wo man von numerischen Instabilitäten ausgehen könnte.

m1 = (-10.7854 - -2.1)/(10.5956 - -21.8)
m2 = (18.6791 - -35.5)/(21.6849 - -44.4)
c1 = -2.1 - m1*-21.8
c2 = -35.5 - m2*-44.4
t1 = linspace(-21.8, 10.5956,2)
t2 = linspace(-44.4, 21.6849,2)
y1 = c1+t1*m1
y2 = c2+t2*m2

plot(t1,y1)
hold on
plot(t2,y2)

Für den Geschwindigkeitstest habe ich folgenden Liniengenerator benutzt:

#include <set>
#include <cstdlib>
#include <cmath>
#include "wpc_pro.h"

class LineGenerator
{
public:
	std::vector<Line> getLines(size_t numLines)
	{
		alreadyUsedPoints.clear();
		std::vector<Line> lines;
		for(size_t i = 0; i < numLines; ++i)
		{
			lines.push_back(generateNewLine());
		}
		return lines;
	}
private:

	Line generateNewLine() {
		Point start = generateNewPoint();
		Point end = getNewEndPoint(start);
		return Line(start, end);
	}

	Point generateNewPoint()
	{
		Point p(0,0);
		do
		{
			p.x = getRandomValue();
			p.y = getRandomValue();
		} while(alreadyUsedPoints.find(p)!=alreadyUsedPoints.end());
		alreadyUsedPoints.insert(p);
		return p;
	}

	Point getNewEndPoint(const Point & p)
	{
		Point result(0,0);

		do
		{

			double angle = getRandomValue();

			double dx = sin(angle);
			double dy = cos(angle);

			double length = double(rand())/RAND_MAX;
			length = pow(length, 10);
			length *= 100;
			if(length < 0.2) length = 0.2;

			result.x = p.x+length*dx;
			result.y = p.y+length*dy;

		} while(alreadyUsedPoints.find(result)!=alreadyUsedPoints.end());
		alreadyUsedPoints.insert(result);

		return result;
	}

	double getRandomValue() {
		double value = std::rand();
		value /= RAND_MAX;
		value *= 1000;
		value -= 500;
		value = int(value);
		value /= 10;

		return value;

	}

	std::set<Point> alreadyUsedPoints;

};

Dieser lehnt doppelte Punkte ab. Das Prinzip ist folgendes: Es wird zunächst ein zufälliger Punkt gezogen. Anschließend ein Zufälliger Winkel und eine zufällige Länge. Die Strecke geht dann vom ersten Punkt in Richtung des Winkels soweit wie die Länge angibt. Die Länge ziehe ich als Zahl von 0 bis 1. Um kleine Längen stärker zu gewichten potenziere ich diese Länge danach mit Exponenten 10.

Die längste Strecke in den Testdaten hat zumeist eine Länge von 100, der Schnitt liegt bei etwa 10. Es gibt also deutlich mehr kurze Strecken als Lange.

Nach dem Geschwindigkeitstest ergibt sich folgendes Endergebnis:

1. Thomas001 time: 157.084s
2. Evilissimo time: 314.453s
3. Brutus time: 384.989s

Bei den Zeiten handelt es sich um die Gesamtzeit um folgendes Testprogramm zu absolvieren:

Der Code von Thomas001 geht bereits ab eine Eingabegröße von 100 in Führung und bleibt die gesamt Testlaufzeit über schneller als die anderen Einsendungen.

#include "wpc_pro.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "LineGenerator.h"
#include <utility>
#include <string>

using namespace std;

typedef unsigned long long u64;

u64 rdtsc() {
	__asm  { rdtsc }
}

namespace Thomas001
{
	size_t wpc_pro(std::vector<Line> const&);
}

namespace Ness
{
	size_t wpc_pro(std::vector<Line> const&);
}

namespace Evilissimo
{
	size_t wpc_pro(std::vector<Line> const&);
}

namespace Brutus
{
	size_t wpc_pro(std::vector<Line> const&);
}

typedef size_t (*wpc_pro_func)(std::vector<Line> const&);
std::vector<wpc_pro_func> functions;
std::vector<string> names;
std::vector<u64> times;

int main()
{

	double clockspeed = 2211e6;

	functions.push_back(Thomas001::wpc_pro);  names.push_back("Thomas001 "); times.push_back(0);
	//functions.push_back(Ness::wpc_pro);       names.push_back("Ness      "); times.push_back(0);
	functions.push_back(Evilissimo::wpc_pro); names.push_back("Evilissimo"); times.push_back(0);
	functions.push_back(Brutus::wpc_pro);     names.push_back("Brutus    "); times.push_back(0);

	srand(time(0));
	LineGenerator generator;

	size_t size = 100;
	while(size < 100000)
	{
		vector<Line> lines = generator.getLines(size);

		double length = 0.0;
		double minLength = lines[0].getLength();
		double maxLength = lines[0].getLength();

		for(vector<Line>::iterator it = lines.begin(); it != lines.end(); ++it)
		{
			double l = it->getLength();
			length += l;
			minLength = min(minLength, l);
			maxLength = max(maxLength, l);
		}

		cout << "\n\nSize: " << lines.size() << endl;
		cout << "minimal Length: " << minLength << endl;
		cout << "maximal Length: " << maxLength << endl;
		cout << "average Length: " << length/lines.size() << "\n" << endl;

		for(int i = 0; i< functions.size(); ++i)
		{
			u64 time = -rdtsc();
			size_t result = functions[i](lines);
			time += rdtsc();
			times[i] += time;
			cout << names[i] << " result: " << result << "\t time: " << time/clockspeed << "s" << endl;
		}

		size*=1.3;
	}

	cout << "Final result: " << endl;
	for(int i = 0; i< functions.size(); ++i)
	{
		cout << names[i] << "\t time: " << times[i]/clockspeed << "s" << endl;
	}

	cin.get();
	return 0;
}

Und hier noch der Siegercode:

#include "wpc_pro.h"
#include <vector>
#include <iostream>
#include <memory>
#include <algorithm>

namespace {
  bool intersect(const Line& l1,const Line& l2,Point& where)
  {
    const double C1=l1.getEnd().x-l1.getStart().x,
      C2=l2.getStart().x-l2.getEnd().x,
      C3=l2.getStart().x-l1.getStart().x,
      D1=l1.getEnd().y-l1.getStart().y,
      D2=l2.getStart().y-l2.getEnd().y,
      D3=l2.getStart().y-l1.getStart().y;

    const double det=C1*D2-C2*D1;
    if(det==0)
      return false;

    const double t1=(C3*D2-C2*D3)/det;
    const double t2=(C1*D3-C3*D1)/det;

    where=Point(C1*t1+l1.getStart().x,
		D1*t1+l1.getStart().y);

    return t1>=0 && t1<=1 && t2>=0 && t2<=1;
  }

  double distance(const Line& l,const Point p)
  {
    const double C1=l.getEnd().x-l.getStart().x,
      D1=l.getEnd().y-l.getStart().y;
    return ((p.x-l.getStart().x)*(-D1)+(p.y-l.getStart().y)*C1);
  }

  struct Node
  {
    Node* left;
    Node* right;
    const Line line;
    Node(const Line& l):left(0),right(0),line(l) { }
    size_t insert(const Line& l);
    size_t split_insert(const Line& l);
    size_t insert_right(const Line& l);
    size_t insert_left(const Line& l);
    ~Node() { delete left;delete right; }
  };

  size_t Node::split_insert(const Line& l)
  {
    Point where(0,0);
    size_t r=intersect(l,line,where);
    const double ds=distance(line,l.getStart()),de=distance(line,l.getEnd());
    if(ds>0)
      {
	r+=insert_right(Line(l.getStart(),where));
	if(de<0)
	  r+=insert_left(Line(where,l.getEnd()));
      }
    else if(ds<0)
      {
	r+=insert_left(Line(l.getStart(),where));
	if(de>0)
	  r+=insert_right(Line(where,l.getEnd()));
      }
    else if(de>0)
      r+=insert_right(Line(where,l.getEnd()));
    else if(de<0)
      r+=insert_left(Line(where,l.getEnd()));
    return r;
  }

  size_t Node::insert_right(const Line& l)
  {
    if(right)
      return right->insert(l);
    else
      {
	right=new Node(l);
	return 0;
      }
  }

  size_t Node::insert_left(const Line& l)
  {
    if(left)
      return left->insert(l);
    else
      {
	left=new Node(l);
	return 0;
      }
  }

  std::vector<Line> evil_lines;

  size_t Node::insert(const Line& l)
  {
    // use split_insert more often than neccessary to build the tree
    // to get all the intersections counted right
    const double ds=distance(line,l.getStart()),de=distance(line,l.getEnd());
    if(ds>0)
      if(de>0)
	return insert_right(l);
      else 
	return split_insert(l);
    else if(ds<0)
      if(de<0)
	return insert_left(l);
      else 
	return split_insert(l);
    else if(de!=0)
      return split_insert(l);
    else
      {
	evil_lines.push_back(l);
	return 0;
      }
  }
}

size_t wpc_pro(const std::vector<Line>& v)
{
  if(v.empty())
    return 0;

  evil_lines.clear();
  size_t r=0;
  std::auto_ptr<Node> tree(new Node(v.front()));
  for(std::vector<Line>::const_iterator i=v.begin()+1;i!=v.end();i++)
    r+=tree->insert(*i);

  // this is really slow, but will not happen ;)
  Point p(0,0);
  for(std::vector<Line>::iterator i=evil_lines.begin();i!=evil_lines.end();i++)
    for(std::vector<Line>::const_iterator j=v.begin();j!=v.end();j++)
      {
	// for good lines find() will always return end()
	// for evil lines find() will return end() if the line was
	// already checked, so it's safe to check intersection now, as
	// we won't get checked by this line ourself.
	if(std::find(i,evil_lines.end(),*j)==evil_lines.end())
	  r+=intersect(*i,*j,p);
      }
  return r;
}

Herzlichen Glückwunsch an den Sieger und alle anderen Teilnehmer!

zuguterletzt möchte ich mich nochmal für die lange Auswertungsdauer entschuldigen. Die Zeit war unangemessen lang, ich werde in Zukunft die Auswertung vor dem Stellen der Aufgabe besser vorbereiten. Ich hoffe, daß ihr trotzdem weiterhin Lust habt gelegentlich an einem WPC teilzunehmen.

MfG Jester

[verlierer]

Herzlichen Glückwunsch evilissimo!!!!

Schade das nur so wenig mitgemacht haben. Und das obwohl Weihnachten war.