Du bist nicht angemeldet.

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

1

17.07.2011, 19:20

#14: "Planetenteilung", Spezial, 14.08.2011

#14: "Planetenteilung"

Typ: Spezial
Deadline: 14.08.2011
Abgabe: Code und Nickname per E-Mail an contest@spieleprogrammierer.de

Bitte beachten:
- Ablauf und Regeln


Aufgabenstellung:

Auf dem Planeten X leben zwei Zivilisationen: eine lebt auf dem Land, die andere unter Wasser.
Wegen Streitigkeiten soll der Planet nun in einen nördlichen und einen südlichen Teil aufgeteilt werden. Die Landbewohner bekommen den einen Teil, die Wasserbewohner den anderen. Dabei soll jedoch möglichst viel Lebensfläche genutzt werden können. Das heißt: die Hälfte der Landbewohner sollte möglichst nur aus Land bestehen und die der Wasserbewohner möglichst nur aus Wasser.
Weiterhin soll die Grenze zwischen den beiden Teilen nicht "zu kompliziert" verlaufen.
Eure Aufgabe ist es, eine möglichst gute Teilung für beliebige Planeten zu finden.

Planeten werden in Form eines 512x256 Pixel großen binären Bitmaps gespeichert. "false" steht für Wasser, "true" für Land. Wir gehen unrealistischerweise davon aus, dass jedes Pixel eine gleich große Fläche auf dem Planeten repräsentiert.

Ein Grenzverlauf wird durch ein 512-elementiges Array dargestellt (int border[512]). Der Wert border[x] beschreibt dabei, ab welcher Zeile (inklusive!) dort die südliche Hälfte beginnt. Die Höhe der Grenze ist also eine Funktion von x. Der Nordpol muss jedoch immer zur nördlichen Hälfte gehören und der Südpol immer zur südlichen, das heißt border[x] >= 1 und border[x] <= 255. Da wir es mit einer strikten Nord-Süd-Teilung zu tun haben, schneidet jede vertikale Linie durch die Karte die Grenze exakt einmal (nicht mehr, nicht weniger).

Schauen wir uns einmal einen möglichen Planeten an (Klick für Vollansicht).
Blau ist Wasser, Gelb ist Land:



Eine mögliche Aufteilung sähe dann so aus:



Die Wasserbewohner bekämen bei dieser Lösung den nördlichen Teil, die Landbewohner den südlichen.
Natürlich ist diese Aufteilung nicht "perfekt", da sich etwas Landfläche in der nördlichen Hälfte befindet und etwas Wasser in der südlichen. Eine perfekte Aufteilung ist hier aber auch gar nicht möglich. Darum soll eine möglichst gute Aufteilung gefunden werden.

Im Download-Paket (siehe unten) gibt es ein kleines Programm mit grafischer Benutzeroberfläche, das ihr zum Experimentieren benutzen könnt. Es erlaubt euch eine Grenze mit der Maus zu zeichnen und zeigt dann die erreichte Punktzahl an:



Die von eurem Algorithmus gelieferte Aufteilung wird anhand von zwei Teilpunktzahlen bewertet.

Die erste Teilpunktzahl ergibt sich aus der Länge der Grenzlinie. Jede y-Änderung dy von border[x] nach border[x+1] führt zu einem Punktabzug von dy/2048. Da wir es mit einem Planeten zu tun haben, der rund ist, zählt auch der y-Unterschied zwischen border[511] und border[0] noch dazu. Maximal zu erreichen ist 1 Punkt, und zwar bei einer vollkommen horizontalen Grenzlinie. Achtung, negative Punktzahlen sind möglich!
Falls das kompliziert klingt, schaut euch einfach den Quelltext an - es ist eigentlich ganz simpel! ;)

