4. ** Brainfuck Interpreter Contest ** [abgeschlossen]

** Brainfuck Interpreter Contest ** [abgeschlossen]


  • ----------------------------
    Ergebnis
    ----------------------------

    http://www.c-plusplus.net/forum/p2120628#2120628

    ---------------------------------------------------------------------------------

    Nachdem der andere Thread ja etwas eingepennt ist, mache ich hier einen neuen auf.

    Ich rufe hiermit den C++.de "C# Brainfuck Interpreter Contest" aus.

    ----------------------------
    Aufgabe
    ----------------------------

    Aufgabe: entwickle einen möglichst kurzen aber korrent funktionierenden Brainfuck Interpreter.

    ----------------------------
    Termin
    ----------------------------

    Start: Montag, 5. September, 00:00
    Ende: Samstag, 17. September, 23:59 (verlängert)

    Regeländerungen sind bis zum offiziennen Start möglich. (Werde ich aber nur machen, wenn es Sinn macht/nötig ist.)

    ----------------------------
    Regeln/Anforderungen
    ----------------------------

    Der Interpreter kann Programme bis einschliesslich 2^20 Zeichen verarbeiten.
    Der Speicher der Brainfuck-Maschine ("das Band") hat 2^16 oder mehr Zellen.
    Jede Zelle kann eine vorzeichenbehaftete Zahl speichern, Wertebereich mindestens 16 Bit (-32768 ... 32767).
    Der Interpreter muss eine Schleifen-Verschachtelungstiefe von min. 1024 unterstützen.

    "Standard" Brainfuck Befehlssatz, also

    ><+-.,[]

    Sämtliche anderen Zeichen werden vom Interpreter ignoriert (d.h. z.B. auch '\0').

    Zu Programmbeginn enthalten alle Zellen den Wert 0, ebenso der "Datenzeiger".

    Das Programm endet, wenn der "Programmzeiger" hinter das letzte Zeichen des Programms verschoben wird. Diese Position darf auch durch die beiden Schleifen-Befehle ("[" und "]") erreicht werden.

    Der Interpreter ist eine C# Klasse, compilierbar mit Visual C# 2010 (Express).
    Verwendet werden dürfen sämtliche C# Features die von Visual C# 2010 (Express) unterstützt werden (einschliesslich "unsafe"), sowie das gesamte .NET Framework 4.0. Eventuelle Compiler-Warnings sind egal. Andere externe Libraries sind nicht erlaubt. Ebenso nicht erlaubt ist das Nachladen von Code/Daten aus Files oder dem Internet.

    Anm.: Zum Herzeigen wäre es natürlich schön wenn der Code auch mit "ideone.com" (Mono 2.8) funktioniert, das ist aber keine Voraussetzung.

    Folgendes Interface wird vom Testsystem bereitgestellt:

    // Im golbalen Namespace 
