WPC-Aufgabe (Programmierwettbewerb)

Brutus

volkard schrieb:

wer macht eigentlich die streckenschneideaufgabe?

ich

Ach ja, ihr Sortieraufgabenlöser, gebt euch doch nicht alle gleich immer auf, ist volkard nicht eine "Motivation" für euch? Denkt halt nochmal scharf nach, irgendwie wird er auch auf seinen Algo. gekommen sein ;-). Wie ich das verstanden habe, besteht das Risiko, wenn er seine schnelle Lösung abgibt, dass die nicht unbedingt korrekt ist. Braucht ihr noch mehr Motivation?

evilissimo

volkard schrieb:

wer macht eigentlich die streckenschneideaufgabe?

Ich versuchs *duck*

Ponto

volkard schrieb:

Ponto schrieb:

Ich bin mir aber bei Sortieren + O(n) ziemlich sicher. Zum Beweis fehlt noch was Zeit zum nachdenken.

na, hoffen wir mal, daß du nicht recht hast. was machen wir, wenn du recht hast? wie soll man das noch messen? vielleicht hängen wir alle noch nen bäckerwitz in die kommentierung und im zweifelsfall gewinnt der beste bäckerwitz?

Wenn das mit O(n) stimmt, ist da nicht viel zu machen. Und die Sortierung schaue ich mir auf keinen Fall an.

Brutus schrieb:

Wie ich das verstanden habe, besteht das Risiko, wenn er seine schnelle Lösung abgibt, dass die nicht unbedingt korrekt ist. Braucht ihr noch mehr Motivation?

Ja. Ich sehe noch immer keine andere Möglichkeit, als alles durchzuprobieren und das mache ich nicht schneller als volkard.

volkard schrieb:

irgendwer schrieb:

Kann das jemand bestätigen
16628551

leider nicht.
ich hab 16628462.
ich hab aber auch 16628551 in meinem ersten versuch gehabt.

Danke, ich hab jetzt auch 16628462.

Noch ein bischen Bestätigung bitte.
Mit evilissimo's WeightListGenerator
SEED=10 ELEMS=100 : 1509278
SEED=10 ELEMS=300 : 5041260

SEED=12 ELEMS=200 : 3132883

SEED=31 ELEMS=200 : 3200808

SEED=1000 ELEMS=100 : 1628503
SEED=1000 ELEMS=300 : bleibt hängen (ich hoffe mal auf gleiche Gewichte)

volkard

SEED=10 ELEMS=100 : 1509278
ich hab 1509218

SEED=10 ELEMS=300 : 5041260
ich hab 5041108

SEED=12 ELEMS=200 : 3132883
ich hab auch 3132883

SEED=31 ELEMS=200 : 3200808
ich hab auch 3200808

SEED=1000 ELEMS=100 : 1628503
ich hab 1624809

SEED=1000 ELEMS=300 : bleibt hängen (ich hoffe mal auf gleiche Gewichte)
ich hab 4776964

Ponto

Hab da ganz andere Werte raus. Kann aber am Generator liegen. Benutze den der glibc? Was habt ihr genommen?

Ich hab mal einen PRNG vorgeschaltet:

class Prng
{
public:
   Prng(unsigned int seed);

   void init (unsigned int seed);
   unsigned int getuint();
private:
   unsigned int a[55];
   int index;
};

Prng::Prng(unsigned int seed)
{
   init(seed);
}

void Prng::init(unsigned int seed)
{
   a[0] = seed;
   for (index = 1; index != 55; ++index) {
      a[index] = a[index-1]*31 + 1;
   }
}

unsigned int Prng::getuint() {
   index = (index + 1) % 55;
   a[index] = a[(index + 23) % 55] + a[(index + 54) % 55];
   return a[index];
}

class WeightListGenerator 
 { 
   std::vector<unsigned> weight_list;   
   Prng prng;

 public: 
   WeightListGenerator( size_t elems , unsigned seed = unsigned(time(0))) 
   : weight_list(std::vector<unsigned int>(elems,0)),
     prng(seed)
   { 
      while(elems--) 
        weight_list[elems] = prng.getuint(); 
   }   
   std::vector<unsigned> const & GetList() const { return weight_list; } 
 };

Mit den folgenden Ergebnissen:

E: 100 S: 10   228544409808
E: 300 S: 10   682663452603
E: 200 S: 12   426704698914
E: 200 S: 31   436103580650
E: 100 S: 1000 193533809787
E: 300 S: 1000 615707704331

