Eine Woche Programmierwettbewerb: Rechtecke

TomasRiker

Der alte Thread ist leider kaputt gegangen (letzte Seite geht nicht):
http://www.c-plusplus.net/forum/viewtopic-var-t-is-181382.html

@Ponto:
Könntest du bitte deinen letzten Beitrag nochmal schreiben? Ich hoffe mal, dass die Auswertung diesmal geklappt hat

Kann mal jemand den alten Beitrag ficksen?

phpBB ist schon eine tolle Software.

Als Markus das Forum aufgesetzt hat, hat er wohl nie mit mehr als 10 Postings/Tag gerechnet...

rüdiger

Wir kümmern uns drum. Ich hab versucht einige Beiträge zu entfernen. Aber das hat bisher nicht geholfen. Macht so lange bitte hier weiter.

finix

TomasRiker schrieb:

Der alte Thread ist leider kaputt gegangen (letzte Seite geht nicht):
http://www.c-plusplus.net/forum/viewtopic-var-t-is-181382.html

@Ponto:
Könntest du bitte deinen letzten Beitrag nochmal schreiben? Ich hoffe mal, dass die Auswertung diesmal geklappt hat

Mit http://www.c-plusplus.net/forum/viewtopic-var-t-is-181382-and-start-is-139.html kommst du an die Auswertung.

Ich kenne ein Forum, das mal mit dem gleichen Problem zu kämpfen hatte.

Laut Admin hat die Wiederinstandsetzung ziemliche Mühe gekostet.
Also viel Glück.

TomasRiker

Cool

Hier ist mein Algorithmus:
http://rafb.net/p/fso6kK79.html

Die Kommentare sollten keine Fragen offen lassen.

Ponto

Hier kommt nochmal meine Auswertung:

Es gab vier Einsendungen: otze, Jens, camper und TomasRiker

Jens hatte zwei Algorithmen abgegeben, die ich beide getestet habe, weil noch genug Kapazität da war.
Da aber jeder nur einen Algorithmus in den Contest schicken kann, gilt nur der, der hier als Jens-1 bezeichnet ist. Der andere läuft außer Konkurrenz.

Ebenso wird mein Algorithmus nicht berücksichtigt, der hier als Ponto bezeichnet wird. Zusätzlich taucht in den Tabellen noch der Algorithmus "TomasRiker Mod" auf. Diesen habe ich aufgenommen, weil TomasRiker in seiner Originallösung die Generatoren stark berücksichtigt.

Insgesamt tauchen hier also 7 Algorithmen auf.

Ich habe die Generatoren mit verschiedenen Parametern gefüttert und die Laufzeiten der Algorithmen aufsummiert. Damit denke ich den Algorithmus zu erhalten, der über einen breiten Anwendungsbereich am besten arbeitet.

Die Tests liefen auf einer Maschine mit 8 Prozessoren von AMD: "AMD Opteron(tm) Processor 852". Die Taktrate ist 2.6GHz. Die Testmaschine hat 64GB Hauptspeicher, welcher von keinem Programm ausgenutzt wurde.
Für jeden Test habe ich den Programmen 120 Sekunden CPU-Zeit gegeben. Testläufe, die länger benötigten wurden mit 130 Sekunden bewertet. Für die anderne Läufe gelten die tatsächlichen Sekunden.

Hier die Laufzeiten in Sekunden:

User:     camper  Jens-1  Jens-2   otze  TomasRiker  TomasRiker  Ponto 
                                                         Mod 
 Dot:          86     783    2194   2507          38          42     61 
 Wiring:     1104    2392    1965   2686         114         924    757 
 Placement   1708    3566    5711   6906         255         516    986 
 Random:     2248    5107     884   5331          28        1472    771 
            -----   -----   -----  -----       -----       -----  ----- 
 Gesamt:     5146   11848   10754  17430         435        2954   2574

Damit ergibt sich die folgende Reihenfolge:

4. otze
3. Jens
2. camper
1. TomasRiker

Man sieht, dass TomasRiker auch ohne seine Optimierung auf die Generatoren hin gewonnen hätte.

Herzlichen Glückwunsch an den Gewinner.

