Eine Woche Programmierwettbewerb: Rechtecke

Jester

Die Rechtecke dürfen laut Aufgabenstellung auch über die fragliche Ebene überstehen. Solche Testfälle sollten auch mitgeneriert werden. Codetags wären prima, so isses ein bißchen schwer zu lesen.

Ich schau, dass ich meinen Algo heute abend irgendwann poste.

jenz

ach ja, darf überstehen,
das macht es beim generieren ja noch viel einfacher...
mit der rechten grenze war ich mir jetzt noch nicht ganz sicher, aber dann klärt sich das ja viel einfacher

code tags sind schon drin.

Ponto

[) schrieb:

paar fragen:
wieso machst du eckige klammern auf die du dann mit runden klammern schließt?
wie ist der "größte index" definiert? index im rectangles-vector?
bedeutet "jeder punkt" jedes integer zwischen min und max für x und y?

Deine zweite Frage: Der Index eines Rechtecks ist der Index im Rectangles Vektor. Der größte davon zählt.
Deine dritte Frage: Die verstehe ich nicht ganz. Zum Rechteck [minx, maxx) x [miny, maxy) gehören alle (x, y) für die gilt minx <= x < maxx und miny <= y < maxy.

Ponto

Headhunter schrieb:

Ich habe eben mal eine lauffähige Version mit Ruby erzeugt - ist das außer Konkurrenz?

Ponto: Hast du vielleicht noch ein paar mehr Testdaten mit korrekten Ausgaben?

Man kann es mitlaufen lassen. Ich poste bald (wahrscheinlich Donnerstag) den Testcode. Dann kann man den auf Ruby portieren. Das müssen die Java Jungs dann auch machen.

Jester

So, hier kommt der Siegercode! Noch ungetestet... aber was kann man falsch machen.

void algorithm(Rectangle plane, std::vector<Rectangle> const & rectangles, std::vector<std::vector<std::size_t> > & result)
{
	for(int x = plane.minx; x<plane.maxx; ++x)
		for(int y = plane.miny; y<plane.maxy; ++y)
			for(size_t index = 0; index<rectangles.size(); ++index)
				if(rectangles[index].minx <= x && x < rectangles[index].maxx && rectangles[index].miny <= y && y < rectangles[index].maxy)
					result[x-plane.minx][y-plane.miny] = index;
}

jenz

ein neuer generator, der geht auch über die begrenzung.

void generate_rectangles(Rectangle plane,std::vector<Rectangle> &rectangles) {
  unsigned int width(plane.maxx-plane.minx);
  unsigned int height(plane.maxy-plane.miny);
  unsigned int number(rand() & 10000);
  rectangles.resize(number+1);
  rectangles[0] = plane;
  for (int i(0);i<number;++i) {
    Rectangle &r(rectangles[i+1]);
    r.minx = rand()%(2*width)-(width/2);
    r.maxx = r.minx+rand()%(2*width)+1;
    r.miny = rand()%(2*height)-(height/2);
    r.maxy = r.miny+rand()%(2*height)+1;
  }
}

jenz

edit: nach jesters nettem hinweis, habe ich die plane noch als erstes Recteck hinzugefügt.
und jetzt ist max immer größer als min

Jester

Die erste Ebene ist mit der Grundebene identisch -- vielleicht doch mal die Aufgabenstellung lesen?

otze

desweiteren erzeugt der algo rechtecke die komplett ausserhalb der ebene liegen. und er erzeugt rechtecke, wo min=max ist.

ich war grad mal auf fehlersuche in meinem algo, und hab deswegen zwecks debugging die rechteckzahl auf 10 limitiert, heraus kamen als rechtecke:

Grundebene [15,25)x[15,25)

erzeugte Ebenen:
[0,19)x[1,6)
[-1,14)x[11,11)

und da wunder ich mich noch, dass der output aus lauter Nullen besteht

ps: muss man auch mit negativen zahlenwerten fertig werden?

pps: jenz, nichts gegen dich ;), auf solche werte wär ich alleine aber wohl net gekommen, und nun kann ich das mal testen

jenz

@otze, kein problem.

ich werde den jetzt gleich mal ausführlich testen.