Geht dein Algo auch mit gleichen Gewichten?
Ich hab den Code so geändert

class WeightListGenerator 
{ 
typedef std::map<unsigned int, int,std::less<unsigned int> > WMAP;
  std::vector<unsigned> weight_list;   
  WMAP wmap;
public: 
  WeightListGenerator( size_t elems , unsigned seed = unsigned(time(0))) 
  : weight_list(std::vector<unsigned int>(elems,0)) 
  { 
     std::srand(seed);                         
	 //while(elems--) {
  //     weight_list[elems] = unsigned(rand()); 
	 //}
	 while(elems>0) {
		 unsigned int value = unsigned(rand()); 
		 if(wmap.find(value) == wmap.end()) {
			 weight_list[elems] = value;
			 wmap.insert(WMAP::value_type(value,0));
			 elems--;
		 } else {
			 std::cout<<"\nEQUAL\n";
		 }
	 }

  }   
  std::vector<unsigned> const & GetList() const { return weight_list; } 
};

Und er gibt mir bei SEED=1000 ELEMS=300 zweimal EQUAL aus, bleibt auch nicht mehr hängen.

Haben wir nicht immer die gleichen Zahlen?

Jetzt wirds lang, aber ich wills wissen.

//begin
	list.push_back(365);
	list.push_back(1216);
	list.push_back(5415);
	list.push_back(16704);
	list.push_back(24504);
	list.push_back(11254);
	list.push_back(24698);
	list.push_back(1702);
	list.push_back(23209);
	list.push_back(5629);
	list.push_back(23830);
	list.push_back(32505);
	list.push_back(19574);
	list.push_back(16513);
	list.push_back(11529);
	list.push_back(13026);
	list.push_back(3768);
	list.push_back(1031);
	list.push_back(22229);
	list.push_back(7851);
	list.push_back(15646);
	list.push_back(7121);
	list.push_back(15810);
	list.push_back(6470);
	list.push_back(4195);
	list.push_back(25857);
	list.push_back(29816);
	list.push_back(11409);
	list.push_back(25981);
	list.push_back(6401);
	list.push_back(7628);
	list.push_back(17112);
	list.push_back(17688);
	list.push_back(1825);
	list.push_back(20443);
	list.push_back(19867);
	list.push_back(32578);
	list.push_back(4482);
	list.push_back(11605);
	list.push_back(18834);
	list.push_back(12136);
	list.push_back(28980);
	list.push_back(10524);
	list.push_back(17391);
	list.push_back(15489);
	list.push_back(1435);
	list.push_back(10254);
	list.push_back(17635);
	list.push_back(10633);
	list.push_back(13079);
	list.push_back(29982);
	list.push_back(17251);
	list.push_back(18993);
	list.push_back(5347);
	list.push_back(15274);
	list.push_back(1580);
	list.push_back(12245);
	list.push_back(1598);
	list.push_back(31753);
	list.push_back(5637);
	list.push_back(25262);
	list.push_back(18121);
	list.push_back(11875);
	list.push_back(9540);
	list.push_back(15177);
	list.push_back(15921);
	list.push_back(1989);
	list.push_back(4243);
	list.push_back(28727);
	list.push_back(8973);
	list.push_back(5492);
	list.push_back(23796);
	list.push_back(11271);
	list.push_back(2314);
	list.push_back(8834);
	list.push_back(22275);
	list.push_back(16241);
	list.push_back(6725);
	list.push_back(7072);
	list.push_back(14203);
	list.push_back(17364);
	list.push_back(32760);
	list.push_back(25907);
	list.push_back(28924);
	list.push_back(16867);
	list.push_back(15961);
	list.push_back(22442);
	list.push_back(2828);
	list.push_back(12442);
	list.push_back(1983);
	list.push_back(22030);
	list.push_back(11867);
	list.push_back(24696);
	list.push_back(19207);
	list.push_back(13018);
	list.push_back(17995);
	list.push_back(9960);
	list.push_back(310);
	list.push_back(22286);
	list.push_back(23471);
	list.push_back(24064);
	list.push_back(32351);
	list.push_back(24447);
	list.push_back(3283);
	list.push_back(3181);
	list.push_back(18888);
	list.push_back(9329);
	list.push_back(18110);
	list.push_back(18862);
	list.push_back(16712);
	list.push_back(24423);
	list.push_back(9139);
	list.push_back(12929);
	list.push_back(3059);
	list.push_back(25402);
	list.push_back(4862);
	list.push_back(411);
	list.push_back(8186);
	list.push_back(6761);
	list.push_back(11757);
	list.push_back(8348);
	list.push_back(24524);
	list.push_back(16304);
	list.push_back(24092);
	list.push_back(17730);
	list.push_back(4737);
	list.push_back(1244);
	list.push_back(14581);
	list.push_back(28381);
	list.push_back(15225);
	list.push_back(7133);
	list.push_back(13432);
	list.push_back(22531);
	list.push_back(5440);
	list.push_back(22045);
	list.push_back(6456);
	list.push_back(12420);
	list.push_back(13237);
	list.push_back(19984);
	list.push_back(21926);
	list.push_back(13216);
	list.push_back(4460);
	list.push_back(20237);
	list.push_back(5778);
	list.push_back(28280);
	list.push_back(3152);
	list.push_back(28508);
	list.push_back(18671);
	list.push_back(19139);
	list.push_back(5517);
	list.push_back(4240);
	list.push_back(26839);
	list.push_back(12738);
	list.push_back(6317);
	list.push_back(14870);
	list.push_back(16847);
	list.push_back(23414);
	list.push_back(527);
	list.push_back(1099);
	list.push_back(7696);
	list.push_back(27714);
	list.push_back(30811);
	list.push_back(21621);
	list.push_back(20905);
	list.push_back(11640);
	list.push_back(18422);
	list.push_back(13866);
	list.push_back(7219);
	list.push_back(23323);
	list.push_back(648);
	list.push_back(31301);
	list.push_back(14768);
	list.push_back(30072);
	list.push_back(18999);
	list.push_back(4385);
	list.push_back(5282);
	list.push_back(19031);
	list.push_back(19904);
	list.push_back(26201);
	list.push_back(17090);
	list.push_back(20187);
	list.push_back(19142);
	list.push_back(10706);
	list.push_back(14836);
	list.push_back(20649);
	list.push_back(2666);
	list.push_back(10748);
	list.push_back(20859);
	list.push_back(16972);
	list.push_back(3099);
	list.push_back(9044);
	list.push_back(25449);
	list.push_back(9945);
	list.push_back(21167);
	list.push_back(10542);
	list.push_back(8794);
	list.push_back(24782);
	list.push_back(1971);
	list.push_back(2993);
	list.push_back(30562);
	list.push_back(26688);
	list.push_back(26880);
	list.push_back(24355);
	list.push_back(31812);
	list.push_back(11318);
	list.push_back(13455);
	list.push_back(2151);
	list.push_back(26085);
	list.push_back(9040);
	list.push_back(1679);
	list.push_back(29379);
	list.push_back(29440);
	list.push_back(20396);
	list.push_back(23988);
	list.push_back(21223);
	list.push_back(13082);
	list.push_back(14857);
	list.push_back(14801);
	list.push_back(6955);
	list.push_back(14777);
	list.push_back(10285);
	list.push_back(2217);
	list.push_back(1305);
	list.push_back(4561);
	list.push_back(4741);
	list.push_back(21763);
	list.push_back(21547);
	list.push_back(1407);
	list.push_back(7436);
	list.push_back(27644);
	list.push_back(13781);
	list.push_back(3577);
	list.push_back(5997);
	list.push_back(27809);
	list.push_back(25286);
	list.push_back(32710);
	list.push_back(18540);
	list.push_back(30141);
	list.push_back(25964);
	list.push_back(18218);
	list.push_back(2178);
	list.push_back(26096);
	list.push_back(10678);
	list.push_back(18661);
	list.push_back(28615);
	list.push_back(25089);
	list.push_back(14877);
	list.push_back(15133);
	list.push_back(6934);
	list.push_back(5493);
	list.push_back(19941);
	list.push_back(2712);
	list.push_back(19563);
	list.push_back(24929);
	list.push_back(3232);
	list.push_back(8238);
	list.push_back(27279);
	list.push_back(28028);
	list.push_back(10997);
	list.push_back(6782);
	list.push_back(9208);
	list.push_back(20344);
	list.push_back(17567);
	list.push_back(20449);
	list.push_back(14570);
	list.push_back(15507);
	list.push_back(6072);
	list.push_back(11420);
	list.push_back(12515);
	list.push_back(31081);
	list.push_back(1336);
	list.push_back(16730);
	list.push_back(32566);
	list.push_back(31756);
	list.push_back(31417);
	list.push_back(5593);
	list.push_back(23286);
	list.push_back(29782);
	list.push_back(10621);
	list.push_back(5091);
	list.push_back(19989);
	list.push_back(11902);
	list.push_back(11953);
	list.push_back(7808);
	list.push_back(16333);
	list.push_back(1002);
	list.push_back(4339);
	list.push_back(10602);
	list.push_back(32319);
	list.push_back(20036);
	list.push_back(14099);
	list.push_back(25793);
	list.push_back(2907);
	list.push_back(4304);
	list.push_back(15382);
	list.push_back(20736);
	list.push_back(12543);
	list.push_back(19453);
	list.push_back(17537);
	list.push_back(20272);
	list.push_back(8291);
	list.push_back(12090);
	list.push_back(14548);
	list.push_back(347);
	list.push_back(8372);
	list.push_back(7434);
	list.push_back(2388);
	list.push_back(3908);
	list.push_back(4351);
	list.push_back(13659);
	list.push_back(24333);
	list.push_back(9045);
	list.push_back(16721);
	list.push_back(23060);
	list.push_back(24088);
	list.push_back(13273);
	list.push_back(26397);
	list.push_back(25069);
	list.push_back(23834);
	list.push_back(27755);
	list.push_back(12509);
	list.push_back(28035);
	list.push_back(13837);
	list.push_back(19374);
	list.push_back(15612);
	list.push_back(4780);
	list.push_back(5187);
	list.push_back(18751);
	list.push_back(30708);
	list.push_back(20999);
	list.push_back(25511);
	list.push_back(6120);
	list.push_back(9652);
	list.push_back(2776);
	list.push_back(17735);
	list.push_back(22551);
	list.push_back(6724);
	list.push_back(24851);
	list.push_back(11535);
	list.push_back(20110);
	list.push_back(26027);
	list.push_back(18871);
	list.push_back(3287);
	list.push_back(29531);
	list.push_back(30481);
	list.push_back(12637);
	list.push_back(12449);
	list.push_back(27915);
	list.push_back(31521);
	list.push_back(28945);
	list.push_back(12315);
	list.push_back(19483);
	list.push_back(31153);
	list.push_back(1376);
	list.push_back(6508);
	list.push_back(6831);
	list.push_back(30373);
	list.push_back(15282);
	list.push_back(14636);
	list.push_back(5254);
	list.push_back(6672);
	list.push_back(18907);
	list.push_back(9140);
	list.push_back(6958);
	list.push_back(9117);
	list.push_back(1004);
	list.push_back(25497);
	list.push_back(14964);
	list.push_back(11566);
	list.push_back(9295);
	list.push_back(29043);
	list.push_back(20767);
	list.push_back(194);
	list.push_back(23059);
	list.push_back(22755);
	list.push_back(12766);
	list.push_back(1436);
	list.push_back(4484);
	list.push_back(11988);
	list.push_back(20606);
	list.push_back(2210);
	list.push_back(11007);
	list.push_back(15616);
	list.push_back(20320);
	list.push_back(25603);
	list.push_back(5124);
	list.push_back(1718);
	list.push_back(299);
	list.push_back(18972);
	list.push_back(30349);
	list.push_back(2779);
	list.push_back(12990);
	list.push_back(14237);
	list.push_back(29342);
	list.push_back(26416);
	list.push_back(20841);
	list.push_back(20711);
	list.push_back(5662);
	list.push_back(16594);
	list.push_back(16732);
	//end

