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

** Brainfuck Interpreter Contest ** [abgeschlossen]

  • ?

    hustbaer schrieb:

    µ schrieb:

    Stellst Du noch ein Testsystem für die Rahmenbedingungen zur Verfügung?

    Falls ich Zeit habe.
    Ist aber schwierig auch nur ne halbwegs gute Testabdeckung zusammenzubekommen. Je nach Code könnte es vorkommen dass nur eine bestimmte Kombination aus Faktoren das Fehlverhalten triggert. Und alle Kombinationen aus Bandposition/Programmposition/Schleifen-Schachteltiefe/Zellenwert abzudecken ist so-gut-wie unmöglich (und auf jeden Fall unpraktikabel).

    Es geht um die Rahmenbedingungen und ich hätte mir das so vorgestellt: Aus z.B. Volkards "Sieben"-Progrämmchen baut man zur Laufzeit mit dem Stringbuilder ein Programm mit >= 2^20 Zeichen.
    Die Verarbeitung des char Zeichensatzes prüft man, indem man jedes nicht-Bf Zeichen in ein anderes Programm einbaut. Bleiben die Negativen Bandsymbole. Da reicht eigentlich ein kleiner Zähler: -[+]+++++++++++++++++++++++++++++++++++++++++++++++++.
    Hier muss '1' rauskommen. Wenn '0' da steht hat man die Schleifenbedingung nur für Zahlen >= 0 korrekt geprüft und die negativen Zahlen vergessen. So wie ich vorhin.

    Ich kann am Sonntag vielleicht was bauen und dann hier veröffentlichen.

    0
  • ?

    TyRoXx schrieb:

    Wenn überhaupt sollte das Verschachtelungslimit höher liegen, mindestens bei 2^10. Das müsste C# doch schaffen, oder?

    C# wirft bei 12k oder 13k rekursiven Aufrufen ohne Übergabeparameter eine StackOverflowException. Zumindest auf meinem System.

    Ich schließe mich an: Im Sinne rekursiver Funktionen sollten wir die Verschachtelungstiefe auf 1024 begrenzen.

    0
  • V

    hustbaer schrieb:

    Was schreiben denn andere Sprach-Standards für minimale Callstack-Tiefe vor, z.B. der C oder C++ Standard?

    C++
    Nesting levels of compound statements, iteration control structures, and selection control structures [256].
    Nesting levels of parenthesized expressions within a full-expression [256].

    0
  • V

    TyRoXx schrieb:

    Hmm, ich bin noch nicht richtig überzeugt. Es gibt unendlich viele Möglichkeiten, ein ineffizientes Programm zu schreiben, und die rekursiven Schleifen mit dem eingebauten stack overflow sind nur eine davon.

    Aber [ und ] müssen zueinanderpassen, wie { und } oder ( und ) in C#. Wo kannst Du Dir in einem C#-Programm mehr als 99 Verschachtelungen von () oder {} denken? WOhlgemerkt, daß wären welche, die der Programmierer alle getippt hat! Es hat nichts damit zu tun, daß man tiefe "rekursive Schleifen" programmieren kann.

    Hier geht es nur um die Frage, wie tief ein Compiler absteigen können muß, um ein Stück Code zu verarbeiten.

    TyRoXx schrieb:

    Wenn überhaupt sollte das Verschachtelungslimit höher liegen, mindestens bei 2^10. Das müsste C# doch schaffen, oder?

    Ja, egal. 2^10, 2^8, 99, es ist praktisch kein Unterschied. Wenn man einen Wert davon schafft, hat man es vermutlich so allgemein programmiert, daß es leicht für andere Werte umgefrickelt werden kann.

    0

  • OK.
    Dann würde ich 256 vorschlagen.

    0
  • Administrator

    hustbaer schrieb:

    Dann würde ich 256 vorschlagen.

    Habe ich nichts dagegen. Ist aber natürlich blöd, während dem laufenden Contest noch Änderungen nachzureichen. Aber gut ... so extrem schlimm auch wieder nicht, ist ja auch nicht ein extrem wichtiger Contest 😃

    Grüssli

    0

  • Ja, ist doof. Andrerseits ist das Argument von volkard gut, dass man in C# auch keine Callstack-Tiefe von 1<<19 hinbekommt.

    Ich warte einfach noch was die anderen Teilnehmer schreiben.

    Die anderen von TyRoXx vorgeschlagenen Änderungen mach' ich auf jeden Fall nicht, die wären etwas zu krass.

    0
  • T

    hustbaer schrieb:

    Die anderen von TyRoXx vorgeschlagenen Änderungen mach' ich auf jeden Fall nicht, die wären etwas zu krass.

    Die sind vor allem nicht ernst gemeint.

    0
  • ?

    @hustbaer
    Hast Du mal geprüft ob deine 227 den Anforderungen stand hält? Speziell auch das kleine Programm in diesem Beitrag: http://www.c-plusplus.net/forum/p2116925#2116925

    0
  • K

    verschachtelte Schleifen muß der Programmierer reingeschrieben haben

    Nein, muss er nicht. Programme koennen auch generiert werden. Gerade bei so einer einfachen Sprache wie Brainfuck.

    Das habe ich noch nicht erlebt.

    Ich habe mir generierten Quelltext angesehen, bei dem es so war.

    Ich kann mir denken, warum ihr ueber die Stacktiefe heult. Nun dann funktioniert eben der Rekursionstrick nicht. Ich habe mal schnell einen Brainfuck-Interpreter in C++ geschrieben und er kommt ohne Rekursion aus und kann mit dem Extrembeispiel von Dravere problemlos umgehen.

    Und warum soll hier 1 rauskommen?

    -[+]+++++++++++++++++++++++++++++++++++++++++++++++++.
    0
  • ?

    @knivil
    Die bisherigen Lösungen können auch mit extremer Verschachtelung umgehen. Es geht darum, rekursive Lösungen zu ermöglichen. Bringen wirds imho aber nichts. Funktionssignaturen sind zu "verbose".

    0
  • ?

    knivil schrieb:

    Und warum soll hier 1 rauskommen?

    -[+]+++++++++++++++++++++++++++++++++++++++++++++++++.

    ASCII 49 = '1'

    Es ist ein simpler Test, ob man die Schleifenbedingungen für negative Zahlen abgefangen hat.

    0
  • V

    knivil schrieb:

    Das habe ich noch nicht erlebt.

    Ich habe mir generierten Quelltext angesehen, bei dem es so war.

    Wozu hat der so viele Blöcke verschachtelt?

    0
  • K

    Keine Ahnung, frag doch die von der modellgetriebenen Softwareentwicklung. Und ich denke mit Templates in C++ kriege ich das auch hin.

    0
  • V

    knivil schrieb:

    Und ich denke mit Templates in C++ kriege ich das auch hin.

    Ja, 1000 Funktionen kriegt man hin.
    Wie mir gerade auffällt, erhöhen die nicht den Stackbedarf des Compilers, wie es 1000 Blocks tun würden.

    knivil schrieb:

    Keine Ahnung, frag doch die von der modellgetriebenen Softwareentwicklung.

    1000 Funktionen, ok. Nicht 1000 Blocks.

    edit: Vielleicht 1000 verschachtelte if-Verzeigungen.

    if(n%2!=0) 
    if(n%3!=0) 
        if(n%5!=0) 