Alle Testläufe sind in der folgenden Tabelle eingetragen: http://www.pontohonk.de/wpc/Contest.ods

Die Rohdaten sind in http://www.pontohonk.de/wpc/Contest.txt zu finden. Die Laufzeitspalten sind sortiert nach camper, Jens-1, Jens-2, otze, TomasRiker Mod, Ponto, TomasRiker, Ponto (mit TomasRiker optimierungen)

Ponto

Hier ist mein eigener Code:

Grob gesagt, wird hier ein Quadtree aufgebaut, der an jedem Knoten abspeichert, ob dieser und die gesamte
Fläche darunter schon belegt sind.

Der erste Knoten (layer0[0]) repräsentiert die gesamte Ebene. In jedem weiteren Layer werden die darüberliegenden Flächen in vier gleich große Quadrate aufgeteilt.

Der Algorithmus läuft dann rekursiv. Es wird das Rechteck in das kleinste Quadrat gelegt, in das das Rechteck passt. Dann wird Anhand der Viertelung aufgeschnitten und die nächste Ebene aufgerufen. Ist eine Ebene schon belegt, kann abgebrochen werden.

#include <cmath> 
 #include <vector> 

 #include "rectangle.hpp" 

 char layerC[4096*4096/8]; 
 char layerB[2048*2048/8]; 
 char layerA[1024*1024/8]; 
 char layer9[512*512/8]; 
 char layer8[256*256/8]; 
 char layer7[128*128/8]; 
 char layer6[64*64/8]; 
 char layer5[32*32/8]; 
 char layer4[16*16/8]; 
 char layer3[8*8/8]; 
 char layer2[4*4/8]; 
 char layer1[1]; 
 char layer0[1]; 

 char * layer[] = { layer0, layer1, layer2, layer3, layer4, layer5, layer6, 
                    layer7, layer8, layer9, layerA, layerB, layerC }; 

 inline bool get(int l, int x, int y) { 
    unsigned int pos = (x * (1 << l) + y); 
    unsigned int byte = pos / 8; 
    unsigned int bit = pos % 8; 
    return (layer[l][byte]) & (1 << bit); 
 } 

 inline void set(int l, int x, int y) { 
    unsigned int pos = (x * (1 << l) + y); 
    unsigned int byte = pos / 8; 
    unsigned int bit = pos % 8; 
    layer[l][byte] |= (1 << bit); 
 } 

 static int pixel = 0; 

 static std::vector<std::vector<std::size_t> > * res; 

 inline unsigned int floor_log2_p1(unsigned int v) 
 { 
    if (v <= 2) return v; 

    unsigned int b = 17U; 
    if (v <   1U<<16U)       b  = 1U; 
    if (v >= (1U<< 7U) << b) b += 8U; 
    if (v >= (1U<< 3U) << b) b += 4U; 
    if (v >= (1U<< 1U) << b) b += 2U; 
    return(b + (v >= (1U<<0U) << b)); 
 } 

 inline void draw(int l, int x, int y, int minx, int maxx, int miny, int maxy, std::size_t idx) { 
    if (minx >= maxx or miny >= maxy) return; 
    if (get(l, x, y)) return; 

    int size = (4096U >> l); 

    if (size == 1) { 
       ++pixel; 
       set(l, x, y); 
       (*res)[x][y] = idx; 
       return; 
    } 

    int half = size/2; 

    int startx = x * size; 
    int midx = startx + half; 
    int starty = y * size; 
    int midy = starty + half; 

    draw(l+1, 2*x,   2*y,   minx, std::min(maxx, midx), miny, std::min(maxy, midy), idx); 
    draw(l+1, 2*x+1, 2*y,   std::max(minx, midx), maxx, miny, std::min(maxy, midy), idx); 
    draw(l+1, 2*x,   2*y+1, minx, std::min(maxx, midx), std::max(miny, midy), maxy, idx); 
    draw(l+1, 2*x+1, 2*y+1, std::max(minx, midx), maxx, std::max(miny, midy), maxy, idx); 

    if (get(l+1, 2*x, 2*y) and get(l+1, 2*x+1, 2*y) and get(l+1, 2*x, 2*y+1) and get(l+1, 2*x+1, 2*y+1)) { 
       set(l, x, y); 
       return; 
    } 
 } 

 void algorithm(Rectangle plane, 
                std::vector<Rectangle> const & rectangles, 
                std::vector<std::vector<std::size_t> > & result) 
 { 
    res = &result; 

    Coordinate width  = plane.maxx - plane.minx; 
    Coordinate height = plane.maxy - plane.miny; 

    for (std::size_t i = rectangles.size(); i > 0; --i) { 

       Rectangle rect = {rectangles[i-1].minx - plane.minx, 
                         rectangles[i-1].maxx - plane.minx, 
                         rectangles[i-1].miny - plane.miny, 
                         rectangles[i-1].maxy - plane.miny }; 

       rect.minx = std::max(Coordinate(0), rect.minx); 
       rect.miny = std::max(Coordinate(0), rect.miny); 

       rect.maxx = std::min(width, rect.maxx); 
       rect.maxy = std::min(height, rect.maxy); 

       if (rect.minx >= rect.maxx or rect.miny >= rect.maxy) continue; 

       int layer = floor_log2_p1(std::max(((rect.maxy-1) ^ rect.miny), ((rect.maxx-1) ^ rect.minx))); 

       draw(12 - layer, (rect.minx >> layer) , (rect.miny >> layer), 
            rect.minx, rect.maxx, rect.miny, rect.maxy, i-1); 
       if (pixel == width * height) break; 
    } 
 }

