Login [Register]
Don't have an account? Register now to chat, post, use our tools, and much more.

Do you think the smallest basic BF interpreter is 169 bytes?
yes
 0%  [ 0 ]
no
 52%  [ 10 ]
couldn't care less
 21%  [ 4 ]
what's the point of this again?
 26%  [ 5 ]
Total Votes : 19

So mid-January (Jan 9, 2019), I realized that squishy's BF interpreter is way oversized, so I began to make my own in TI-Basic.

My initial version was quite bloated at 274 bytes, but it worked (as a proof of concept):
Code:
Ans→Str1
DelVar L₁999→dim(L₁:1→A
1→B:While A≤length(Str1
sub(Str1,A,1→Str2
B+(Str2=">")-(Str2="<→B
L₁(B)+(Str2="+")-(Str2="-→L₁(B
If Str2=".
Disp L₁(B:If Str2=",
Then:Input C:C→L₁(B:End
1→C:If Str2="]
Then:If 0≠L₁(B:Then
Repeat C=0:A-1→A
sub(Str1,A,1→Str2
C+(Str2="]")-(Str2="[→C
End:End:Else:If Str2="[
Then:If not(L₁(B:Then
Repeat C=0:A+1→A
sub(Str1,A,1→Str2
C+(Str2="[")-(Str2="]→C
End:End:End:End:A+1→A:End

[The new-lines are for TI's on-calc editor which is the only thing I have worked on this in.]
My subsequent version was 232 bytes, then 200, 194, 185, 178, 176, 173, 171, then finally, 169 bytes.
I reached 169 Feb 19, 2019, and I believe this to be a lower minimum (but that's what I thought of 176 and 171 too Razz).
Some limitations came into play though.

Code:
restricted tokens: prgm
as few variables as possible. (I am using 6, counting lists, variables, and strings (not ans))

I will post my smallest later (maybe it will be even better then) so that you guys can puzzle over how to make one yourselves (It is the best way to learn!).
If someone (anyone) can beat my 169, I will be amazed and will post my code asap.

Timing: I measure the speed of the interpreter by running "+[.+]":prgmBLANK for 2-10 minutes and dividing the number of seconds by whatever number it ended on (my 169 byte is 2.1083 numbers/sec which is not my best.)
[.+] is equivalent to:

Code:
While Ans:Disp Ans:Ans+1:End
in BASIC.

If you have any questions or you think you can make a smaller interpreter, please post below.
Post your smallest BF Interpreter here so we can see how you did (after you make it)…

EDIT: If you don't know what BF is, you can read the wiki on it here: https://en.wikipedia.org/wiki/Brainf--k

Current Results:
LogicalJoe: 145 (derived from lirtosiast's solution)
lirtosiast: 146
PT_: 159
LogicalJoe: 163
kg583: 165
JWinslow23: 167
Haha, I also made a BF interpreter a while ago (only, it had many more features, and it handled the , instruction somewhat uniquely):

Code:
ClrHome
Input "BF program:     ",Str1
ClrHome
Disp "  0/100 compiled","Press MODE to","abort.
Str1+" ->Str1
"+-><[],.->Str2
"?->Str3
" !'#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}|~->Str0
DelVar L30->dim(L3
1->B
Repeat getKey=22 or B>length(Str1
   1+dim(L3->dim(L3
   round(B|E2/length(Str1),0
   Output(1,3-int(log(Ans+not(Ans))),Ans
   inString(Str2,sub(Str1,B,1->L
   If Ans
   Str3+sub(Str2,Ans,1->Str3
   If L<=4
   Then
      1->L3(dim(L3
      0
      Repeat B>length(Str1) or Ans and L!=Ans
         If Ans and L=Ans
         1+L3(dim(L3->L3(dim(L3
         B+1->B
         If Ans<=length(Str1
         inString(Str2,sub(Str1,Ans,1
      End
   Else
      B+1->B
   End
End
If B<=length(Str1
Then
   Disp "Aborted","successfully.
   Return
End
Output(1,1,100
If 2>length(Str3
"?[]->Str3
sub(Str3,2,length(Str3)-1->Str3
Disp "Code compiled.
Pause "Press ENTER.
ClrHome
Disp "
DelVar L1999->dim(L1
0->dim(L2
1->I
1->P
1->A
1->B
While I<=length(Str3
   getKey->K
   inString("-+",sub(Str3,I,1
   If Ans
   Then
      2Ans-3
      AnsL3(I)+L1(P
      Ans+256((Ans<0)-(Ans>255->L1(P
   Else
      inString("<>",sub(Str3,I,1
      If Ans
      Then
         2Ans-3
         P+AnsL3(I
         Ans+dim(L1)((Ans<1)-(Ans>dim(L1->P
      Else
         If ","=sub(Str3,I,1
         Then
            "?->Str4
            Output(8,1,Ans
            Repeat K=22 or K=105 and 1<length(Str4
               If 1<length(Str4
               Then
                  Output(8,15," 
                  expr(sub(Str4,2,length(Str4)-1
                  If Ans>=33 and Ans<=127
                  Output(8,15,sub(Str0,Ans-31,1
                  max(cumSum(binomcdf(2,0))(Ans={10,13,32
                  If Ans
                  Output(8,15,sub("LFCRSP",2Ans-1,2
               End
               Repeat max(Ans={22,23,24}) or Ans>71 and min(Ans!={75,81,85,91,95,103,104
                  getKey->K
               End
               If Ans>71 and Ans!=105 and Str4!="?0" and 4>length(Str4
               Str4+sub("789  456  123  0",Ans-36-5int(.1Ans),1->Str4
               If 1<length(Str4
               Then
                  If max(K={23,24} or expr(sub(Str4,2,length(Str4)-1))>255
                  sub(Str4,1,length(Str4)-1->Str4
               End
               Output(8,1,Str4+"   
            End
            If K!=22
            expr(sub(Str4,2,length(Str4)-1->L1(P
            Output(8,1,"   
            Output(8,15," 
         Else
            If "."=sub(Str3,I,1
            Then
               If 32<=L1(P) and 126>=L1(P
               Then
                  Output(A,B,sub(Str0,L1(P)-31,1
                  B+1->B
               End
               If max({10,13}=L1(P
               Then
                  Disp "
                  A+1->A
                  1->B
               End
               If B>16
               Then
                  1->B
                  Disp "
                  A+1->A
               End
               If A>7
               7->A
            Else
               If "["=sub(Str3,I,1
               Then
                  If L1(P
                  Then
                     I->L2(1+dim(L2
                  Else
                     1->N
                     Repeat I>length(Str3) or not(N
                        I+1->I
                        If I<=length(Str3
                        Then
                           inString("][",sub(Str3,I,1
                           If Ans
                           N+2Ans-3->N
                        End
                     End
                     If N
                     Then
                        Disp "Error:","Mismatched [
                        length(Str3->I
                     End
                  End
               Else
                  If "]"=sub(Str3,I,1
                  Then
                     If L1(P
                     Then
                        If dim(L2
                        Then
                           L2(dim(L2->I
                        Else
                           Disp "Error:","Mismatched ]
                           length(Str3->I
                        End
                     Else
                        dim(L2)-1->dim(L2
                     End
                  End
               End
            End
         End
      End
   End
   If K=22
   length(Str3->I
   I+1->I
End
If K=22
Then
   ClrHome
   Disp "Aborted","successfully.
   Return
End
Output(8,1,"Done
Pause
ClrHome

Here's the download if you want it.

However, you seem to have a few different rules for what constitutes acceptable input and output. Imma tackle this challenge and get back to you.
Here's my 170-byte solution, I believe JWinslow got the same, but with different code.

//"++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>-\>>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
Ans->Str1
"[.]-<+>->Str2
0rand(999->F
1->D
"inString(Str2,sub(Str1,A,1->|u
For(A,1,length(Str1
|u->B
If B>4
D+B-6->D
|LF(D)+sum(DeltaList(B={4,6->X
If B=2
Disp Ans
If not(B
Input X
X->|LF(D
2-B->U
While Ans(B=3-2not(X
Ans->S
A+U->A
S+sum(DeltaList(|u={3,1
End
End


I'm pretty sure the last loop can be optimized, but how? Surprised That's the question Very Happy

EDIT: 166 163 162 161 159 bytes!
I ended up doing something totally different from P_T, and got it down to 168 bytes (!).

"],[.<->+"+Ans->Str1
0rand(999->T
1->B
"-2+inString(Str1,sub(Str1,A,1->u
For(A,9,length(Str1
u->C
|LT(B)+sum(deltaList(Ans={4,6
If not(C
Then
Input E
E
End
If C=2
Disp Ans
Ans->|T(B
B+sum(deltaList(C={3,5->B
C
While Ans and 1=abs(C) and |T(B)angle(C
Ans->D
A+C->A
D+u*(1=abs(u
End
End

Took some advice from him, but I wasn't sure exactly how he was going about it. Now I know, and knowing is half the battle.

EDIT: I have a solution in 167 bytes (meaning I have exactly matched ol' LogicalJoe, using a method that he probably didn't use; this also probably points to the fact that 167 isn't optimal).

"],[.-<+>"+Ans->Str1
0rand(999->T
1->B
"-2+inString(Str1,sub(Str1,A,1->u
For(A,9,length(Str1
u->C
|LT(B)+sum(deltaList(Ans={3,5
If not(C
Then
Input E
E
End
If C=2
Disp Ans
Ans->|T(B
If C>3
B+C-5->B
C
While Ans and 1=abs(C) and |T(B)angle(C
Ans->D
A+C->A
D+u*(1=abs(u
End
End
I got mine down to 165 bytes (somehow?). I feel like there is still something left to optimize, but I don't know what. Apologies if I poorly converted the code to SourceCoder style (I'm working by hand).


"[,]<->+."+Ans->Str1
"-2+inString(Str1,Sub(Str1,A,1->|u
"Ans(1=abs(Ans->|v
0rand(999->Z:1->B
For(A,9,length(Str1
u-3:B+|v->B
u-4
|v+|LZ(B->D
If |u=6:Disp Ans
If not(|u:Then
Input D:End
D->|LZ(B
|u
|v->C
While Ans(D xor angle(C
A-tanh(Ans->A:u:C+|v->C
End:End
155 bytes, or 154 if we can expect the calculator to be in Degree mode. This was written before looking at other solutions, and so is probably suboptimal.


Code:
seq(inString(" <].[>,+",sub(Ans,X,1))-4,X,1,length(Ans->C
0rand(999->T
9->P
For(X,1,dim(|LC
  |LC(X->D
  P-iPart(sin(45^^oAns->P
  |LT(P)+iPart(D/4->V
  If not(D
  Disp Ans
  If D=3
  Input V
  V->|LT(P
  X->A
  While (V xor D=1)sum((1=abs(|LC))|LC,min(X,A),max(X,A
    X+D->X
  End
End


Edit: 154 bytes; (1=abs(|LC)) should be (1=LC^^2).
Seeing as how I have been completely crushed, here is my code:
Ans→Str1:0rand(999→L₁
1→B:For(A,1,length(Str1
inString("<>-+,.[]",sub(Str1,A,1→D
B+sum(ΔList(D={1,2→B
L₁(B→C:If D=5:Input C
C+sum(ΔList(D={3,4→L₁(B
If D=6:Disp C
(15-2D)(D=8-not(C→C
While C:A+Cˉ¹abs(C→A
sub(Str1,A,1
C+(Ans="[")-(Ans="]→C
End:End

I managed to get it down to 166 bytes, but that was it.
I am currently at 158 bytes:


Code:
// Hello world in Brainf*ck: "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>-\>>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
Ans->Str1
"[.]-<+>->Str2
0rand(999->F
1->D
"inString(Str2,sub(Str1,A,1->|u
For(A,1,length(Str1
   |u->B
   If B>4
   D+B-6->D
   |LF(D->X
   If B=2
   Disp Ans
   If not(B
   Input X
   X+sum(DeltaList(B={4,6->|LF(D
   2-B->U
   While Ans(B=3-2not(X
      Ans->S
      A+U->A
      S+sum(DeltaList(|u={3,1
   End
End
lirtosiast wrote:
155 bytes, or 154 if we can expect the calculator to be in Degree mode. This was written before looking at other solutions, and so is probably suboptimal.


Code:
seq(inString(" <].[>,+",sub(Ans,X,1))-4,X,1,length(Ans->C
0rand(999->T
9->P
For(X,1,dim(|LC
  |LC(X->D
  P-iPart(sin(45^^oAns->P
  |LT(P)+iPart(D/4->V
  If not(D
  Disp Ans
  If D=3
  Input V
  V->|LT(P
  X->A
  While (V xor D=1)sum((1=abs(|LC))|LC,min(X,A),max(X,A
    X+D->X
  End
End


This is a nice solution, though notably does not allow for non-BF characters; a true interpreter would just ignore such characters, but this version seems to pretend everything non-BF is a "-" operator. Also, I think you can optimize a tad for speed (though no improvement in size) via:

Code:
seq(inString(" <].[>,+",sub(Ans,X,1))-4,X,1,length(Ans->C
0rand(999->T
9->P
For(X,1,dim(|LC
  |LC(X->D
  P-iPart(sin(45^^oAns->P
  |LT(Ans)+iPart(D/4->V
  If not(D
  Disp Ans
  If D=3
  Input V
  V->|LT(P
  X
  While (V xor D=1)sum((1=abs(|LC))|LC,min(X,Ans),max(X,Ans
    Ans+D
  End
  Ans->X
End
True, I didn't think about speed at all. (1=abs(|LC))|LC is also recalculated every iteration of the loop and this only saves 1 byte.

Adding the - symbol to the string so it can be distinguished would add probably 3 bytes. So then I would have 157 and PT_ 160. But I think those rules are less fun.
kg583 wrote:
This is a nice solution, though notably does not allow for non-BF characters; a true interpreter would just ignore such characters, but this version seems to pretend everything non-BF is a "-" operator.

This being a code golf challenge, I myself would rule that it doesn't matter for this specific purpose. But hey, who am I to judge code golf contests?
I managed a 158 byte solution (157 if I only have a 99 dim list) (treating undefined as . which won't change the algorithm being executed).
[Also, beat PT_! ~dance]

Code:
Ans→Str1:0rand(999→θ
"[,]-<+>→Str2
"inString(Str2,sub(Str1,A,1→|u
1→B:For(A,1,length(Str1
|u→D:If D>4:B+D-6→B
⌊θ(B→C:If D=2:Input C
C+sum(ΔList(D={4,6→⌊θ(B
If not(D:Disp C:D-2→D
While Ans(D=1-2not(C
Ans→E:A-D→A
E+sum(ΔList(|u={1,3
End:End

I had no idea that you could remove the |L when storing to a list Surprised.
And the vector should NOT take 10 seconds to initialize, I want to use dim=99 now (I mean REALLY, 999 locations?).
I wan an idiot with the poll, I wish I could try that again…
So, as for non-BF characters, there should be 2 versions, one which ignores them another which doesn't.

EDIT: Apparently, this is very similar to PT's Solution
EDIT2: Had to fix the loop code.
Combining PT_ and LogicalJoe's clever use of sequence variables with my arithmetic tricks, I managed to get to 148 bytes.


Code:
Ans->Str1
".>[,]< -->Str2
"4-inString(Str2,sub(Str1,A,1->|u
0rand(099->T
1->P
For(A,1,length(Str1
   |u->D
   P+iPart(sin(45^^oD->P
  |LT(P->C
  If not(D
  Input C
   C+iPart(D/4->|LT(P
  If D=3
  Disp C
  D->E
   While E and D+1=2not(C  // E and D+1=2not(C
    A+D->A
      E+|unot(1!=abs(|u->E
   End
End


EDIT: 146 bytes.


Code:
Ans->Str1
".>[ ]<,-->Str2
"4-inString(Str2,sub(Str1,A,1->|u
0rand(099->T
1->P
For(A,1,length(Str1
   |u->D
   P+iPart(sin(45^^oD->P
  |LT(P->C
  If D=~3
  Input C
   C+iPart(D/4->|LT(P
  If D=3
  Disp C
  D->E
   While E and D+1=2not(C  // E and D+1=2not(C
    A+D->A
      E+iPart(|u^^-1->E
   End
End
lirtosiast managed the first Interpreter under 150 bytes! (Great job)
I didn't think it could be done.
Here's a version which eliminates the E variable with no size difference (still 146 bytes):

Code:
Ans→Str1:0rand(099→T:1→P
".>[ ]<,-→Str2
"4-inString(Str2,sub(Str1,A,1→|u
For(A,1,length(Str1
|u→D:P+iPart(sin(45°D→P
⌊T(P→C:If D=~3
Input C:C+iPart(D/4→⌊T(P
If D=3:Disp C
D(D+1=2not(C→C:While C  // C and D are both valid candidates
A+D→A:C+iPart(|uˉ¹→C
End:End

There must to be something better than iPart(sin(45°D, [7 bytes], but I can't find it.
Using lirtosiast's program as a base. 145 bytes!technically 144 because I am using 6! to initialize the list.

Code:
Ans→Str1:".>[ ]<,-→Str2
0rand(6!→T:"4-inString(Str2,sub(Str1,A,1→|u
1→B:For(A,1,length(Str1
|u→D:B+iPart(sin(45°D→B
⌊T(B→C:If D=⁻3:Input C
C+iPart(D/4→⌊T(B:If D=3
Disp C:D+1=2not(C→C
While C:A+D→A
C+DiPart(|uˉ¹→C:End:End

The code was crushed like that for viewing it in TI's 10 Line editor.
  
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are GMT - 5 Hours
 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

 

Advertisement