#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!
) - ich werds wohl auch mal versuchen 
Offtopic »
Mal wieder was Lustiges
(23.01.2009, 09:49)
23.04.2024, 08:20
Zum Seitenanfang