Ponto

Otze hat mich gebeten seinen Code auch zu veröffentlichen.
Jens und Camper können dies bei Bedarf selbst tun.

#include <list>
#include <utility>
#include <cmath>

#include <boost/optional.hpp>
#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH

#define BOOST_NO_MT
#include <boost/pool/pool_alloc.hpp>

#include <iostream>
struct Cross
{
    int middleX;
    int middleY;
};

enum Quadrant
{
    rightTop=0,
    leftTop=1,
    rightDown=2,
    leftDown=3,
    several
};

struct TreeRectangle
{
    Rectangle rect;
    std::size_t number;
    Quadrant quadrant;
};

typedef std::list<TreeRectangle,boost::fast_pool_allocator<TreeRectangle> > Container;
//typedef std::list<TreeRectangle> Container;
typedef Container::iterator iterator;

///////////////////////////////////////////////////////////////////////////////
//RECTANGLE
///////////////////////////////////////////////////////////////////////////////
Rectangle makeRectangle(int minx,int maxx,int miny,int maxy)
{
    Rectangle rect;
    rect.minx=minx;
    rect.maxx=maxx;
    rect.miny=miny;
    rect.maxy=maxy;
    return rect;
}
std::pair<Rectangle,boost::optional<Rectangle> >
cutHorizontal(const Rectangle& rectangle,int lineY)
{
    std::pair<Rectangle,boost::optional<Rectangle> > result;

    //no conversion needed,simply copy
    if((rectangle.maxy<=lineY)||(rectangle.miny>=lineY))
    {
        result.first=rectangle;
    }
    else
    {
        result.first=makeRectangle(rectangle.minx,rectangle.maxx,rectangle.miny,lineY);
        result.second=boost::optional<Rectangle>(makeRectangle(rectangle.minx,rectangle.maxx,lineY,rectangle.maxy));
    }
    return result;
}
std::pair<Rectangle,boost::optional<Rectangle> >
cutVertical(const Rectangle& rectangle,int lineX)
{
    std::pair<Rectangle,boost::optional<Rectangle> > result;

    //no conversion needed,simply copy
    if((rectangle.maxx<=lineX)||(rectangle.minx>=lineX))
    {
        result.first=rectangle;
    }
    else
    {
        result.first=makeRectangle(rectangle.minx,lineX,rectangle.miny,rectangle.maxy);
        result.second=boost::optional<Rectangle>(makeRectangle(lineX,rectangle.maxx,rectangle.miny,rectangle.maxy));
    }
    return result;
}
std::list<Rectangle> cutRectangle(const Rectangle& rectangle,const Cross& cross)
{
    std::list<Rectangle> result;
    std::pair<Rectangle,boost::optional<Rectangle> > hCut=cutHorizontal(rectangle,cross.middleY);

    std::pair<Rectangle,boost::optional<Rectangle> > vCut=cutVertical(hCut.first,cross.middleX);
    result.push_back(vCut.first);
    if(vCut.second)
    {
        result.push_back(vCut.second.get());
    }

    if(hCut.second)
    {
        std::pair<Rectangle,boost::optional<Rectangle> > vCut=cutVertical(hCut.second.get(),cross.middleX);
        result.push_back(vCut.first);
        if(vCut.second)
        {
            result.push_back(vCut.second.get());
        }
    }
    return result;
}
////////////////////////////////////////////////////////////////////////////////
//QUADRANT
////////////////////////////////////////////////////////////////////////////////
Quadrant getQuadrant(const Rectangle& rectangle,const Cross& cross)
{
    if( (rectangle.maxx<=cross.middleX) && (rectangle.maxy<=cross.middleY) )
    {
        return leftDown;
    }
    if( (rectangle.maxx<=cross.middleX) && (rectangle.miny>=cross.middleY) )
    {
        return leftTop;
    }
    if( (rectangle.minx>=cross.middleX) && (rectangle.maxy<=cross.middleY) )
    {
        return rightDown;
    }
    if( (rectangle.minx>=cross.middleX) && (rectangle.miny>=cross.middleY) )
    {
        return rightTop;
    }
    return several;
}

