** Brainfuck Interpreter Contest ** [abgeschlossen]
-
0.2) hustbaer - 220
class I{int i,p,n;public void R(S z){var m=new int[1<<16];for(;i<z.P.Length;i+=n<0?-1:1){int c=z.P[i]-92,a=m[p];n-=n==0&a==0!=c<0|c*c!=1?0:c;c=c+48^n<<16;m[p+=c>15&c<19?c-17:0]-=c==0?a-z.R():c*c==1?c:0;if(c==2)z.W(a);}}} class I_Nice { int i, p, n; public void R(S z) { var m = new int[1 << 16]; for (; i < z.P.Length; i += n < 0 ? -1 : 1) { int c = z.P[i] - 92, a = m[p]; n -= n == 0 & a == 0 != c < 0 | c * c != 1 ? 0 : c; c = c + 48 ^ n << 16; m[p += c > 15 & c < 19 ? c - 17 : 0] -= c == 0 ? a - z.R() : c * c == 1 ? c : 0; if (c == 2) z.W(a); } } }Auch eine "klassische" 1-Schleifen-Lösung.
Das ist die letzte Variante für die ich nen Hashcode gepostet hatte (Interpreter_9_1252.cs).
Erklärung folgt gleich in Form der kommentierten 218 Zeichen Version (ist bis auf zwei dumme Oversights genau das selbe).
-
0.3) hustbaer - 218
class I{int i,p,n;public void R(S z){for(var m=new int[1<<16];i<z.P.Length;i+=n<0?-1:1){int c=z.P[i]-92,a=m[p];n-=n==0&a==0!=c<0|c*c!=1?0:c;c+=48^n<<16;m[p+=c>15&c<19?c-17:0]-=c==0?a-z.R():c*c==1?c:0;if(c==2)z.W(a);}}} class I_Nice { // Wir machen Member. Das spart das "=0" das wir bei lokalen Variablen bräuchten. // (Dadurch kann R() zwar nichtmehr ein 2. mal mit einem neuen Programm aufgerufen werden, // aber das war auch nicht gefordert :-) int i, // Der "instruction pointer" p, // Der "data pointer" n; // Der "nesting counter" // Der "nesting counter" wird zum Suchen der passenden [ oder ] verwendet. // "[" werden als +1 gezählt, "]" als -1 // n == 0 => "normal mode" - Normale Programmausführung // n < 0 => "+skip mode" - wir suchen die passende [ zu einer gefundenen ] (rückwärts) // n > 0 => "-skip mode" - wir suchen die passende ] zu einer gefundenen [ (vorwärts) public void R(S z) { for (var m = new int[1 << 16]; // Der Speicher. Wir sparen 1x ";" wenn wir den hier anlegen statt vor der Schleife (das ist das verschenkte Zeichen, hihi) i < z.P.Length; // Sollte klar sein :) i += n < 0 ? -1 : 1 // Anpassen des "instruction pointer": rückwärts wenn wir im "-skip mode" sind, sonst vorwärts ) { int c = z.P[i] - 92, // 92 abziehen, damit wir unten Tricks wie "c * c == 1" verwenden können a = m[p]; // Wert der aktuellen Zelle kopieren, damit wir 3x "a" statt 3x "m[p]" schreiben können // Als erstes passen wir mal den "nesting counter" an. // Dazu müssen wir folgendes machen: // // Im "normal mode": // Wenn eine [ oder ] gefunden wurde UND der Wert der aktuellen Zelle "passt", dann müssen wir // in den "skip mode" wechseln. // (Zu [ "passt" 0 und zu ] "passt" alles ausser 0) // Dazu "zählen" wir einfach die [ bzw. ] ganz normal (siehe oben), dadurch wird n != 0. // Im "skip mode": // Jede [ oder ] muss gezählt werden // Wenn wir dabei n == 0 erzeugen verlassen wir den "skip mode". Das ist gut so, // weil n == 0 bedeutet dass wir das Ziel erreicht haben. // // Die "Zählung" einer [ oder ] erfolgt also immer gleich, wir müssen nur gucken OB wir zählen müssen. // // Momentan ist "c" so eingestellt, dass // '[' c == -1 (91 - 92) - "Wert" dieser Klammer ist "+1" (also "-c") // ']' c == 1 (93 - 92) - "Wert" dieser Klammer ist "-1" (also "-c") // // Um zu testen ob c -1 oder 1 ist können wir c * c == 1 schreiben. // (Lässt sich beweisen dass das für alle 32 Bit Zahlen trotz Überlauf gilt, // da ich für so nen Beweis aber zu doof bin, hab ich's einfach ausprobiert :D) // // Wenn also c * c == 1, dann ist der "Wert" der aktuellen Klammer gleich "-c" (s.o.) // // Um zu entscheiden ob wir zählen müssen verwenden wir folgende Bedingung: // // ( (n != 0) || ((a == 0) == (c < 0)) ) && (c * c == 1) // // Erklärung ("(c * c == 1)" vorgezogen, zur besseren Verständlichkeit): // // (c * c == 1) es ist eine Klammer // && UND // ( ( // (n != 0) wir sind im "skip mode" // || ODER // ((a == 0) == (c < 0)) der Wert der Zelle passt zur Klammer // (das "Null sein" der aktuellen Zelle gleicht dem "[ sein" der Klammer ^^) // ) ) // // Das setzt also die oben beschriebenen Regeln um. // // Blöderweise bräuchten wir da aber zwei Klammern wenn wir das so 1:1 hinschreiben wollen, // da die Operator-Precedence nicht "passt" wenn wir alle Klammern wegnehmen. // Daher formen wir die Bedingung einfach um, nach // A && B => !(!A || !B) // A || B => !(!A && !B) // // So erhalten wir: // // !( ( !(n != 0) && !((a == 0) == (c < 0)) ) || !(c * c == 1) ) // // Bis auf das erste "!" können wir alle loswerden, indem wir == zu != verwandeln (und umgekehrt), und dafür das ! streichen // Und das erste werden wir noch los, indem wir später den "if" und "else" Teil vertauschen: // // ( ( (n == 0) && ((a == 0) != (c < 0)) ) || (c * c != 1) ) // // Jetzt machen wir noch aus && ein einfaches & und aus || ein einfaches |. // ("bool | bool" ist das selbe wie "bool || bool", nur ohne short-circuit Semantik, der 2. Ausdruck wird also immer ausgewertet. // Das selbe nochmal für "bool & bool") // Macht: // ( ( (n == 0) & ((a == 0) != (c < 0)) ) | (c * c != 1) ) // // Und jetzt nehmen wir noch alle Klammern weg, und gucken was passiert: // // n == 0 & a == 0 != c < 0 | c * c != 1 // // TADAA, funktioniert :) // // BTW: das spart genau EIN Zeichen, denn in der Original-Version hätten wir // "a == 0 ^ c < 0" statt "a == 0 != c < 0" schreiben können, und auch nur ein Klammerpaar gebraucht xD n -= n == 0 & a == 0 != c < 0 | c * c != 1 ? 0 : c; // Achja, "-=" statt "+=" machen wir, weil wir so einfach "? 0 : c" statt "? 0 : -c" schreiben können. // Gut, weiter... // Wenn wir im "skip mode" sind, dann wollen wir alles bis auf [ und ] ignorieren. // Wenn wir im "normal mode" sind, dann nicht :) // // Wir könnten nun natürlich "if (n == 0) {}" oder sowas schreiben, aber das geht kürzer! // Und zwar indem wir den Wert von c "kaputtmachen" wenn n != 0. // (d.h. so verändern, dass kein gültiger Opcode mehr erkannt werden kann, egal was das Input-Zeichen war) // // Und es gibt noch weitere "benachbarte" Zeichen die wir ausnutzen können, also "verschieben" // wir "c" auch nochmal. Und zwar um 48. Für einen weiteren "c * c == 1" Trick. // // Das können wir beides in einem Statement machen, und zwar indem wir (48 ^ n << 16) auf c draufaddieren. // // Der (n << 16) Teil ist im "normal mode" immer 0, d.h. da geht nix kaputt. // Und im "skip mode" ist der Betrag von (n << 16) immer ausreichend gross, so dass // sämtliche gültigen Input-Zeichen (inklusive Kommentare) ausreichend weit "verschoben" werden, // dass kein Opcode mehr erkannt wird. // (Das funktioniert allerdings nur bis zu einer Schachteltiefe von ~ 32K, was nach der // Anpassung/Klarstellung der Regeln aber mehr als genug ist, hihi.) c += 48 ^ n << 16; // Bleibt nur noch... // - Den "data pointer" anzupassen // - Den aktuellen Zellenwert anzupassen // - Input lesen // - Output schreiben // Momentan ist "c", nach der neuerlichen Verschiebung, so eingestellt, dass // '<' c == 16 (60 - 92 + 48) // '>' c == 18 (62 - 92 + 48) // '+' c == -1 (43 - 92 + 48) // '-' c == 1 (45 - 92 + 48) // '.' c == 2 (46 - 92 + 48) // ',' c == 0 (44 - 92 + 48) // Bis auf Output schreiben lässt sich das wieder in einem einzigen Statement machen... // // Wenn c im Bereich (15 ... 19) liegt (exklusive), ist der "data pointer" anzupassen, und zwar um "c - 17" // (Spezialfall: c == 17 entspricht keinem Opcode, aber da c - 17 == 0 ist das egal): // // p += c > 15 & c < 19 ? c - 17 : 0 // // Wenn c == 0, dann wollen wir lesen. // Ansonsten, wenn c -1 oder 1 ist, dann wollen wir den Zellenwert anpassen. // // Das können wir nun so zusammenfassen: m[ p += c > 15 & c < 19 ? c - 17 : 0 ] -= c == 0 ? a - z.R() : c * c == 1 ? c : 0; // "a - z.R()" ist ein netter Trick (den ich von µ abgeguckt habe, hihi), um das Lesen auch noch in // diese Zeile reinzupacken. // ("-=" statt "+=" wieder aus dem selben Grund wie beim "nesting counter".) // Und hier nun doch noch ein "if", zum Schreiben: // (k.A. wie ich dieses "if" wegbekommen könnte - alles was mir da sonst einfällt wäre viel länger) if (c == 2) z.W(a); } } }Die meisten die mitgemacht haben, werden die meisten der hier erklärten Dinge schon kennen bzw. auch ohne Erklärung verstehen. Vielleicht ist es aber für anderen interessant...
-
b = das Band.
p = pointer. Der Zeiger (Index) auf die aktuelle Zelle
i = Index auf das aktuelle Bf Token im Input-Code
n = Inhalt der aktuellen Zelle
j = Hilfvariable die das aktuelle Token (um einen bestimmten Wert verschoben) speichert
w = Zwei Modi. w==0 ist die normale Ausführung. D.h. + - > < . und , werden bearbeitet. w!=0 ist ein Vor- oder Rücklauf über eine Schleife. Dabei ist w>0 ein Lauf vorwärts und w<0 ein Lauf rückwärts. In diesem Zustand speichert w das doppelte (weil kürzerer Code)der Differenz der öffnenden und schließenden Klammern bis der Wert wieder =0 ist und der normale Ausführungsmodus wieder aufgenommen werden kann.class I_Nice { public void R(S S) { var b = new int[1 << 16]; for (int p = 0, i = 0, w = 0, n = 0, j; i < S.P.Length; i += w < 0 ? -1 : 1) if (0 == (w += (j = 92 - S.P[i]) * j == 1 ? j + (w == 0 ? n != 0 ? -1 : 1 : j) : 0)) { if (j == 46) S.W(n); n = b[p -= (j -= 31) * j == 1 ? j : 0] += (j -= 17) * j == 1 ? j : j == 0 ? S.R() - n : 0; } } }Interessante Punkte bei if (0 == (w += (j = 92 - S.P[i]) * j == 1 ? j + (w == 0 ? n != 0 ? -1 : 1 : j) : 0))
-
wenn w==0 wird der normale Modus ausgeführt
-
Das Token wird zuerst in j = 92 - S.P[i] kodiert. Da '['=91 und ']'=93 ist j bei einem Klammersymbol -1 oder 1. Damit ist j*j == 1. Falls j*j == 1 wird der Schleifentiefezähler um den Summanden j + (w == 0 ? n != 0 ? -1 : 1 : j) angepasst, sonst wird nichts dazugezählt. Dieser Ausdruck führt dazu, dass der Zähler erhöht oder erniedrigt wird, falls ein Lauf bereits im Gange ist (w!=0). Außerdem startet dieser Zähler einen Lauf nach vorne, wenn das aktuelle Bandsymbol ==0 ist und einen Lauf zurück, wenn das aktuelle Bandsymbol !=0 ist. Andere, unwesentliche, Kombinationen führen zu einem Ausdruckswert von 0. Einsetzen aller möglichen Werte schafft Klarheit
Nun if (j == 46) S.W(n);
j hat immer noch den Wert 92 - S.P[i]. Da '.'=46 und 92-46==46 wird der Schreibebefehl bei j==46 ausgeführt.Interessante Punkte bei n = b[p -= (j -= 31) * j == 1 ? j : 0] += (j -= 17) * j == 1 ? j : j == 0 ? S.R() - n : 0;
-
Erst '>'= 62 und '<'=60 behandeln. j, die Hilfsvariable des aktuellen Tokens, wird um 31 erniedrigt und damit gilt j = 61 - S.P[i].
Damit ist j*j==1 genau dann wenn das < oder das > Symbol gefunden wurden. Dann ist -j aber auch genau der Wert, um den sich der Zeiger bewegen muss. -
Gleicher Trick für + und - nachdem j um weitere 17 erniedrigt wurde.
-
Nach dem letzten Schritte ist j == 0 für das Read-Symbol. Da der aktuelle Bandwert um den eingelesenen Wert erhöht wird, subtrahiert man den letzten Bandwert wieder.
Hmmm, noch Fragen?
-
-
Falls jemand meine Erklärung schon gelesen hat (vor dem 2. EDIT), und sich gewundert hat...
Nein, ich bin nicht auf den Kopf gefallen
Klar ist "c * c == 1" für c=0 nicht TRUE.
Bloss dass ich erst "c * c < 2" stehen hatte, weil das ein Zeichen kürzer ist. Das wollte mir nicht aus dem Kopf, ist irgendwie stecken geblieben.
-
hustbaer schrieb:
// Wir machen Member. Das spart das "=0" das wir bei lokalen Variablen bräuchten.
NEIN NEIN NEIN WIE KONNTE ICH DAS ÜBERSEHEN ?
EDIT: Den Rest lese ich morgen. Hatte einen Cocktail zuviel heute abend
-
µ, das vierfache =0 bei dir tut mir richtig weh. Als Membervariablen wären das auf einen Schlag 7 Zeichen weniger. Ansonsten: Das Muster
(j -= XXX) * j == 1gefällt mir. Da wär ich wohl auch nicht drauf gekommen.
-
Bashar ich beiße mir gerade selbst in den Arsch dafür. 221 wären es sonst.
-
@Bashar:
Wobei ich das "Deaktivieren" von Opcodes das unsere beiden Codes gemeinsam haben (zum Sparen des 2. "if" das in 1-Schleifen-Lösungen sonst nötig wäre) auch sehr kuhl finde
-
Naja, 221 geht ja noch.
Blöd wäre wenn du auf 219 oder gar 217 gekommen wärst damit
-
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.
-
Bashar schrieb:
Ansonsten: Das Muster
(j -= XXX) * j == 1gefällt mir. Da wär ich wohl auch nicht drauf gekommen.Spielt ein kleines wenig "Glück" eine Rolle. Bei hohen char-Werten kommt es zum Überlauf. Aber es gibt keine Zahl in UTF-16 die in diesen Fällen ebenfalls j*j==1 ergeben würde. Sonst hätte ich auf long umsteigen müssen. Bei einer Variante dieses Schemas hatte ich nämlich ein solches Problem.
-
hustbaer schrieb:
Wobei ich das "Deaktivieren" von Opcodes das unsere beiden Codes gemeinsam haben (zum Sparen des 2. "if" das in 1-Schleifen-Lösungen sonst nötig wäre) auch sehr kuhl finde
Ich hätte mir einen (sinnlosen) Rückgabewert bei der S.W() Funktion gewünscht. Dieses Monster war sonst nirgends unterzubringen. Imho ist nur der Upadate-Teil der For-Schleife in der Lage, Ausdrücke ohne Rückgabewert zu verarbeiten.
-
Übrigens ist mir bei diesem Contest aufgefallen, dass C# keine oktalen Literale kennt. Es war eine sehr frühe chancenlose Version mit >400 Zeichen, aber da hätte ich das erste mal seit ... weiß ich nicht ... überhaupt Oktalzahlen gebraucht, und C# hat die einfach nicht.
010 == 10 in C#. Keine Warnung. 
-
Mit long hättest du aber Probleme, da C# keine implizite Konvertierung long -> int erlaubt.
D.h. beim Aufruf der Write Funktion wäre dann ein "(int)" Cast fällig gewesen = +5 Zeichen.Ich hatte mir das mit long nämlich auch schon überlegt, da ich eben erst "i * i < 2" stehen hatte. Dummerweise geht sich das aber nicht mit allen möglichen UTF-16 Zeichen aus, bei 46xxx (sqrt(1 << 31)) ist Schluss - da wird die Zahl nämlich auf einmal negativ.
-
µ 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
-
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...)
-
µ 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)