interface S/*ystem*/
{
    string P/*rogram*/ { get; }  // Das Programm (der Source-Code)
    int R/*ead*/();              // Liest ein Input-Zeichen
    void W/*rite*/(int ch);      // Schreibt ein Output-Zeichen
}

    Der Interpreter besteht aus einer Klasse "I", die (zumindest) eine öffentliche (public) Funktion "R" implementiert.

    Das Testsystem instanziert diese Klasse mit dem Default-Konstruktor, und ruft dann die Funktion "R" (wie "Run") auf, wobei als einziger Parameter eine Referenz auf das System (siehe Interface "S" oben) übergeben wird. Die genaue Signatur der Funktion ist dabei nicht vorgeschrieben (d.h. wer meint dass er sich leisten kann darf sie z.B. gerne "static" oder gar "virtual" machen).

    Anm.: die Funktion "R" darf weitere zusätzliche Parameter haben, sofern diese alle optional sind. Beim Aufruf werden dann die jeweiligen Default-Werte für diese Parameter übergeben.

    Die Funktion "R" muss das über das "System" zugängliche Brainfuck Programm ("S.P") ausführen, und dabei die erwarteten Nebeneffekte produzieren (=Aufrufe von S.R und S.W zum Lesen/Schreiben von Input/Output).

    Wie genau die Klasse "I" das macht ist egal, d.h. das Programm muss nicht klassisch "interpretiert" werden - wer einen ausreichend kurzen JIT-Compiler o.ä. hinbekommt kann damit gerne antreten.

    Der Interpreter muss korrekte Brainfuck Programme korrekt verarbeiten können.

    Der Interpreter darf davon ausgehen, dass ein korrektes Brainfuck Programm bestimmte Bedingungen erfüllt/einhält:

    • "[" und "]" sind "balanced" (also "]", "[", "[[]", "[]]" etc. wären keine korrekten Programme)
    • Der "Datenzeiger" wird vom Programm niemals ausserhalb des Bandes positioniert
    • Das Programm erzeugt keine Unter- oder Überläufe (d.h. es inkrementiert keine Zellen mit dem Wert 32767 und dekrementiert keine Zellen mit dem Wert -32768)

    Anders gesagt: das oben erwähnte ist UB, der Interpreter muss damit nicht klarkommen oder in einer bestimmten Art und Weise reagieren. Fehlermeldungen/Diagnostics für diese Fälle sind nicht erforderlich.

    Die Funktion "I.R" darf, sofern ein korrektes Brainfuck Programm übergeben wurde, keinerlei Exceptions werfen.

    Die Interpreter werden mit dem von mir entwickelten Test-System getestet. Voraussetzung für die Wertung ist dass alle Tests mit "PASSED" abgeschlossen werden.

    Das Test-System wird, inklusive Tests, vor Beginn des Contests zur Verfügung gestellt.

    ----------------------------
    Formales & Wertung
    ----------------------------

    Abgegeben wird der komplette Quelltext der Klasse "I".

    Der - korrekt funktionierende - Brainfuck Interpreter mit dem kürzeste Source-Code (gemessen in Zeichen) gewinnt.
    Sind zwei oder mehr Interpreter exakt gleich lang, dann teilen diese sich den jeweiligen Platz.

    Gezählt wird der gesamte Quelltext der Klasse, ab dem "c" von "class I" bis inklusive der Klammer "}" welche die Definition von "I" abschliesst.
    Sollte ein Teilnehmer "using" benötigen, so sind diese vor die Definition der Klasse "I" zu schreiben. Die Zählung beginnt dann mit dem "u" des 1. "using".

    "partial" Klassen sind nicht erlaubt.
    Sämtliche Whitespaces (Spaces, Tabs, Newlines etc.) werden mitgezählt.
    Der Quelltext muss allerdings keinerlei "schöne" oder "übliche" Formatierung haben, und natürlich auch keinerlei Kommentare.

    Anm.: Es wäre schön, wenn ihr euren Code 1x in der zu bewertenden Form abgebt, und zusätzlich eine schön formatierte Variante, inklusive erklärender Kommentare. Ist aber ebenso keine Voraussetzung.

    Beispiel:

    class I/*nterpreter*/ // public brauchen wir nicht
{
	// public ist Pflicht, die genaue Signatur/Parameternamen etc. sind nicht vorgeschrieben.
	// Voraussetzung ist bloss dass der Aufruf mit genau einem Parameter vom Typ "S" möglich ist.
	// Wer mag darf auch nen Returnwert verwenden, z.B. wenn jmd. was mit Rekursion versuchen möchte.
	public void R/*un*/(S theSystemButYouMightChooseAShorterName)
	{
		// hier schlauen Code reinschreiben
	}
}

    Eine weitere Anmerkung:

    Es sollen Brainfuck-Interpreter verglichen werden, und nicht nach Wegen gesucht werden wie man das Testsystem bescheissen kann. Beiträge die versuchen das Testsystem über z.B. Reflection zu bescheissen werden disqualifiziert.
    (Ich könnte natürlich stattdessen das Testsystem soweit absichern dass es nicht mehr möglich ist zu bescheissen, aber das ist mir ehrlich gesagt zu viel Aufwand.)

    ----------------------------
    Abgabe
    ----------------------------

    Ihr könnt eure Interpreter auf einem der folgenden Wege abgeben

    • Email mit dem Quelltext als Attachment an s7xfhgb7vf@snkmail.com (alle deren Quelltext Zeichen ausserhalb des Latin-I Zeichensatzes enthält bitte nur diese Option)
    • Email mit dem Quelltext direkt im Text der Email
    • Email mit einem Link auf http://www.ideone.com mit dem Test-System das euren Interpreter ausführt. Die Klasse "I" sollte dabei ganz am Anfang stehen. (Tip: mit "visibility: private" scheint euer Code nicht unter "recent" auf)
    • Email über's Forum geht natürlich auch, und wäre fast besser, da damit automatisch klar ist von wem der Beitrag kommt

    Natürlich wäre es auch möglich eure Interpreter hier im Forum zu posten, allerdings möchte ich euch bitten es nicht zu tun. Ich fände es interessanter, wenn ein Austausch erst nach Ende des Contests stattfindet.
    Und ihr wollte ja auch eure besten Tricks nicht vorab verraten 🙂

    Mit der Abgabe eines Interpreters stimmt ihr der Veröffentlichung im Forum nach Ende des Contests zu.

    0

  • Und hier das Testsystem:

    V5: http://ideone.com/dWU7z (volkards "strosoki" hinzugefügt)
    V4: http://ideone.com/PzGpP (alle Tests OK, enthält "VerifyingInterpreter" der die Tests testet 🕶 )
    V3: http://ideone.com/VjOeH (mehr Tests)
    V2: http://ideone.com/NkEMJ
    V1: http://ideone.com/AzF6U

    Ein kleines Visual Studio Makro das beim Formatieren/Zählen hilft gibt's hier:

    http://www.c-plusplus.net/forum/p2115505#2115505

    ---------------------

    Falls jemand interessante Test-Brainfuck-Programme hat, bitte auch einfach an s7xfhgb7vf@snkmail.com schicken, über die Forums-Mail oder einfach hier posten.
    Die Laufzeit sollte sich allerdings in Grenzen halten - ideone.com limitiert ja auf 2 Sekunden CPU Zeit.

    0
  • Administrator

    Ich hab dich mal angepinnt. Hoffentlich wird es was.

    Grüssli

    0
  • S

    Hätte große Lust, aber derzeit bin ich leider zu zugedeckt um mitzumachen 😞 Viel Erfolg an die Teilnehmer, zeigt was ihr könnt 👍

    MfG SideWinder

    0
  • ?

    Jetzt habe ich hier editiert statt zu zitieren. Oh bin ich neben der Spur...

    0
  • ?

    hustbaer schrieb:

    "Standard" Brainfuck Befehlssatz, also

    ><+-.,[]

    Folgendes Interface wird vom Testsystem bereitgestellt:

    // Im golbalen Namespace 
