WPC-Aufgabe (Programmierwettbewerb)

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

Herzlichen Glückwunsch evilissimo!!!!

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

So,wie jeder der sich mein programm mal angesehen hat vielleicht gesehen hat baut das programm einen BSP tree.Also im Prinzip einen Binaerbaum,wo eine linie in einem Knoten gespeichert wird und rechter und linker unterbaum nur linien enthalten die rechts/links von der linie liegen.Daher hat man im besten fall logarithmische kosten zum durchsuchen nach schnittpunkten.
Also halten wir fest eine Strecke teilt die Ebene in 2 Halbebene und die Trennlinie ist die durch die Strecke verlaufende Gerade. Strecken die diese Gerade schneiden werden geteilt und es wird ggf. als Schnittpunkt gezaehlt (je nachdem ob es auf der Strecke liegt oder nur auf der verlaengerten Gerade.
Soweit so gut,ein fundamentales Problem sind allerdings Strecken die auf ein und der selben Gerade liegen. Hier kann man nicht sagen ob sie in den rechten oder linken unterbaum eingefuegt werden muessen. Fuegt man sie in nur einen Unterbaum ein, kann es passieren, dass eine andere Strecke auf der anderen Seite liegt und trotzdem genau bis zur trennenden Gerade verlaeuft (diese also beruehrt). Das waere dann aber ein Schnittpunkt mit der Strecke die nun genau im falschen Unterbaum eingefuegt wurde,er wuerde also nicht gezaehlt. Fuegt man die problematische Strecke in beide Unterbaeume ein, so wird eine andere Strecke an der Gerade geteilt und fuehrt zu 2 schnittpunkten,also wieder falsch.

Meine erste Loesung war es diese boesen Strecken gar nicht einzufuegen,sondern in einen array zu packen und dann extra zu pruefen. Das ist zwar langsam,aber sollte ein extrem seltener Sonderfall sein. So nun aber ein Gegenbeispiel wo dies nicht korrekt ist: Folgende einfuegereihenfolge:
1. eine Senkrechte Strecke sagen wir (0,-1)-(0,1)
2. eine waagerechte (1,0)-(2,0)
3. eine waagerechte (-2,0)-(-1,0)
4. eine waagerechte (-0.5,0)-(0.5,0)
so was passiert also? nach 1-3. hat man einen Baum mit 1. in der wurzel und 2.,3. als rechtes/linkes kind. Nun soll 4 eingefuegt werden. 4 schneidet 1. wird also geteilt,nun soll (-0.5,0)-(0,0) und (0,0)-(0.5,0) in 3 bzw 4 eingefuegt werden,die liegen beide auf der jeweils trennenden Gerade,also werden beide als boese Linien gespeichert und nicht eingefuegt. Nun wird zum schluss deren Schnitt geprueft, jede der boesen linien schneidet 1. also 2 extra schnittpunkte,also werden 3 gezaehlt obwohl nur einer da ist!

behoben kann das werden indem man z.b. durch eine exception signalisiert das eine boese linie aufgetreten ist,und dann alle linien und schnittpunkte die durch sie entstanden sind wieder entfernt werden oder so,dafuer hatte ich aber keine zeit mehr...

wann kommt denn die nächste aufgabe? ich möchte euch mal so richtig an die wand proggen.

Jester

Gibt's denn noch mehr Interessenten?

Ponto

Jester schrieb:

Gibt's denn noch mehr Interessenten?

Immer.

Brutus

Jop.

lohnt sich aber nur wenn volkard auch mitmacht.

Aufgabe: Programmiert Doom 4 und schickt die fertigen Programme an...

Soll ich das jetzt schreiben oder ist das zu schlecht.

PeterTheMaster

interesse ja, zeit weiss nicht.

ich progge euch alle an die wand ey

Wie kann man jemand an die Wand proggen?

Geht das mit C oder muss ich C++ verwenden? Kann einer mal ein Beispiel für and die Wand proggen posten?

cout << hello wört

PeterTheMaster

sei x ein verb. der ausspruch "ich x'e dich an die wand!" heisst soviel wie "ich bilde mir ein, im x'en sehr viel besser zu sein als du.".
woher diese metapher allerdings kommt, ist mir gerade nicht ganz klar. gibt es in irgendeiner sportart eine wand?

setX("wx");
pronounceX(); // wichs

cu frau ulle

Ich hätte auch mal Lust mitzumachen

Beim Squash gibt es ne Wand.

Jäster schrieb:

Aufgabe: Programmiert Doom 4 und schickt die fertigen Programme an...

Soll ich das jetzt schreiben oder ist das zu schlecht.

Hier schonmal das Främework: (funzt aber noch nicht so ganz)

#include <iostream.h>

class doom4
{
    bool Load();
};

bool doom4::Load()
{
 //<-- hier Code einfügen
 return false;
}

void main(void)
{
    doom4 doom3;
    if(!doom3.Load()) cout<<"Could not load Doom4"<<endl;
    return;
}