Rectangle getQuadrantOfRectangle(const Rectangle& plane,Quadrant quadrant)
{
    int middleX=(plane.maxx-plane.minx)/2+plane.minx;
    int middleY=(plane.maxy-plane.miny)/2+plane.miny;
    switch(quadrant)
    {
        case rightTop:
            return makeRectangle(middleX,plane.maxx,middleY,plane.maxy);
        break;
        case leftTop:
            return makeRectangle(plane.minx,middleX,middleY,plane.maxy);
        break;
        case rightDown:
            return makeRectangle(middleX,plane.maxx,plane.miny,middleY);
        break;
        case leftDown:
            return makeRectangle(plane.minx,middleX,plane.miny,middleY);
        break;
        default:
            return Rectangle();//just making the compiler happy
    }
}
////////////////////////////////////////////////////////////////////////////////
//TREE RECTANGLE
////////////////////////////////////////////////////////////////////////////////

TreeRectangle transformRectangle(const Rectangle& plane,const Rectangle& rectangle,std::size_t number)
{
    TreeRectangle rect;
    rect.rect.minx=std::max(rectangle.minx,plane.minx);
    rect.rect.miny=std::max(rectangle.miny,plane.miny);
    rect.rect.maxx=std::min(rectangle.maxx,plane.maxx);
    rect.rect.maxy=std::min(rectangle.maxy,plane.maxy);
    rect.number=number;
    return rect;
}
TreeRectangle transformRectangleSimple(const Rectangle& rectangle,std::size_t number)
{
    TreeRectangle rect;
    rect.rect=rectangle;
    rect.number=number;
    return rect;
}
bool operator<(const TreeRectangle& o1,const TreeRectangle& o2)
{
    return o1.number>o2.number;
}

void classifyRectangle(TreeRectangle& rectangle,const Cross cross)
{
    rectangle.quadrant=getQuadrant(rectangle.rect,cross);
}

////////////////////////////////////////////////////////////////////////////////
//ALGORITHM
////////////////////////////////////////////////////////////////////////////////

bool isInvisible(const TreeRectangle& lower,const TreeRectangle& upper)
{
    return (lower.rect.minx>=upper.rect.minx)
        && (lower.rect.maxx<=upper.rect.maxx)
        && (lower.rect.miny>=upper.rect.miny)
        && (lower.rect.maxy<=upper.rect.maxy);
}

//ok, i really hate myself for this function...
void cullInvisibleRectangles(Container& rectList)
{
    for(iterator i=rectList.begin();i!=rectList.end();++i)
    {
        iterator j=i;
        j++;
        while(j!=rectList.end())
        {
            if(isInvisible(*j,*i))
            {
                j=rectList.erase(j);
            }
            else
            {
                j++;
            }
        }
    }
}

