3. Eine Woche Programmierwettbewerb: Rechtecke

Eine Woche Programmierwettbewerb: Rechtecke

  • K

    Jap, ihr habt Recht.

    0
  • H

    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?

    0
  • J

    Wenn Du nen Generator schreibst und hier postest, dann poste ich meinen simplen Algorithmus, der so stupide ist, dass er garantiert nix falsch macht. 🙂

    0
  • H

    Generator? Nööö, da habe ich zwar auch schon dran gedacht, aber noch nichts programmiert. Was ich meinte war, ist dass ich ne Lösung in Ruby statt C++/Java geschrieben habe.
    Und was fürn Algorithmus meinst du 😃 ?

    0
  • J

    Mein Vorschlag: Du schreibst nen Generator (damit haben wir ne Beispielquelle) und ich rücke dafür einen Lösungsalgorithmus raus, der zwar lahm ist, aber garantiert richtig. 🙂

    0
  • J

    @jester: Einen Generator für Zufallsrechtecke???

    Mehr muss er (oder besser du) nicht machen, wenn deine Lösung wirklich keine Fehler macht, dann kannst du doch darauf gleich die Ausgabe erzeugen.

    Und eine paar Zufallsrechtecke zu erzeugen sollte nun wirklich nicht sooo schwer sein, oder?

    Also eigentlich bietet sich doch an, dass du (Jester) den Generator schreibst.
    😉

    Sorry, aber liegt einfach so auf der Hand.

    Grüße,
    Jenz

    PS. ich werde auch eine Lösung zusammentickern und natürlich nicht die offensichtliche triviale.
    Aber besser als O(N) wird man von der Komplexität wohl nicht werden können...
    Aber das ist ja auch nicht gefragt, sondern eine schnelle Lösung... auch wenn sich das meistens gegenseitig bedingt.

    0
  • O

    Aber besser als O(N) wird man von der Komplexität wohl nicht werden können...

    kommt drauf an, welches N du meinst 😉

    0
  • J

    @jester: okay, dann mache ich das.

    @otze: ich sehe da nur eine veränderliche und du?

    jenz

    0
  • O

    jenz schrieb:

    @otze: ich sehe da nur eine veränderliche und du?

    ich sehe 2, wobei die eine teilmenge der anderen ist 😉

    0
  • J

    das hier könnte doch ein guter anfang für einen generator sein:

    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);
  for (int i(0);i<number;++i) {
    Rectangle &r(rectangles[i]);
    r.minx = rand()%width;
    r.maxx = r.minx+rand()%(width-r.minx);
    r.miny = rand()%height;
    r.maxy = r.miny+rand()%(height-r.miny);
  }
}

    leider muss ich jetzt weg. ist ungetestet, aber compiliert...

    Heute Abend geht es weiter.

    Jens

    0
  • J

    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.

    0
  • J

    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.

    0
  • P

    [) 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.

    0
  • P

    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.

    0
  • J

    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;
}
    0
  • J

    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

    0
  • J

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

    0
  • O

    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 😃

    0
  • J

    @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.

    0
  • P

    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.

    0
Anmelden zum Antworten