... 
                             ...if(n%65537!=0) 
                                    cout<<n<<" ist eine Primzahl.\n";
    0

  • µ schrieb:

    @hustbaer
    Hast Du mal geprüft ob deine 227 den Anforderungen stand hält? Speziell auch das kleine Programm in diesem Beitrag: http://www.c-plusplus.net/forum/p2116925#2116925

    Nein.
    Werde ich aber natürlich noch.

    0

  • Es gibt neue Tests, darunter welche für negative Zellenwerte, Schleifen-Schachteltiefe und Kommentare:

    http://www.c-plusplus.net/forum/p2113680#2113680

    Den rot13 hab' ich probiert aber nicht zum Laufen bekommen. Der scheint nicht zu terminieren. Falls ihn jmd. zum Laufen bekommt, bitte melden wie.

    "99 bottles" ist mir zu lange (der Output).

    0

  • hustbaer schrieb:

    µ schrieb:

    @hustbaer
    Hast Du mal geprüft ob deine 227 den Anforderungen stand hält? Speziell auch das kleine Programm in diesem Beitrag: http://www.c-plusplus.net/forum/p2116925#2116925

    Nein.
    Werde ich aber natürlich noch.

    Hmpf.
    Kackt natürlich ab.

    Aber was solls.
    +1 (fix)
    -2 (weil's sonst fad wird)
    macht

    Interpreter_8_1252.cs, 226 Zeichen

    SHA-256 = 8f307069b911c7225c5bc67e6c64ac218662f27f56d66272deabcfe18db0a3cc

    0

  • @µ
    Und wie sieht's bei dir mit den neuen Tests aus?

    BTW: deinen kleinen "1" Test schafft natürlich auch mein "falscher" 227er. Nur einen meiner neuen Test-Cases nicht 🤡

    0

  • Vielleicht könnten nochmal alle Teilnehmer schreiben was sie als minimal geforderte Schleifen-Schachteltiefe haben wollen (ohne lange Diskussionen wenn möglich 🤡 ). Dann kann ich mich nach der Mehrheit richten, und passe die Beschreibung + die Tests entsprechend an.

    0
Anmelden zum Antworten