Hallo liebe Community,
da es sicherlich interessant wäre einen zu machen habe ich mich umgeschaut und eine nette Idee für einen Programmierer Contest gefunden. Danke dazu an David Scherfgen.
Und ich dachte warum nicht, um mal ein frischen Wind reinzubringen, wer mit machen will macht mit und wer nicht, der nicht.
Das Spiel
Diesmal geht es um ein einfaches Spiel, das ich "Sokoslide" nenne.
Ein Sokoslide-Level sieht wie folgt aus:
mmo-core.de/attachment/3818/?s…4a6642572fc31eefdf988c255
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):
mmo-core.de/attachment/3819/?s…4a6642572fc31eefdf988c255
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:
Alles anzeigen
Das Beispiel-Level von vorhin sieht "kodiert" wie folgt aus:
Alles anzeigen
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.
Was ist erlaubt?
Zunächst gelten die normalen Regeln. Das Wichtigste hier noch einmal:
- Programmiersprache: Jede Sprache.
Das Programmier-Paket
Im Anhang findet ihr ein kleines Test-Framework , 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.
Das Paket beinhaltet den Quellcode für VS2012: http://www.file-upload.net/download-8015583/paket.zip.html
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 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 einfach per PN, und zwar bis zum 26.09.2013 (23:59:59 Uhr). Es ist kein Problem, mehrfach eine Lösung einzureichen (ich benutze dann die zuletzt eingereichte Version). Alle Lösungen werden später veröffentlicht.
credits:David Scherfgen von spieleprogrammierer.de
da es sicherlich interessant wäre einen zu machen habe ich mich umgeschaut und eine nette Idee für einen Programmierer Contest gefunden. Danke dazu an David Scherfgen.
Und ich dachte warum nicht, um mal ein frischen Wind reinzubringen, wer mit machen will macht mit und wer nicht, der nicht.
Das Spiel
Diesmal geht es um ein einfaches Spiel, das ich "Sokoslide" nenne.
Ein Sokoslide-Level sieht wie folgt aus:
mmo-core.de/attachment/3818/?s…4a6642572fc31eefdf988c255
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):
mmo-core.de/attachment/3819/?s…4a6642572fc31eefdf988c255
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:
Quellcode
- [COLOR=green]// 16x16-Spielfeld.[/COLOR][COLOR=green]// Jedes Feld ist entweder:[/COLOR]
- [COLOR=green]// - leer '.'[/COLOR]
- [COLOR=green]// - Mauer '#'[/COLOR]
- [COLOR=green]// - Block 'r', 'g', 'b'[/COLOR]
- [COLOR=green]// - Zielfeld 'R', 'G', 'B'[/COLOR]
- [COLOR=blue]typedef[/COLOR] [COLOR=blue]char[/COLOR] Level[[COLOR=#FF8C00]16[/COLOR]][[COLOR=#FF8C00]16[/COLOR]];
- [COLOR=green]// Die zu programmierende Funktion:[/COLOR]
- [COLOR=green]// Gegeben ist ein garantiert in höchstens 255 Zügen lösbares Level.[/COLOR]
- [COLOR=green]// Gesucht, als Rückgabewert, ist die Anzahl der Züge der optimalen Lösung (Mindestanzahl).[/COLOR]
- [COLOR=blue]int[/COLOR] numMovesToSolve([COLOR=blue]const[/COLOR] Level[COLOR=green]&[/COLOR] level)
- {
- [COLOR=green]// Hier kommt dein Code![/COLOR]
- [COLOR=green]// Berechne die zur Lösung benötigte Anzahl von Zügen und gib sie zurück.[/COLOR]
- [COLOR=blue]return[/COLOR] [COLOR=#FF8C00]0[/COLOR];
- }
Das Beispiel-Level von vorhin sieht "kodiert" wie folgt aus:
Brainfuck-Quellcode
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.
Was ist erlaubt?
Zunächst gelten die normalen Regeln. Das Wichtigste hier noch einmal:
- Programmiersprache: Jede Sprache.
Das Programmier-Paket
Im Anhang findet ihr ein kleines Test-Framework , 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.
Das Paket beinhaltet den Quellcode für VS2012: http://www.file-upload.net/download-8015583/paket.zip.html
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 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 einfach per PN, und zwar bis zum 26.09.2013 (23:59:59 Uhr). Es ist kein Problem, mehrfach eine Lösung einzureichen (ich benutze dann die zuletzt eingereichte Version). Alle Lösungen werden später veröffentlicht.
credits:David Scherfgen von spieleprogrammierer.de