Eine Woche Programmierwettbewerb: Rechtecke

Ponto

Hallo,

hier mal ein neuer Programmierwettbewerb.

Aufgabenstellung:

Gegeben ist eine Menge von Rechtecken. Für jeden Punkt in der Ebene ist das Rechteck mit dem größten Index gesucht, das den Punkt überdeckt.

Rechtecke haben die folgende Definition:

struct Rectangle {
   int minx, maxx, miny, maxy;
}

Rechtecke werden halb-offen angegeben: [minx, maxx) x [miny, maxy). Dies bedeutet, dass der Punkt (minx, miny) überdeckt wird; der Punkt (maxx, maxy) aber nicht.

Die zu schreibende Funktion hat folgende Signatur:

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

Das Rechteck plane bezeichnet die Ebene, in der alles stattfindet. Die Ausdehnung ist auf 4096x4096 beschränkt.

Der Parameter rectangles bezeichnet die Menge der eingegebenen Rechtecke. Diese müssen nicht vollständig in der Ebene plane liegen. Überstehende Teile sollen ignoriert werden. Das erste Rechteck in rectangles ist immer identisch mit plane.

Das Ergebnis wird in result gespeichert, welches bereits die korrekten Dimensionen plane.maxx-plane.minx und plane.maxy-plane.miny hat. Der Punkt (x,y) der Ebene wird im Feld result[x-plane.minx][y-plane.miny] gespeichert. Die Felder von result haben anfangs unbestimmte Werte.

Es sollte unerheblich sein, ob man das Programm auf einer 32bit- oder 64bit-Maschine kompiliert.

Bewertung:
Zuerst wird die Korrektheit bewertet. Dann die Geschwindigkeit mit großen Rechteckmengen bis ungefähr 50 Mio.

Abgabe:
Wenn jemand eine sinnvolle Signatur für Java erzeugt, dann würde ich auch Javaabgaben akzeptieren. Ansonsten C++ unter Benutzung der Standardbibliothek, Boost oder Qt.

Die Abgabe hat bis Sonntag 20. Mai 2007 18:00 Uhr per Mail an contest@pontohonk.de zu erfolgen.

Beispiel:

Es werden die folgenden Rechtecke übergeben:

plane:
[3, 8) x [3, 8)

rectangles:
[3, 8) x [3, 8)
[5, 9) x [2, 6)
[4, 6) x [5, 7)
[3, 4) x [3, 7)

Das Ergebnis würde dem folgenden Bild entsprechen:
00000
32200
32211
30111
30111

otze

wenn ich nochmal was zeit finde(grad mitten im Umzug), werd ich mich auch mal dran setzen. wenn ich es bis zum zeitpunkt nicht schaffen sollte(also 2-3 Tage später), wäre es dann vielleicht möglich, ausser Konkurrenz das Programm einzuschicken? dann nur der interesse halber

gibt es sonst noch wen, der sich da grad wohlwollend drüber beugt?

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?

SG1

[) schrieb:

wieso machst du eckige klammern auf die du dann mit runden klammern schließt?

Weil es um halb-offene Intervalle geht.

ok. sry wenn die fragen doof sind, ich habs ned so mit mathe, insb. ned mit notationen.

die aufgabe sieht leicht aus, kann mal jemand kurz sagen wo die schwierigkeit liegt?

Korbinian

Hi,

in Java analog:

public interface PontoContest {
    void algorithm(Rectangle plane, ArrayList<Rectangle> rects, ArrayList<Integer> result);
}

Headhunter

Korbinian schrieb:

Hi,

in Java analog:

public interface PontoContest {
    void algorithm(Rectangle plane, ArrayList<Rectangle> rects, ArrayList<Integer> result);
}

Sicher? Müsste "results" nicht zweidimensional sein? Also so:

public interface PontoContest {
    void algorithm(Rectangle plane, ArrayList<Rectangle> rects, ArrayList<ArrayList<Integer>> result);
}

OT: Muss man eigentlich immer noch so auf "result" zugreifen? result.elementAt(x).elementAt(y)

Jester

der letzte Parametertyp sollte eher ArrayList<ArrayList<Integer>> heißen, oder?

Korbinian

Jap, ihr habt Recht.

Headhunter

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?

Jester

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

Headhunter

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 ?

Jester

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.

jenz

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

otze

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

kommt drauf an, welches N du meinst

jenz

@jester: okay, dann mache ich das.

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

jenz

otze

jenz schrieb:

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

ich sehe 2, wobei die eine teilmenge der anderen ist

jenz

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

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.