Ergebnis: 6213835

Zuviel rumgefrickelt
Mit dem neuen Algo ist das Ergebnis 6149750

Brutus

Hat jemand 'ne große Vergleichsliste für die Schnittpunktaufgabe? Ne 30er, am besten 50er oder am allerbesten ne 100er wäre ganz hilfreich, dann könnten wir auch mal vergleichen.

Hehe, ich glaub, ich hab nen Algo gefunden (meinen alten konnt ich ja jetzt in die Tonne treten ), muss ich zu Hause mal ausprobieren.

irgendwer schrieb:

Zuviel rumgefrickelt
Mit dem neuen Algo ist das Ergebnis 6149750

hm, ich komme auf 6149588

Michael E.

Hehe, Algo mit O(n) Komm aber heut nicht mehr nach Hause

evilissimo

Und hier noch etwas für WPC_Pro:

#include <limits>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>

static const double max_int = std::numeric_limits<int>::max();

#include <windows.h>

#pragma once

struct Point
{
  Point(double xc, double yc) : x(xc), y(yc) {}
  double x, y;
};

class Line
{
public:
  Line(Point const& startPoint, Point const& endPoint) : start(startPoint), end(endPoint)
  {}
  Point const& getStart() const { return start; }
  Point const& getEnd()   const { return end;   }

private:
  Point start, end;
};

