** Brainfuck Interpreter Contest ** [abgeschlossen]
-
Bisschen früh aber ich bin ja nun raus: Gratulation an Hustbaer, war zeitweise ein spannendes Rennen
Jederzeit gerne wieder ein Contest. Aufgaben bei denen man schrittweise optimieren kann haben ihren Reiz
-
hustbaer schrieb:
@GPC:
(...)
Würde mich nicht wundern, wenn ich deinen Code mit "meinen" Tricks sogar unter meine 219 bringe
Hihi. Nö, komm nichtmal in die Nähe. Es geht zwar noch einiges, aber nicht genug
-
Uff.
Hab grad meinen Code "kommentiert". Gar nicht so einfach das so zu erklären dass man es verstehen kann ohne allzuviel zu grübeln...
169 Zeilen mit Kommentaren.(Witzigerweise ist mir dabei noch ein "verschenktes" Zeichen aufgefallen, also meine beste Version liegt jetzt bei 218, hihi)
-
Ich hab meine Variante auch abgegeben. Ist zwar nicht konkurrenzfähig, aber vielleicht lässt sich ja doch eine Erkenntnis daraus gewinnen. Insofern wäre es wohl schön, wenn jeder der was gebastelt hat, dies auch an hustbaer schickt.
Edit: Vielleicht könnten wir ja noch ein kleinen Benchmark einbauen. Es wäre später interessant zu sehen, inwiefern die Ausführungszeiten bei den Codes von dessen Länge abhängig sind.
-
Loslos, will Code sehen.
-
Naja, det dauert noch ein paar Stunden...
Nicht dass sich nochwas tun würde bis dahin, aber ich hab Samstag 23:59 geschrieben, daran halte ich mich jetzt auch
-
*hust* *drängel*
-
Sorry, bin grad erst ausm Kino zurückgekommen. Ich muss die Interpreter noch testen und das Ergebnis zusammenschreiben - dauert noch etwas.
-
So. Viele haben nicht eingereicht, aber egal. Hier das
Ergebnis
-
µ - 228
-
KasF - 255
-
Bashar - 260
-
Dummie - 264
-
GPC - 276
-
hustbaer - 254 bzw. 218
Die Sourcen folgen sogleich...
-
-
- µ - 228
class I{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;}}} 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; } } }µ hat keine Erklärung dazugeschrieben. Ich müsste den Code auch selbst erst auseinandernehmen, aber das Grundprinzip kommt mir sehr bekannt vor
Im Prinzip fast das selbe wie mein Code, nur fehlen ein paar Tricks.
-
- KasF - 255
class I{public void R(S q){int[]b=new int[1<<16];int z=0,i=0,s=0,a;while(i<q.P.Length){a=q.P[i]-40;s+=a==51&&(b[z]==0||s!=0)?1:a==53&&(b[z]|s)!=0?-1:0;if(s==0){b[z]+=a==3?1:a==5?-1:a==4?q.R()-b[z]:0;z+=a==22?1:a==20?-1:0;if(a==6)q.W(b[z]);}i+=s<0?-1:1;}}} class I_Nice { public void R(S q) { int[] b = new int[1 << 16]; int z = 0, i = 0, s = 0, a; while (i < q.P.Length) { a = q.P[i] - 40; s += a == 51 && (b[z] == 0 || s != 0) ? 1 : a == 53 && (b[z] | s) != 0 ? -1 : 0; if (s == 0) { b[z] += a == 3 ? 1 : a == 5 ? -1 : a == 4 ? q.R() - b[z] : 0; z += a == 22 ? 1 : a == 20 ? -1 : 0; if (a == 6) q.W(b[z]); } i += s < 0 ? -1 : 1; } } }KasF hat keine Erklärung dazugeschrieben. Ist aber auch eine "klassische" (hihi) 1-Schleifen-Lösung.
-
Gerade nach Hause gekommen. Schön, die Codes treffen ein
Falls Erklärung erwünscht, schreibe ich morgen gerne was dazu.
Und auf die Tricks auf die ich nicht gekommen bin, bin ich natürlich am meisten gespannt
-
- Bashar - 260
class I{int j,p,b,r=1,i,t,k;public void R(S s){var d=new int[65536];for(;j<s.P.Length;j+=r){k=s.P[j];i=">+[.,<-]".IndexOf(s.P[j])%5+(b!=0?6:0);t=(k&2)-1;r=i==8&&(b+=t)==0?1:r;k=d[p+=i==0?t:0];if(i==3)s.W(k);d[p]=i==1?k+t:i==4?s.R():k;b=i==2&&k!=0^t>0?r=t:b;}}} class I_Nice { int j, p, b, r = 1, i, t, k; public void R(S s) { var d = new int[65536]; for (; j < s.P.Length; j += r) { k = s.P[j]; i = ">+[.,<-]".IndexOf(s.P[j]) % 5 + (b != 0 ? 6 : 0); t = (k & 2) - 1; r = i == 8 && (b += t) == 0 ? 1 : r; k = d[p += i == 0 ? t : 0]; if (i == 3) s.W(k); d[p] = i == 1 ? k + t : i == 4 ? s.R() : k; b = i == 2 && k != 0 ^ t > 0 ? r = t : b; } } }Bashar hat mir nen "kaputten" Code geschickt. Da der Fehler aber lediglich eine überschüssige "}" ganz zum Schluss war, hab ich das mal "übersehen". Erklärt vielleicht auch warum er selbst 261 gezählt hat, wo es doch nur 260 sind
Bashar hat folgende Erklärung dazugeschrieben:
Bashar schrieb:
Die Maschine hat zwei Modi, einen Befehlsausführungsmodus und einen Schleifenmodus. In ersterem (b == 0) werden Befehle ausgeführt, in letzterem (b != 0) werden Klammern gezählt. Beide sind in derselben Schleife untergebracht, dh auch im Schleifenmodus werden Befehle "ausgeführt". Halt anders.
Variablen:
j = Befehlszeiger
p = Datenzeiger
b = Anzahl der offenen Klammerebenen (positiv in Vorwärts- und negativ in Rückwärtsrichtung)
r = Richtung, +1 vorwärts, -1 rückwärts
i = decodierter Befehl, wenn man so will
t = durch den aktuellen Befehl vorgegebene Richtung (z.B. + ist +1, - ist -1, analog bei >< und [])
k = Hilfsvariable für das aktuelle Zeichen und das aktuelle DatumDie Interessanten Sache hier werden allerdings nicht erklärt
Ist zwar auch eine "1-Schleifen-Lösung", aber macht einige Dinge ganz anders als ... die anderen
-
hustbaer schrieb:
Bashar hat mir nen "kaputten" Code geschickt. Da der Fehler aber lediglich eine überschüssige "}" ganz zum Schluss war, hab ich das mal "übersehen". Erklärt vielleicht auch warum er selbst 261 gezählt hat, wo es doch nur 260 sind
Oops, das war die schließende Klammer vom Namespace.
-
- Dummie - 264
class I{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();}}}} 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(); } } } }Dummie hat auch keine Erklärung dazugeschrieben. Erste rekursive Lösung. Ansonsten ziemlich einfach zu verstehen.
-
- GPC - 276
class I{int p=0,i=-1;int[]b=new int[65536];public void R(S s,int x=1){for(int j=i;++i<s.P.Length;){int c=s.P[i];if(c>90|x!=0){if(c==62)++p;if(c==60)--p;if(c==43)++b[p];if(c==45)--b[p];if(c==44)b[p]=s.R();if(c==46)s.W(b[p]);if(c==91)R(s,b[p]);if(c==93){i=x==0?i:j-1;break;}}}}} class I_Nice { int p = 0, i = -1; int[] b = new int[65536]; public void R(S s, int x = 1) { for (int j = i; ++i < s.P.Length; ) { int c = s.P[i]; if (c > 90 | x != 0) { if (c == 62) ++p; if (c == 60) --p; if (c == 43) ++b[p]; if (c == 45) --b[p]; if (c == 44) b[p] = s.R(); if (c == 46) s.W(b[p]); if (c == 91) R(s, b[p]); if (c == 93) { i = x == 0 ? i : j - 1; break; } } } } }Zweite Rekursive Lösung. Zwar ein paar Zeichen länger als die von Dummie, dafür viel eleganter
GPC hat folgenden Code als Erklärung dazugeschrieben:
class I { int bufferPtr = 0, sourceIndex = -1; int[] buffer = new int[65536]; /// <summary> /// Hauptfunktion /// </summary> /// <param name="s"></param> /// <param name="execute">Wenn execute != 0, dann führe die Befehle bis zum Schleifen-/Programmende aus</param> public void R(S s, int execute=1) { //Zu Beginn den derzeitigen index in initialIndex merken, damit man bei Schleifen zurückspringen kann for (int initialIndex = sourceIndex; ++sourceIndex < s.P.Length; ) { int opCode = s.P[sourceIndex]; //Zum besseren Verständnis ist die Bedingung hier im Vergleich zur kurzen Version negiert if (opCode < 91 && execute == 0) continue; if (opCode == 62) ++bufferPtr; if (opCode == 60) --bufferPtr; if (opCode == 43) ++buffer[bufferPtr]; if (opCode == 45) --buffer[bufferPtr]; if (opCode == 44) buffer[bufferPtr] = s.R(); if (opCode == 46) s.W(buffer[bufferPtr]); if (opCode == 91) R(s, buffer[bufferPtr]); if (opCode == 93) { //Am Ende einer Schleife wird entschieden, ob man zurück zum Anfang springt (index auf initialIndex - 1 zurücksetzen) //oder alle Durchläufe absolviert hat, aus der Funktion zurückkehrt und mit dem nächsten Befehl weitermacht sourceIndex = execute == 0 ? sourceIndex : initialIndex - 1; break; } } } }Erklärt zwar auch nicht wirklich viel, aber viel muss auch nicht erklärt werden
-
Bashar, dein Code ist echt kaputt
-
0.1) hustbaer - 254
class I{public void R(S z){int p=1<<16,i=-1;var m=new int[2*p];m[93]=-++m[91];while(++i<z.P.Length){int c=z.P[i],n=m[c],d=n;p+=c==62?1:c==60?-1:0;m[p]+=c==43?1:c==45?-1:0;if(c==46)z.W(m[p]);if(c==44)m[p]=z.R();while(n!=0&&m[p]!=0==n<0)n+=m[z.P[i+=d]];}}} class I_Nice { public void R(S z) { int p = 1 << 16, i = -1; var m = new int[2 * p]; m[93] = -++m[91]; while (++i < z.P.Length) { int c = z.P[i], n = m[c], d = n; p += c == 62 ? 1 : c == 60 ? -1 : 0; m[p] += c == 43 ? 1 : c == 45 ? -1 : 0; if (c == 46) z.W(m[p]); if (c == 44) m[p] = z.R(); while (n != 0 && m[p] != 0 == n < 0) n += m[z.P[i += d]]; } } }Hah, eine "konkurrenzfähige" 2-Schleifen Lösung, da guckt ihr, was?
Das ist der Code den ich quasi zu Beginn des Contest hatte (Interpreter_2_1252.cs).Ein paar kleine Erklärungen: ich hatte in meinen "frühen" Ansätzen einfach SO viele Stellen wo ich mit '[' bzw. ']' verglichen hatte, dass ich mir dachte, da muss ein Lookup-Table her (Lookup-Tables sind auch einfach so kuhl!).
Der Lookup Table ist die erste Hälte von "m", die zweite wird für den Speicher verwendet (der Daten-Zeiger wird dazu einfach initial auf 1 << 16 platziert statt auf 0).
Der Lookup-Table enthält für '[' +1, für ']' -1 und sonst überall 0.
-
hustbaer schrieb:
Die Interessanten Sache hier werden allerdings nicht erklärt
Was ist denn interessant? Ich kommentier mal:
class I_Nice { // TRICK: Membervariablen werden mit 0 initialisiert. int j, p, b, r = 1, i, t, k; public void R(S s) { // TRICK: var ist kürzer als int[]. Und 65536 ist genauso lang wie 1<<16 :p var d = new int[65536]; // TRICK: for ist kürzer als while for (; j < s.P.Length; j += r) { k = s.P[j]; // Das ist das wichtigste: Zusammengehörende Zeichen werden auf ein i abgebildet. // Im Befehlsausführungsmodus: // >< => 0 // +- => 1 // [] => 2 // . => 3 // , => 4 // Im Schleifenmodus wird 6 addiert, so dass wir 6 bis 10 // (und 5 für "nicht gefunden") // haben, alles ausser [] (8) wird aber ignoriert. // Probleme: 1) Ätzend langer Code. 2) Ich hatte erst sowas wie // .IndexOf(...) / 2, aber für "nicht gefunden" gibt IndexOf -1 // zurück, und -1/2 ist auch 0 (:open_mouth:). 3) IndexOf geht nur mit // char, nicht mit int, ich kann also mein k nicht wiederverwenden i = ">+[.,<-]".IndexOf(s.P[j]) % 5 + (b != 0 ? 6 : 0); // Bit 1 des Zeichens gibt bei ><, +-, [] praktischerweise an, ob // nach oben oder nach unten gezählt werden soll. t = (k & 2) - 1; // Schleifenmodus mit Klammern: Zähle die Klammerebenen. Bei 0 // Schleifenmodus beenden und Richtung auf "vorwärts" setzen r = i == 8 && (b += t) == 0 ? 1 : r; // Datenzeiger verändern, falls i==0 (dh ><) k = d[p += i == 0 ? t : 0]; if (i == 3) s.W(k); // Aktuelles Datum verändern, falls +-, bzw. ggf. einlesen d[p] = i == 1 ? k + t : i == 4 ? s.R() : k; // bei [] evtl. in den Schleifenmodus schalten (b auf +1 bzw. -1) // bei [ soll das passieren falls das aktuelle Datum k == 0 ist, // bei ] falls das aktuelle Datum k != 0 ist. Da t für [ +1 und für // ] -1 ist, wird das in der Bedingung k != 0 ^ t > 0 // zusammengefasst. Die Laufrichtung im Schleifenmodus ist // auch durch t festgelegt. b = i == 2 && k != 0 ^ t > 0 ? r = t : b; } } }
-
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).