Die zweite Teilpunktzahl betrifft die Qualität der Aufteilung. Sie ergibt sich wie folgt:
Punktzahl = (Wasser(Hälfte der Wasserbewohner) / Wasser(Gesamt)) * (Land(Hälfte der Landbewohner) / Land(Gesamt))
Im Optimalfall ist hier ebenfalls 1 Punkt zu erreichen. Welche Hälfte die Landbewohner und welche die Wasserbewohner bekommen, entscheidet der Bewertungsalgorithmus selbständig, indem er die jeweils günstigere Alternative wählt.

Die erste Punktzahl fließt mit einem Gewicht von 1/3 in die Gesamtpunktzahl ein, die zweite mit einem Gewicht von 2/3.
Insgesamt ist maximal 1 Punkt zu erreichen.

Achtung, auch die Laufzeit eures Algorithmus spielt eine Rolle! Er darf pro Planet nicht länger als 1 Sekunde brauchen. Dies bezieht sich auf den Rechner, auf dem am Ende getestet werden wird (Intel Core i7 860, 8 GB RAM, Windows 7 64 Bit). Ihr bekommt die Möglichkeit, in eurem Algorithmus die bereits abgelaufene Zeit abzufragen, um dann rechtzeitig abzubrechen, falls nötig. Nicht genutzte Zeit bringt keine Zusatzpunkte.


Die zu implementierende Funktion:

Die Funktion, die ihr implementieren sollt, sieht so aus:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Zusätzliche Standard-Header dürfen hier eingebunden werden.

namespace DEIN_NICKNAME_HIER
{

// Zusätzliche Klassen/Funktionen dürfen hier definiert werden.

void dividePlanet(const PlanetMap& planetMap,
                  Border& outBorder,
                  const Clock& clock)
{
    // TODO:
    // Optimalen Grenzverlauf berechnen und in "outBorder" speichern.

    // - Der Algorithmus darf höchstens 1 Sekunde laufen.
    // - Kein Multi-Threading!
    // - Kein Inline-Assembler!
    // - Keine Intrinsics!
    // - Keine Nicht-Standard-Libraries!
    // - Keine globalen/statischen Variablen benutzen, um nachfolgende
    //   Aufrufe des Algorithmus zu beschleunigen!

    // setze die Grenze einfach in die Mitte
    for(int x = 0; x < MAP_WIDTH; ++x) outBorder[x] = MAP_HEIGHT / 2;

    // mach etwas sinnvolles, so lange noch Zeit übrig ist ...
    while(clock() < 0.99) { /* etwas sinnvolles */ }
}

}



Die Bewertung:

Ich werde alle eingesendeten Lösungen mit einer Reihe von zufällig generierten Planetenkarten testen. Die im Download-Paket enthaltenen 100 Karten sind eine zufällige Auswahl aus diesem größeren Testdatensatz (natürlich ist es verboten, sich für diese 100 Karten schon im Voraus Lösungen zu errechnen und diese dann im Algorithmus nur noch direkt auszugeben). Die erreichten Punktzahlen werden aufsummiert. Benötigt ein Algorithmus länger als 1 Sekunde oder liefert er eine ungültige Lösung, so erhält er für diesen Durchlauf 0 Punkte. Am Ende gewinnt der Teilnehmer, der die meisten Punkte erreicht hat. Bei randomisierten Algorithmen werde ich mehrere Durchläufe durchführen und den Mittelwert bilden, damit weniger Glück im Spiel ist.

Bei der Auswertung werde ich die aktuelle Version von Code::Blocks zum Kompilieren benutzen (GCC). Kompiliert wird mit der Optimierungsstufe 3, "expensive optimizations" und MMX/SSE/SSE2/SSE3. Für optimale "Reproduzierbarkeit" eurer Ergebnisse empfehle ich auch schon bei der Entwicklung diesen Compiler zu benutzen.


Download:

SpproContest14.zip