size_t wpc_pro(std::vector<Line> const& lines);

class WPCProHelper
{
    enum
    {
        minLength = 20,
	    maxLength = 100,
        windowWidth = 640,
    	windowHeight = 480
    };
public:
    WPCProHelper()
    {
        __int64 s = get_rdtsc();
        Sleep(1000);
        __int64 e = get_rdtsc();   
        computer_speed = (e - s) / 1000;
    }
    size_t execute( int num , unsigned seed )
    {
        std::vector<Line> vec = generateLines(num,seed);
        startMessure();
        size_t erg = wpc_pro(vec);    
        endMessure();            
        return erg;
    }
    __int64 getDuration()
    {
        return (( end_ticks - start_ticks ) / computer_speed);
    }
private:
    __int64 computer_speed;
    __int64 start_ticks;
    __int64 end_ticks;    
private:
    void startMessure()
    {
        start_ticks = get_rdtsc();
    }
    void endMessure()
    {
        end_ticks = get_rdtsc();
    }
    bool invalidPoint(Point const& p) 
    {
	    return (p.x <= 0 || p.y <= 0 || p.x >= windowWidth || p.y >= windowHeight);
    }
    __int64 get_rdtsc()
    {
       __asm rdtsc
    }
    inline std::vector<Line> generateLines( int numLines , unsigned seed = unsigned(time(0))) 
    {
        using namespace std;
        srand(seed);
        std::vector<Line> target;
	    for(int i = 0; i < numLines; ++i) {
		    Point start(0, 0), end(0, 0);
		    double length, phi;

		    start.x = random01() * windowWidth;
		    start.y = random01() * windowHeight;

		    do {
			    length = random01() * (maxLength - minLength) + minLength;
			    phi = random01() * 2 * 3.14;

			    end.x = start.x + length * cos(phi);
			    end.y = start.y + length * sin(phi);
		    } while(invalidPoint(end));

		    target.push_back(Line(start, end));
	    }
        return target;
    }
    double random01() 
    {
        return double(rand()/max_int);
    }
};