void createVisibilityList(Rectangle plane,Container& rectangles)
{

    if(rectangles.empty()||rectangles.size()==1)
    {
        return;
    }
    //the cross splits the ground Plane in 4 parts
    Cross cross;
    cross.middleX=(plane.maxx-plane.minx)/2+plane.minx;
    cross.middleY=(plane.maxy-plane.miny)/2+plane.miny;

    Container quadrants[4];
    for(iterator rect=rectangles.begin();rect!=rectangles.end();)
    {
        classifyRectangle(*rect,cross);
        if(rect->quadrant==several)
        {
            std::list<Rectangle> newRectangles=cutRectangle(rect->rect,cross);
            foreach(Rectangle& newRect,newRectangles)
            {
                TreeRectangle newTransformedRect=transformRectangle(plane,newRect,rect->number);

                classifyRectangle(newTransformedRect,cross);
                quadrants[newTransformedRect.quadrant].push_back(newTransformedRect);
            }
            rect=rectangles.erase(rect);
        }
        else
        {
            iterator copy=rect;
            ++copy;
            //quadrants[rect->quadrant].push_back(*rect);
            quadrants[rect->quadrant].splice(quadrants[rect->quadrant].end(),rectangles,rect);
            rect=copy;
        }
    }

    for(std::size_t i=0;i!=4;++i)
    {
        Rectangle newPlane=getQuadrantOfRectangle(plane,Quadrant(i));
        cullInvisibleRectangles(quadrants[i]);
        createVisibilityList(newPlane,quadrants[i]);
        rectangles.splice(rectangles.begin(),quadrants[i],quadrants[i].begin(),quadrants[i].end());
    }
}

void algorithm(Rectangle plane, std::vector<Rectangle> const & rectangles, std::vector<std::vector<std::size_t> > & result)
{
    //transform the rects into a better format
    Container transformedRectangles;
    std::size_t i=0;
    std::vector<Rectangle>::const_reverse_iterator end=rectangles.rend();

    for(std::vector<Rectangle>::const_reverse_iterator rect=rectangles.rbegin();rect!=end;++rect)
    {
        if((rect->maxx>plane.minx) && (rect->minx<plane.maxx)
        && (rect->maxy>plane.miny) && (rect->miny<plane.maxy) )
        {
            transformedRectangles.push_back(transformRectangle(plane,*rect,rectangles.size()-1-i));
        }
        ++i;
    }

    //the algorithm
    createVisibilityList(plane,transformedRectangles);

    //map the rectangles on result
    foreach(TreeRectangle& rectangle, transformedRectangles)
    {
        for(int x=rectangle.rect.minx;x<rectangle.rect.maxx;++x)
        {
            for(int y=rectangle.rect.miny; y<rectangle.rect.maxy; ++y)
            {
                result[x-plane.minx][y-plane.miny]=rectangle.number;
            }
        }
    }
}

otze

1. Juhu, ich hab wieder internet
2. hab mir fast gedacht, dass mein algo der langsamste im test ist, ich hab aber nicht genau ahnung, woran es nun hängt.

mein algorithmus funktioniert folgendermaßen: ich baue einen baum auf,indem ich alle rechteck dahingehend einteile, in welchem quadrant des rechtecks sie sich befinden. wenn ein rechteck in verschiedenen quadranten ist, dann wird es an den quadrantgrenzen zerschnitten, sodass dann jedes teil genau in einen quadranten passt. Danach geh ich alle rechtecke durch und überprüfe jedes einzelne, ob es ein anderes rechteck verdeckt. wenn ja, dann wird das verdeckte rechteck entfernt. Das ganze ruf ich dann rekursiv für die einzelnen quadranten wieder auf.

Am Ende füg ich die übrig gebliebenen rechtecke wieder in einer liste zusammen. jedes rechteck in der liste ist dann vollständig sichtbar und kann dann so gezeichnet werden.

lolz

TomasRiker schrieb:

Cool

Hier ist mein Algorithmus:
http://rafb.net/p/fso6kK79.html

Die Kommentare sollten keine Fragen offen lassen.

Den Link gibts leider nicht mehr, könntest du deinen Algorithmus noch einmal hochladen?

Danke.