Du bist nicht angemeldet.

Werbeanzeige

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 179

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

1

09.02.2013, 12:30

#15: "Rutschige Angelegenheit", Geschwindigkeit, 03.03.2013

Hallo liebe Community,

anstatt mich dem Wahnsinn des Karnevals hinzugeben, habe ich die Zeit genutzt um mir einen neuen Programmier-Contest auszudenken!
Der Titel des neuen Contests lautet "Rutschige Angelegenheit", es handelt sich um einen Geschwindigkeits-Contest (eure Programme müssen möglichst schnell sein), und er läuft bis einschließlich zum 03.03.2013.

Das Spiel
Diesmal geht es um ein einfaches Spiel, das ich "Sokoslide" nenne.
Ein Sokoslide-Level sieht wie folgt aus:



Jedes Level besteht aus 16x16 Feldern.
Ein Feld kann folgendes sein:
- Leer bzw. Eisfläche
- Mauer
- Spielfigur (roter/grüner/blauer Kreis)
- Zielfeld (rotes/grünes/blaues Quadrat)

Wichtige Eigenschaften eines Levels:
- Der innere Rand eines Levels besteht immer vollständig aus Mauern, so wie im Beispiel oben.
- In jedem Level gibt es exakt 3 Spielfiguren (eine in jeder Farbe) und exakt 3 Zielfelder (eins in jeder Farbe).
- Auch wenn das im Beispiel-Level der Fall ist, ist nicht garantiert, dass sich die Spielfiguren und die Zielfelder direkt neben einer Mauer befinden.
- Der betretbare Bereich jedes Levels ist eine zusammenhängende Fläche. Es kann also nicht passieren, dass zwei Spielfiguren durch Mauern komplett getrennt sind.

Das Ziel des Spiels ist es, alle drei Spielfiguren auf ihre farblich passenden Zielfelder zu bewegen.
Eine Spielfigur kann sich aber nicht beliebig bewegen, sondern nur in eine Richtung (links, rechts, oben, unten) angestoßen werden. Da alles auf einer Eisfläche stattfindet, "rutscht" sie so lange weiter, bis sie entweder gegen eine Mauer oder gegen eine andere Spielfigur stößt (daher der Name des Contests). Sie bleibt insbesondere auch nicht automatisch stehen, wenn sie ein Zielfeld erreicht hat.

Schauen wir uns einmal eine Lösung für das oben gezeigte Level an (anklicken zum Vergrößern):



Wie man sieht, benötigt diese Lösung 14 Züge.
Tatsächlich ist dies auch eine kürzeste Lösung, d.h. mit weniger als 14 Zügen kann man das Level nicht bewältigen.

Die Aufgabe
Vielleicht könnt ihr euch jetzt bereits denken, was eure Aufgabe ist ...
Ihr sollt eine Funktion programmieren, die für ein gegebenes Sokoslide-Level berechnet, wie viele Züge mindestens für die Lösung benötigt werden.
Übergibt man der Funktion also das Level aus unserem Beispiel, dann müsste sie korrekterweise mit 14 antworten.

Folgender Code zeigt die Definition der Funktion sowie des Typs Level, der einfach nur ein 16x16-char-Array ist.
Im Code seht ihr auch bereits, wie die verschiedenen Spielfelder im Array dargestellt werden, nämlich mit den Zeichen . # r g b R G B:

C-/C++-Quelltext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 16x16-Spielfeld.
// Jedes Feld ist entweder:
// - leer '.'
// - Mauer '#'
// - Block 'r', 'g', 'b'
// - Zielfeld 'R', 'G', 'B'
typedef char Level[16][16];

// Die zu programmierende Funktion:
// Gegeben ist ein garantiert in höchstens 255 Zügen lösbares Level.
// Gesucht, als Rückgabewert, ist die Anzahl der Züge der optimalen Lösung (Mindestanzahl).
int numMovesToSolve(const Level& level)
{
    // Hier kommt dein Code!
    // Berechne die zur Lösung benötigte Anzahl von Zügen und gib sie zurück.
    return 0;
}

Das Beispiel-Level von vorhin sieht "kodiert" wie folgt aus:

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
################
#.......R......#
#..............#
#..####.....####
#..####.....####
#..####..b..####
#..####..#.....#
#..####..#.....#
#........#.....#
#..####..#..g..#
#..####..####..#
#..##.r.......B#
#..##..........#
#......G.....###
#............###
################

Worauf ihr euch verlassen dürft
Um die Sache nicht unnötig kompliziert zu machen, dürft ihr euch auf folgende Dinge verlassen:
- Es gibt keine ungültigen Levels bzw. Eingaben.
- Jedes übergebene Level ist lösbar, und zwar mit mindestens 3 und höchstens 255 Zügen.
- Die Eigenschaften der Levels, die weiter oben aufgelistet wurden, werden immer eingehalten.

Das Programmier-Paket
Ich habe ein kleines Test-Framework geschrieben, mit dem ihr eure Lösung testen könnt. Es enthält eine Datei levels.txt, in der bereits 5 Beispiel-Levels zusammen mit ihren korrekten Lösungen enthalten sind. Das Framework lädt diese, ruft eure Funktion auf und testet sie auf Korrektheit. Außerdem misst es die Geschwindigkeit eurer Lösung.
Im Zip-Paket findet ihr einen CodeLite-Workspace und eine Solution für Visual C++ 2010.

Das Paket könnt ihr hier herunterladen: zum Download