#include "WPCProHelper.h"
#include <iostream>

int main()
{
    WPCProHelper h;
    size_t erg = h.execute(10000,333);
    std::cout << erg << "\t" << h.getDuration() << std::endl;
}

Mein ergebnis für die verwendete Einstellung ( seed = 333 / linien = 10000 )

4052812 Schnittpunkte

Mein AMD Athlon XP 2600+ mit 1024 MB RAM braucht dafür ca. 2.9 Sekunden

Ich hab den Code mit dem VC8 als Release compiliert mit eingeschalteten Optimierungen.

Da mein Algorithmus noch O(n^2) ist lässt sich da bestimmt noch was drehen. Mal schauen ob mir noch ne Idee kommt

BR
evilissimo

PS: Ich bitte um eine Anpassung des obigen Codes für vergleichbare tests, muss aber dazu sagen das die Generierung der Linien mit Prng mir persönlich viel zu lange dauert. *g* Vielleicht kann das ja jemand mal anpassen ( Vorallem eine evtl portablere Version beitragen )

Ponto

evilissimo schrieb:

Da mein Algorithmus noch O(n^2) ist lässt sich da bestimmt noch was drehen. Mal schauen ob mir noch ne Idee kommt

Viel besser kann es nicht gehen, da im Worst Case O(n^2) Schnittpunkte exisitieren.

evilissimo

du meinst wohl eher 2 * n

gib mir mal ein beispiel für n^2 falls du eins hast, wäre interessant.

BR
evilissimo

Jester

schau Dir mal ein kariertes Blatt Papier an.

volkard

Ponto schrieb:

Viel besser kann es nicht gehen, da im Worst Case O(n^2) Schnittpunkte exisitieren.

das stimmt.
aber jester hat extra angeküdigt, daß viele kurze srecken dabei sind. da könnte doch was unterquadratisches gehen.

evilissimo

Jester schrieb:

schau Dir mal ein kariertes Blatt Papier an.

naja ein Kariertes Blatt hat glaub ich dann n * ( n / 4 ) Schnittpunkte.