rechtecke ausserhalb der ebene sollten berücksichtigt (bzw. verworfen) werden.

jenz

edit: ich habe den generator noch mal geändert.
soweit ich jetzt probiert habe scheint es zu passen.

Ponto

otze schrieb:

ps: muss man auch mit negativen zahlenwerten fertig werden?

Die Koordinaten sind int und können als 32-bit 2-Komplement angenommen werden. Also können die auch negativ werden.

otze

ahh ok, danke

noch eine Frage:

Der Parameter rectangles bezeichnet die Menge der eingegebenen Rechtecke. Diese müssen nicht vollständig in der Ebene plane liegen.

bedeuted dass, dass jedes rechteck midnestens einen Punkt mit der Grundebene gemeinsam haben muss? so les ich das nämlich da heraus. Oder ist zb das verhalten von jenz generator richtig?

Ponto

otze schrieb:

ahh ok, danke

noch eine Frage:

Der Parameter rectangles bezeichnet die Menge der eingegebenen Rechtecke. Diese müssen nicht vollständig in der Ebene plane liegen.

bedeuted dass, dass jedes rechteck midnestens einen Punkt mit der Grundebene gemeinsam haben muss? so les ich das nämlich da heraus. Oder ist zb das verhalten von jenz generator richtig?

Die können ganz außerhalb liegen.

otze

dann entfern besser das Wort "vollständig". das verwirrt leute wie mich

ok, keine Fragen mehr

//edit erstes Ergebnis: eine 4096x4096 große ebene mit 15 millionen rechtecken in 2min, 45sec durchgerechnet :). Viel mehr geht im moment nicht, weil ich zwischendurch bedrohlich nah an die 2GB speichergrenze komme ;). Aber das undn bissl mehr speed krieg ich noch hin, bzw wenn ich mehr zeit hätte

habt ihr schon Ergebnisse?

ca. 40 Sekunden bei 4096² und 50M Rechtecken, 915MB Speicherverbrauch
A64 3200+ Venice, Vista x64 (2GB Grenze, wasn des? :D)
muss aber noch Korrektheitstests durchführen

Der Wettbewerb ist IMO etwas ungünstig angesetzt, ich fahre morgen über verlängertes WE Eltern besuchen und möchte die Zeit eigentlich nicht vor dem Rechner verbringen. Ansonsten coole Optimierungsaufgabe, Respekt.

Jester

Ich komme wohl nicht vor Freitag zum Implementieren :(. Könnt ihr die Generatoren die ihr verwendet mal posten?

Ponto

Verwirrt die Teilnehmer nicht durch irgendwelche erfundenen Zwischenergebnisse!

Es soll ja keiner abgeschreckt werden.

otze

Jester schrieb:

Ich komme wohl nicht vor Freitag zum Implementieren :(. Könnt ihr die Generatoren die ihr verwendet mal posten?

ich hab den von jenz benutzt

@Ponto ich bin eh für niemanden ne Konkurrzenz, weil das Programm das bei mir fehlerfrei läuft, bei dir wahrscheinlich nichtmal compilieren wird

camper

Eigentlich die ideale Aufgabe, um Grafikprozessoren zu beschäftigen. Fütter den Prozessor mit den Rechtecken, der Index dient für die Tiefe und Farbe und lass es ihn einfach malen. Anschließend untersucht man einfach die Farbe für jedes Pixel. ist aber wohl nicht portabel hinzukriegen

otze

camper schrieb:

Eigentlich die ideale Aufgabe, um Grafikprozessoren zu beschäftigen. Fütter den Prozessor mit den Rechtecken, der Index dient für die Tiefe und Farbe und lass es ihn einfach malen. Anschließend untersucht man einfach die Farbe für jedes Pixel. ist aber wohl nicht portabel hinzukriegen

ginge schon. opengl is ja ziemlich portabel

Ponto

Wenn Ihr das mit der OpenGL Unterstützung von Qt so hinkriegt, dass es hier kompiliert, soll es mir recht sein. Aber wie bekommt ihr die Daten aus der Graphikkarte? Und wenn man den Index als Farbe kodiert, reichen da die Werte?