Was ist erlaubt/verboten?
Zunächst gelten die normalen Regeln. Das Wichtigste hier noch einmal:
- Programmiersprache: C++!
- Kein Inline-Assembler erlaubt, auch keine Intrinsics.
- Eure Funktion darf keine statischen Variablen benutzen oder sich auf sonstige Weise Dinge für einen nachfolgenden Aufruf "merken". Das gilt auch für Speicherreservierungen.
- Keine Nicht-Standard-Libraries benutzen!
- Kein OpenMP/Multithreading.

Wie wird ausgewertet / Worauf kommt es an?
Ich werde jede eingereichte Lösung mit einer Reihe von Sokoslide-Levels testen (nicht nur die, die im Paket enthalten sind!).
Oberstes Kriterium ist die Korrektheit. Liefert eine Funktion eine falsche Antwort, führt dies zur Disqualifikation.
Alle korrekten Lösungen werden nun auf Geschwindigkeit getestet. Um die Benutzer von GCC bzw. Visual C++ nicht zu benachteiligen, werde ich versuchen jede Lösung mit beiden Compilern zu kompilieren und dann jeweils das bessere Ergebnis benutzen. Wenn eine Lösung nur mit einem Compiler kompiliert werden kann, ist das nicht weiter schlimm, aber ihr verliert diesen Vorteil.
Wie genau die Lösungen untereinander verglichen werden, kann ich jetzt noch nicht sagen. Es wird aber ähnlich ablaufen wie in früheren Contests dieser Art.
Ich werde Visual C++ 2012 sowie die bei der neuesten CodeLite-Version mitgelieferte MinGW-Version zum Kompilieren benutzen, und zwar mit den Standardeinstellungen für den Release-Mode (beim GCC bedeutet das -O2). Bei Visual C++ wird die Größe des Stacks der von MinGW angepasst (2 MB), um eine bessere Vergleichbarkeit zu gewährleisten. Ich benutze die 32-Bit-Versionen der Compiler.

Was gibt es zu gewinnen?
Dem Gewinner des Contests winkt ein besonderer Rang im Forum (siehe z.B. Helmut!), unendlicher Ruhm und Ehre, sowie ein kleiner Sachpreis (ich weiß jedoch noch nicht, was es sein wird).

Was muss ich tun, um mitzumachen?
Lade dir das Programmier-Paket herunter, tüftle eine Lösung aus und teste sie auf Herz und Nieren. Sende deinen Code dann an contest@spieleprogrammierer.de, und zwar bis zum 03.03.2013 (23:59:59 Uhr). Es ist kein Problem, mehrfach eine Lösung einzureichen (ich benutze dann die zuletzt eingereichte Version). Gib in der E-Mail auch bitte deinen Benutzernamen im Forum an. Alle Lösungen werden später veröffentlicht.

Bei Fragen/Problemen schreibt bitte in diesen Thread.

Viel Erfolg!

2

09.02.2013, 12:39

Welche Versionen von VC++ und gcc wirst du verwenden (Stichwort: C++11 Unterstützung)?
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 179

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

3

09.02.2013, 12:41

- Visual C++ 2012 (muss ich erst noch installieren, sollte aber kein Problem sein die 2010er-Solution zu öffnen)
- Die MinGW-Version, die bei der dann aktuellen CodeLite-Version mitgeliefert wird (aktuell ist das 4.7.1).

Schrompf

Alter Hase

Beiträge: 1 298

Wohnort: Dresden

Beruf: Softwareentwickler

  • Private Nachricht senden

4

09.02.2013, 12:46

VC2010 meint: auto und Lambdas, aber keine Range Based Loops. Nuja, immerhin was. Ich finde die Idee gut, und werde mal einen Nachmittag verwenden, wenn ich Zeit finde. Aktuell bin ich aber in heftigem Splatter-Fertigstellungsstress und sollte eigentlich keine Zeit auf solche Spiele verwenden :-(
Häuptling von Dreamworlds. Baut aktuell an nichts konkretem, weil das Vollzeitangestelltenverhältnis ihn fest im Griff hat. Baut daneben nur noch sehr selten an der Open Asset Import Library mit.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 179

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

5

09.02.2013, 12:49

@Schrompf:
Ich benutze die 2012er zum Testen. Die 2010er-Solution ist nur dafür gedacht, dass es möglichst viele öffnen können, falls sich da etwas geändert hat.
Würde mich freuen, wenn du mitmachst! Zumindest eine einfache Lösung ist ja recht schnell programmiert. ;)

BlueCobold

Community-Fossil

Beiträge: 10 855

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

6

09.02.2013, 13:25

Eine einzelne Funktion? So'n hässliches Monster-Spaghetti-Ding?
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]

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 179

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

7

09.02.2013, 13:33

Es hindert dich ja niemand daran mit Klassen zu arbeiten, die du in deiner Funktion benutzt.
Vor der Abgabe kopierst du die dann alle in deine Funktion rein, als lokale Klassen.

BlueCobold

Community-Fossil

Beiträge: 10 855

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

8

09.02.2013, 13:42

So eingerostet ist mein C++ nun auch wieder nicht, dass man mir das erklären müsste ;) Ich fand's nur... na ja, ich finde sowas hässlich :P Aber für den Contest akzeptabel.
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]

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

9

09.02.2013, 15:04

Endlich :) Schöne Aufgabe :)
Wird wohl nur etwas mühselig dafür Testkarten zu machen.
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

BlueCobold

Community-Fossil

Beiträge: 10 855

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

10

09.02.2013, 16:44

Testkarten sind nicht so ein Problem, aber die Minimierungsbedingung ;) Man kann ziemlich fiese Karten konstruieren, die viele Heuristiken und Annahmen gleich mal sprengen können.
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