Das Download-Paket enthält ein Code::Blocks-Projekt (C++) und ein Visual C++-Projekt für ein Programm, das euren Algorithmus mit 100 zufällig generierten Planetenkarten testet, und das bereits erwähnte Experimentier-Tool mitsamt Quelltext. Die Ausgabe eures Algorithmus wird in eine .txt-Datei gespeichert, die vom Experimentier-Tool dann automatisch geladen wird. So könnt ihr eure Lösungen visuell begutachten.

Viel Erfolg!

Beiträge: 775

Beruf: Student

  • Private Nachricht senden

2

17.07.2011, 21:04

Ei das klingt ja ganz spaßig und nicht aaallzu zeitaufwendig (je nach dem ... :D) - ich werds wohl auch mal versuchen :)

Damit das unter VS10 kompilierfähig ist muss man übrigens in Line 245 bei der Mainfunktion ein c_str() beim string für den cout ergänzen. Also:

C-/C++-Quelltext

1
    std::cout << std::string(34, '-').c_str() << std::endl;

Wundert mich, dass das unter Codeblocks geht. Für cout ist doch << std::string gar nicht definiert?

BlueCobold

Community-Fossil

Beiträge: 10 871

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

3

17.07.2011, 21:10

Hö? Mit include <string> und <iostream> geht das nicht?

Also bei mir geht das in VS10:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
#include <iostream>
#include <string>

int main(int argc, char* argv[])
{
    std::cout << std::string(34, '-') << std::endl;
    return 0;
}
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »BlueCobold« (17.07.2011, 21:16)


drakon

Supermoderator

Beiträge: 6 526

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

4

17.07.2011, 21:12

Doch. Du schaust am falschen Ort. ;)
http://www.cplusplus.com/reference/string/operator%3C%3C/

Du kannst ja selbst Funktionen für den << Operator schreiben. Das wurde auch für string gemacht. Nur halt nicht wie für ein Standardtyp, sondern wie eine sonst unabhängige Klasse (in "string").

5

17.07.2011, 21:15

Wieso steht da beim Beispiel

C-/C++-Quelltext

1
int n;
?

Beiträge: 775

Beruf: Student

  • Private Nachricht senden

6

17.07.2011, 21:41

@ drakon & BlueCobold
Ah danke, hab mich schon gewundert es aber dann einfach hingenommen. Nur verstehe ich nicht ganz, wie ich std::string überhaupt nutzen kann, wenn augenscheinlich ja <string> nicht dabei ist - ich hatte zuvor angenommen, dass irgendein Header das wiederum mitzieht (bzw. hab ich gar nicht erst in die Header geschaut). Wenn ich jetzt <string> einbinde, wird der << Operator auch "erkannt". Kann mich bitte mal jemand über meine Wissenslücken aufklären?

drakon

Supermoderator

Beiträge: 6 526

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

7

17.07.2011, 22:04

Es kann sein, dass ein anderer Standardheader das mitzieht, was aber nicht bei jeder Implementierung so sein muss. Falls es im Contest nicht standardmässig dabei ist wird es david ja sicher noch erlauben den Header zu includen oder es explizit irgendwo machen.
<string> enthält die nötigen Definitionen, wie man in dem Link oben sieht. Oder was ist daran nicht klar?

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

8

17.07.2011, 22:24

Standard-Header dürfen natürlich gerne mit eingebunden werden.
Macht es einfach und schreibt einen Kommentar in eure Lösung, damit ich bescheid weiß.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 187

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

9

18.07.2011, 01:14

Hat eigentlich jemand eine Idee, wie "schwer" dieses Problem komplexitätstechnisch ist?

BlueCobold

Community-Fossil

Beiträge: 10 871

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

10

18.07.2011, 06:54

Das hängt vermutlich davon ab wie viele Striche man für die Grenze benutzen darf. ;) Bei unbegrenzter Anzahl wird's irgendwas mit O ( n*m ) sein (wobei n und m die Kantenlänge der Map ist), schätze ich. Bei weniger wird's vermutlich komplexer.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

Werbeanzeige