interface S/*ystem*/
{
    string P/*rogram*/ { get; }  // Das Programm (der Source-Code)
    int R/*ead*/();              // Liest ein Input-Zeichen
    void W/*rite*/(int ch);      // Schreibt ein Output-Zeichen
}

    Das Testsystem instanziert diese Klasse mit dem Default-Konstruktor, und ruft dann die Funktion R() auf.

    Also bei "." ruft man W/*rite*/ und bei "," R/*ead*/ auf?
    Warum ruft das Testsystem dann von sich aus R auf? 😕

    0
  • B

    edit: Auch verlesen. Dürfte wohl mehr Betriebsblindheit gewesen sein ... 🙂

    0
  • ?

    Achsooo... sorry verlesen.

    Wie auch immer: Der erste Interpreter läuft fehlerfrei nach 15 minuten arbeit. Ich liebe Brainfuck 😃

    0

  • @Dravere:
    Danke 🙂

    @SideWinder & µ:
    Also von mir aus können wir das ganze gerne verlängern, z.B. auch auf 14 Tage. Regeländerungen sind ja noch erlaubt 🙂

    --------------------

    Wer für/gegen eine Verlängerung ist einfach mit einem +1/-1 Beitrag abstimmen, danke 🙂

    0
  • ?

    Von meiner Seite aus ist eine Verlängerung nicht mehr notwendig.

    0
  • B

    Was genau verstehst du unter "Interpreter"? Ist das gemeint wie "kein Compiler" oder einfach allgemein als eine Implementation der Sprache?

    0
  • Administrator

    +1 für die Verlängerung auf 14 Tage.

    Oder ich mache definitiv nicht mit 🙂
    Meine Chancen zu Gewinnen dürften aber sowieso klein sein. Ich habe einen Hang zu langen Code zu schreiben 😃

    Grüssli

    0

  • @Bashar:
    Mit "Interpreter" ist einfach eine Implementierung gemeint.

    Voraussetzung ist allerdings, dass die Funktion "R" so implementiert wird, dass sie das Programm auch gleich ausführt. Ob sie dazu erstmal IL Code erzeugt, den dann lädt und ausführt, oder das Programm klassisch "interpretiert", ist egal.

    Ich gehe zwar davon aus, dass eine compilierende Implementierung sowieso keine Chance hat zu gewinnen, sehe aber keinen Grund sowas zu verbieten.

    Ich werden heute Abend/Nacht noch den ersten Beitrag entsprechend anpassen.

    Ebenso werd' ich noch ein Paar Beispiele reinschreiben was nicht erlaubt ist. z.B. das Referenzieren/Verwenden von externen Programmen oder Daten, sei's nun über's lokale File-System oder über's Netzwerk. (Das Erzeugen von neuen Files wäre dagegen erlaubt, wobei ich auch davon ausgehe dass eine Implementierung die mit Files rummacht wohl keine Chancen haben wird)

    0

  • Ich werde übrigens selbst auch mitmachen.
    Fairerweise sollte das wohl ausser Konkurrenz sein, da die Regeln ja von mir aufgestellt wurden 🙂

    0
  • ?

    @hustbaer
    Von mir aus kannst Du in Konkurrenz teilnehmen.

    Ich bin eigentlich fertig und wüsste gerade nicht, wo ich noch Zeichen sparen kann. Der Code sieht aus wie Sau 🙂

    0
  • ?

    Nochmal dazu:

    Sämtliche Whitespaces (Spaces, Tabs, Newlines etc.) werden mitgezählt.

    Das ist die einzige Regel die ich etwas unsinnig finde. Sie zwingt einen dazu am Ende alles in eine Zeile zu pressen.
    Könnte man die Whitespaces nicht einfach bei der Zählung ignorieren, um wenigstens etwas Struktur in den Code zu kriegen?

    0

  • µ schrieb:

    Sämtliche Whitespaces (Spaces, Tabs, Newlines etc.) werden mitgezählt.

    Das ist die einzige Regel die ich etwas unsinnig finde. Sie zwingt einen dazu am Ende alles in eine Zeile zu pressen.
    Könnte man die Whitespaces nicht einfach bei der Zählung ignorieren, um wenigstens etwas Struktur in den Code zu kriegen?

    Naja, ich sehe keine sinnvolle Alternative.

    Auch sehe ich den Sinn dahinter nicht.
    Ohne automatisches Zähl-Tool hätte es wohl kaum einen Sinn, denn wenn man mit Hand zählen muss, ist die schnellste Möglichkeit immer noch alle unnötigen Whitespaces zu eliminieren und dann auf die Zeilenlänge(n) zu gucken.

    ----

    Ich fände es allerdings gut, wenn die Teilnehmer ihren Code 1x in "Bewertungsform" und 1x zusätzlich hübsch formatiert und vor allem mit Kommentaren abgeben, damit man einfacher versteht was abgeht. Auch gerne inklusive Erklärung wie man auf ein spezielles Konstrukt gekommen ist etc.

    0
  • Administrator

    Ehm, müssen alle Fragen zum Contest öffentlich gestellt werden?
    *Angst hat seine Idee zu verraten* 😃

    Grüssli

    0

  • Dravere schrieb:

    Ehm, müssen alle Fragen zum Contest öffentlich gestellt werden?
    *Angst hat seine Idee zu verraten* 😃

    Natürlich nicht. Jeder der Fragen hat kann mir auch gerne eine Mail über's Forum schicken oder über die Email Adresse im 1. Beitrag. Ich verspreche diese Mails auf jeden Fall nicht vor Ende des Contests zu veröffentlichen, und auch danach nicht ohne guten Grund (Drohungen, gröbere Beschimpfungen, jemand braucht ein Alibi 😃 etc.).

    Wenn es darum gehen sollte dass jemand etwas ausnutzen möchte, was in den Vorgaben unklar formuliert ist, dann müsst derjenige natürlich damit rechnen dass ich die Vorgaben anpasse bzw. deutlicher formuliere. Was dann natürlich jeder lesen kann.

    Wobei ich versuchen kann eine Formulierung zu finden, die den "Trick" nicht verrät wegen dem die Frage aufgekommen ist.

    ---------------

    Was ich gleich vorwegnehmen kann: das Testsystem wird zur Bewertung noch modifiziert, und zwar in folgender Weise:

    1. Eventuell neue Test-Cases, die nicht vor Ende des Contest bekanntgegeben werden.
    2. Zumindest der Name des Namespace in dem das Testsystem liegt wird angepasst.
      Sinn: es sollen Brainfuck-Implementierungen verglichen werden, und nicht Programme die über Reflection/... versuchen das Testsystem zu bescheissen. 🙂

    Werde ich auch noch im Kopfbeitrag updaten vor dem offiziellen Start.

    0

  • UPDATE

    Es gibt zwei Änderungen:

    1. Ende bis 17. September verlängert. Beim eher mässigen Anklang den der Contest bisher gefunden hat, will ich auch nicht auf "nur" 1-2 zusätzliche Teilnehmer verzichten.
    2. Die genaue Signatur von "I.R" ist nicht mehr vorgeschrieben.

    Der Kopfbeitrag wurde entsprechend angepasst. Weiters hab' ich zwecks Übersichtlichkeit ein wenig umformatiert, und ein paar Unklarheiten beseitigt.

    Ein neues Testsystem gibt es auch:

    http://ideone.com/NkEMJ

    Das neue Testsystem enthält aber keine wesentlichen Änderungen, bloss ein paar zusätzliche Checks in der RunTest Funktion: Exceptions aus "I.R" werden kontrolliert gefangen und als Fehler gewertet, und es wird erstmal gecheckt ob überhaupt eine passende Funktion "R" gefunden wurde, bevor diese "invoked" wird. Also kein Grund zur Panik.

    0

  • Achja, ich kann natürlich nicht gut etwas "mir selbst einreichen", nachdem ich schon andere Beiträge bekommen habe. Das wäre nicht so wirklich ganz fair 😃

    Daher werde ich mit meinem aktuellen Stand teilnehmen (bzw. falls ich bis Sonntag Abend noch was krüzeres hinbekomme dann damit).

    Interpreter_1_1252.cs (Source in Codepage 1252):

    SHA-256 = 9bda27b6d64fb9032ac3db270b0101d49424e1251ce332495fca1ea484421e5c
    Länge verrate ich natürlich noch nicht 🙂

    http://www.webutils.pl/index.php?idx=sha1
    http://www.xorbin.com/tools/sha256-hash-calculator

    0
Anmelden zum Antworten