** Brainfuck Interpreter Contest ** [abgeschlossen]

hustbaer

µ schrieb:

Ich hätte mir einen (sinnlosen) Rückgabewert bei der S.W() Funktion gewünscht. Dieses Monster war sonst nirgends unterzubringen.

Ach, was ich mir nicht alles gewünscht habe während des Contest
Die Regel dass sämtliche Kommentare ignoriert werden müssen war z.B auch halbwegs "lästig" - ASCII 0-127 hätte da einiges erleichtert.

@Bashar
Zu meiner Schande muss ich gestehen, dass ich bisher ebenfalls Oktal-Literale wie in C++ vermutet habe. Noch nie benötigt bisher.

@hustbaer
Stimmt. Den Cast habe ich nicht bedacht.

Die Kommentare habe ich nicht als lästig empfunden. Spontan weiß ich nicht, was ASCII 0-127 für erhebliche vorteile bringen würde. Habe nie darüber nachgedacht.

EDIT: Und ja, wie gesagt. Deinen Code zerpflücke ich morgen. Ist mir heute Abend zu viel

Dieser Thread ist bei Google auf Position 7 bei dem Suchbegriff "Brainfuck Interpreter".

Wir hinterlassen der Welt nichts Gutes

hustbaer

Bei mir is der auf Platz 30 (google.com) bzw. Platz 40 (google.de)...
(Liegt vielleicht daran dass ich als "Hauptsprache" in meinem Browser Englisch eingestellt hab...)

Bashar

µ schrieb:

Interessant: Niemand konnte 65536 bzw 1<<16 oder eine größere Zahl mit weniger als 5 Zeichen darstellen. Ich vermute irgendeine geschickte Lösung mit Überlauf.... habe sie aber nicht gefunden.

~0u ist mir eingefallen, aber das ist dann wieder zuviel.

~0u !

ich sollte mir mal eine Tabelle mit Literalen einprägen.

(google liefert regional sehr unterschiedliche Suchergebnisse. Kein Wunder bei einer Million Servern)

Dummie

class I_Nice
{
    int[] m = new int[1 << 16];
    int n = 0, z, c;

    public void R(S s, int p = -1, int r = 2)
    {
        while ((z = ++p) < s.P.Length && (c = s.P[p] - 40) != 53)
        {
            if (c == 51)
                if (m[n] != 0)
                    R(s, p--);
                else
                {
                    R(s, p, 0);
                    p = z;
                }

            if (r > 0)
            {
                m[c == 20 || c == 22 ? n -= 21 - c : n] += c == 3 || c == 5 ? 4 - c : 0;

                if (c == 6)
                    s.W(m[n]);

                if (c == 4)
                    m[n] = s.R();
            }
        }
    }
}

m = Speicher
n = Position im Speicher m
z = "Rückgabewert" bei rekursiven Aufruf
p = Stelle des aktuellen Zeichen
c = Aktuelles Zeichen
r [Funktionsparameter] = Code ausführen oder "Suchlauf" (Flag)

Zunächst werden alle Zeichen als Zahlen abgebildet, da 'x' länger ist als eine zweistellige Zahl. Um einige Zeichen noch kürzer darstellen zu können, wird 40 subtrahiert.
So ist das Zeichen [ nun 6 und ] ist 4.

Da diese Zeichen fast nebeneinander liegen kann man durch Subtraktion der Paare herausfinden, ob man addieren oder subtrahieren muss.

Dieser Trick wird hier gleich 2x angewendet:

m[c == 20 || c == 22 ? n -= 21 - c : n] += c == 3 || c == 5 ? 4 - c : 0;

Ansonsten ist das Programm nichts besonderes, aber das hatte ich ja bereits am Anfang erwähnt

314159265358979

Wie ihr die []-Behandlung so kurz hinbekommen habt ist genial. Ich hatte da verschachtelte Schleifen, auch wenns sowieso nicht funktioniert hat.

GPC

Ich möchte mich an der Stelle noch mal bei hustbaer bedanken, der sich hier wirklich reingehängt hat, ein tolles Testsystem hochgezogen hat und die ganze Geschichte betreute!

GPC schrieb:

Ich möchte mich an der Stelle noch mal bei hustbaer bedanken, der sich hier wirklich reingehängt hat, ein tolles Testsystem hochgezogen hat und die ganze Geschichte betreute!

Dem schließe ich mich an. Vielen Dank dafür.

µ schrieb:

Interessant: Niemand konnte 65536 bzw 1<<16 oder eine größere Zahl mit weniger als 5 Zeichen darstellen. Ich vermute irgendeine geschickte Lösung mit Überlauf.... habe sie aber nicht gefunden.

» ~0u «?

freaky

Bashar schrieb:

~0u ist mir eingefallen, aber das ist dann wieder zuviel.

Zeus

Wird der Code auch veröffentlicht?

Blätter mal ein paar Seiten zurück

hustbaer

Zeus schrieb:

Wird der Code auch veröffentlicht?

Ich hab im Kopfposting nen Link auf das Ergebnis gemacht, die einzelnen Beiträge kommen gleich danach (durchsetzt mit ein paar Zwischenrufen :)).

hustbaer

Irgendwer wollte aus den abgegebenen Beiträgen den kürzesten Interpreter basteln...

Ich wollte nur sagen: für mich ist die Sache hier beendet, rechnet nicht damit dass ich da nochmal was ankurble (hab' im Moment keine Zeit/keine Lust mich um sowas zu kümmern).

hustbaer

Nochwas...

Hätte jemand Interesse an einem 2. Brainfuck Contest?

Ziel: die schnellste Brainfuck-Implementierung.
(Auf die Ausführungszeit eines BF Programms bezogen, Interpreter/Compiler/JITer egal, bei Compiler/JITer müsste man dann nur festlegen ob die Compilezeiten mitgerechnet werden).

Einzig die Wertung wäre dabei nicht ganz trivial. Man könnte wieder ein Testsystem basteln das bestimmte Benchmarks durchführt. Dann müsste man noch festlegen auf welcher Hardware getestet wird, und irgend ein ausreichend vertrauenswürdiger User der so ein System hat, müsste die Benchmarks machen und die Ergebnisse posten.

Zwischenergebnisse könnte man auf dem eigenen System ermitteln, und die Zeiten dann relativ zu einer vorgegebenen Referenzimplementierung angeben.

Bzw. wenn jemand eine andere Idee für nen Contest hat immer her damit (aber dann vielleicht besser in einem eigenen Thread). Wichtig wäre dass sich der Aufwand im Rahmen hält, denn sonst wird kaum jemand mitmachen.

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.

hustbaer

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.

TyRoXx

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?