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

** Brainfuck Interpreter Contest ** [abgeschlossen]


  • noptimizer schrieb:

    Die Zeit zu messen ist unmöglich. Der eine kompilliert den BF-Code und seine Lösung ist bei vielen Schleifen die beste und der andere interpretiert ihn und ist bei Hello-World-Programmen schneller. Somit hängen die Punkte direkt von den Tests ab.

    Äh. Ja. Und?
    Wodurch wird da jetzt irgendwas unmöglich? 😕

    Dass mit "grossen dicken" Programmen gemessen wird, die ordentlich viel Schleifen drin haben, ist für mich schonmal klar.

    0
  • T

    Außerdem könnte man Compiler und Interpreter getrennt messen.
    Ihr wollt das aber nicht mit C# machen, oder? C++ scheint mir da viel geeigneter. Warum überhaupt C# beim letzten Contest?

    0
  • ?

    TyRoXx schrieb:

    Warum überhaupt C# beim letzten Contest?

    Weils ne geile Sprache ist und das Forum Raum für Contests in mehr als nur einer Sprache hat 👍

    @hustbaer
    Ich bin für einen neuen Contest und wollte schon einen Thread zwecks Ideensuche starten. Deinen Vorschlag finde ich aber weniger gut. Es wäre ein blinder Contest, man wüsste nicht wie gut die anderen Teilnehmer bereits sind. Die Randbedingungen zu definieren wäre schwierig. Bleibt man bei C#? Darf Assembler-Code generiert werden? Wenn ja, steht ein Linker & Assembler zur Verfügung?

    Ich weiß nicht. Lieber zu Hause bleiben und eine nette Aufgabe finden, die mit reinen C#-Mitteln zu lösen ist und den Wettbewerbscharakter der Zwischenlösungen erfüllt.

    0

  • Also ich finde C# wäre da perfekt geeignet.

    Parsen, optimieren, IL-Code generieren, JITen, ausführen. Ich wüsste, bis auf Java, jetzt keine Sprache/Plattform, wo das so problemlos und ohne gefrickel geht wie in C#.

    Es wäre ein blinder Contest, man wüsste nicht wie gut die anderen Teilnehmer bereits sind.

    Naja, nicht ganz.

    Man könnte z.B. posten dass der eigene Interpreter/Compiler die vorgegebenen Tests N mal schneller als die vorgegebene Referenz-Implementierung ausführt.

    Klar werden da auch bei unterschiedlicher Hardware unterschiedliche Faktoren rauskommen, aber naja.

    Aber egal. Man muss ja nicht alles unbedingt ein 2. mal aufkochen 🙂

    Mach einen Thread zur Ideen-Suche auf, ich finde die Idee weitere Contests zu veranstalten auf jeden Fall gut!
    Wenn ich Zeit habe, und es sich vom Aufwand her im Rahmen hält, dann kann ich auch wieder die Leitung übernehmen.

    0
  • V

    Ich sehe da zwei verschiedene Dinge.

    - Den schnellsten Interpreter.

    - Den schnellsten Compiler, wo die Laufzeit des Compilers nicht gewertet wird (solange unter 60 Minuten oder so). Da würde der Optimierer gewinnen, der aus [>+>+<<-] ein while(band[kopfpos]){++kopfpos;++band[kopfpos];++kopfpos;++band[kopfpos];--kopfpos;--kopfpos;--band[kopfpos];}
    oder besser band[kopfpos+1]+=band[kopfpos];band[kopfpos+2]+=band[kopfpos];band[kopfpos]=0; macht. Ausgabesprache des Compilers könnte erstmal C# sein. Klingt enorm aufwändig, vielleicht wäre das besser ein Gemeinschaftprojekt.

    0

  • volkard schrieb:

    Da würde der Optimierer gewinnen, der aus [>+>+<<-] ein while(band[kopfpos]){++kopfpos;++band[kopfpos];++kopfpos;++band[kopfpos];--kopfpos;--kopfpos;--band[kopfpos];}
    oder besser band[kopfpos+1]+=band[kopfpos];band[kopfpos+2]+=band[kopfpos];band[kopfpos]=0; macht. Ausgabesprache des Compilers könnte C# sein. Klingt enorm aufwändig, vielleicht wäre das besser ein Gemeinschaftprojekt.

    Naja, ich hätte da schon ein paar Ideen 🙂

    Das Beispiel das du da zeigst, sollte sich ohne wirklich grossen Aufwand zum gewünschten Output optimieren lassen.

    0
  • ?

    Das erste Beispiel ist nur eine String-Ersetzung. Jeder optimierte Code benötigt aber wohl direkt einen Syntaxbaum auf dem man arbeiten kann.

    Das ist interessant aber einfach zu viel für einen kleinen Contest.

    0
  • G

    Ich würde mich höchstwahrscheinlich auch an einem neuen Contest beteiligen 👍
    Aber ich denke dass ein "Schnellster BF Compiler/Interpretet" nicht gerade die ideale Aufgabe ist. Zumindest mich würde es nicht reizen, denn will man es richtig machen, muss man einiges an Arbeit reinstecken.

    0
  • ?

    Wir braeuchten wieder irgendwas kurzes knackiges. Von mir aus wieder die gleichen Bedingungen, nur diesmal nen anderer Satz von Befehlen. Vielleicht irgendwas in Richtung Formeln mit Grundrechenarten etc.

    0
  • R

    KasF schrieb:

    Wir braeuchten wieder irgendwas kurzes knackiges. Von mir aus wieder die gleichen Bedingungen, nur diesmal nen anderer Satz von Befehlen. Vielleicht irgendwas in Richtung Formeln mit Grundrechenarten etc.

    Taschenrechner Programmieren wäre langweilig. Wenn dann Minimum / Integral / Steigung (arithmetisch oder numerisch). Sonst SAT-Solver möglichst kurz (vorher Eingabeformat festlegen).

    0
  • B

    Einen Brainfuck-Compiler fände ich persönlich ziemlich interessant als Übungsprojekt. Für einen Contest ist es vielleicht ein bisschen viel.

    hustbaer schrieb:

    Parsen, optimieren, IL-Code generieren, JITen, ausführen. Ich wüsste, bis auf Java, jetzt keine Sprache/Plattform, wo das so problemlos und ohne gefrickel geht wie in C#.

    Wenn ich das richtig sehe, geht das über System.Reflection.Emit. Kommt man da mit der MSDN aus oder gibt es irgendwas anderes nützliches, was man sich anlesen sollte?

    0
  • R

    Bashar schrieb:

    Einen Brainfuck-Compiler fände ich persönlich ziemlich interessant als Übungsprojekt. Für einen Contest ist es vielleicht ein bisschen viel.

    hustbaer schrieb:

    Parsen, optimieren, IL-Code generieren, JITen, ausführen. Ich wüsste, bis auf Java, jetzt keine Sprache/Plattform, wo das so problemlos und ohne gefrickel geht wie in C#.

    Wenn ich das richtig sehe, geht das über System.Reflection.Emit. Kommt man da mit der MSDN aus oder gibt es irgendwas anderes nützliches, was man sich anlesen sollte?

    Es gehen drei Wege um dynamischen Code zu generieren:

    • System.Reflection.Emit (IL-Code): Ist am schwierigsten, da eigene Sprache, aber man hat die meiste Kontrolle über die Sprache. (siehe Assembler-Begründungen)
    • System.Codedom: Kann man eigenen Code als String einer .Net Sprache wie VB.Net, JScript oder C# compilieren, oder (fast) sprachenunabhängig Code über den jeweiligen Compiler der generieren, (es wird noch eine Sprache gebraucht die aus dem DOM Quelltext erzeugt). Dies wird bei XML-Serialiserung und offensichtlich vom WinForms-Designer verwendet.
    • System.Linq.Expressions (ab .Net 3.5 eingeschrängt und ab 4.0 vollständig): Ähnlich wie System.Codedom nur leichtgewichtiger und ohne umwege über einen Compiler und kann direkt Delegates zurückliefern.

    IL ist wie gesagt eine "eigene" Sprache und mächtiger als C# (ref return & multi indices & properties other_method). Ich vermute mal, dass Assembler für das Verständnis hilft, wobei IL eben ausschließlich stackbasiert ist.

    Außerdem kann man auch vorhanden Code via Reflector Ildasm oder ILSpy anschauen und beim letzteren mit dem Originalen vergleichen.

    Edit:
    Fürs weiterlesen:
    Verwalteter Code hinter den Kulissen, Teil 1

    0
  • ?

    Wie wäre es mit einem Primzahltester in Malbolge als Contest? Laufzeit: 4 Jahre 😉

    Irgendwas in Richtung Mathe-Parser, Solver, was weiß ich wäre schon interessant. Jetzt heißt es eine kleine, knackige und gut optimierbare Aufgabe zu finden.

    Rhombicosidodecahedron schrieb:

    Sonst SAT-Solver möglichst kurz (vorher Eingabeformat festlegen).

    Erster Gedanke: Das ist doch eine geile Idee!

    Etwas weiter überlegen:
    SAT-Solver sind beliebig komplex. Es würde wohl auf Durchprobieren aller Belegungen hinauslaufen. Aber ok, ein naiver Brainfuck-Interpreter kostet auch keine Hirnzellen. Die Aufgabe bestünde wieder im Verkürzen von Code. Hmmm...

    0
  • ?

    Sobald die Aufgabe in Richtung Optimierung der Laufzeit geht, sollte es kein bekanntes Problem sein. Beispiel Primzahltester: Dann packe ich meine alten Skripte aus, implementiere den besten Algorithmus und fertig. Das ist nichts.

    Wie wäre es mit sehr einfachen Bots die in irgendeiner Form gegeneinander antreten?

    0
  • F

    µ schrieb:

    Wie wäre es mit sehr einfachen Bots die in irgendeiner Form gegeneinander antreten?

    Daran hätte ich auch Interesse.

    0
  • R

    So in der Art?
    http://en.wikipedia.org/wiki/Core_War

    0
  • ?

    Sowas wie Core-War, ja.

    Das würde Einarbeitung erfordern (ich kenne mich auch noch nicht damit aus), oder wir arbeiten ein eigenes kleines Bot-Framework aus. Es könnte ja sehr einfach anfangen und im Laufe der Zeit erweitert werden.

    0
  • V

    Optimalerweise kann so ein Contest ohne Ende sein. Es gibt halt eine laufend aktualisierte Rangliste. Und

    Core-War ist Core-War. Man proggert da in Redcode. Nicht in C#.

    Gut ist Colobot bzw Ceebot. Extrem gut. Aber das Framework zu basteln, würde wohl den Rahmen sprengen.

    Mein liebstes Game wäre wohl http://en.wikipedia.org/wiki/Classic_Empire_(video_game) , da hat mir immer gefehlt, daß man ein wenig Scripten kann.

    Sehr hübsch als Basis wäre auch http://www.windowsgames.co.uk/slay.html
    Derselbe Autor haut auch ein klassisches Empire raus http://www.windowsgames.co.uk/mother.html

    Spannend fände ich, das http://en.wikipedia.org/wiki/Prisoner's_dilemma aufzusetzen. Extrem einfaches Framework. Und ich würde gerne wissen, on Tit For Tat wirklich so gut ist. Mir scheint, die Forschung ist dahingehend eingeschlafen.

    0
  • 3

    Vielleicht irgend ein Kartenspiel?

    Edit: Achja, bitte mal irgendwas, wo ich auch ne Chance habe, da Programm mal hinzubekommen 😃

    0
  • Administrator

    Mathematische Probleme in eingeschränkter Zeit mit bestmöglichem Ergebnis zu lösen sind auch immer wieder nette Aufgaben. Zum Beispiel gab es doch letzten was bei Spieleprogrammierer.de, wo eine Karte bestmöglichst in Nord und Süd aufgeteilt werden musste.
    http://www.spieleprogrammierer.de/32-programmier-contests/16101-14-planetenteilung-spezial-14-08-2011/

    Hauptproblem bei Contests ist halt immer dasselbe. Irgendwer muss es organisieren und das kostet meistens Zeit. Und am Ende wird es oft nicht mal gebührend geschätzt 😉

    Grüssli

    0
Anmelden zum Antworten