Back
Close

Getting started with BrainFuck

DPAmar
44.5K views
Previous: Evaluate Not() function

Evaluate Eq() and Neq() functions

To check if 2 values A and B are equal, we need to compute A-B. Either the result is 0 (then A == B) or not (then A != B)

In other words, "A-B" = Neq(B) because result is true if and only if A<>B

The Eq() function is a bit more tricky, it combines Neq and Not functions.

Let's start

  • Memory: A, B
  • Cursor: on A
  • Input: any

Process for Neq

  • while B is not null
    • invariant : d=A-B is constant
    • decrease B
    • decrease A
  • loop
  • B=0, so A=d
  • go back to cell A

Process for Eq

  • set else flag after B
  • compute A-B as explained above
  • while A is not null
    • reset A and else flag
  • loop (on null value)
  • while else flag is not null
    • set A to 1
    • reset else flag
  • loop (on null value)
  • go back to cell A

Code for Neq

>[    while B is not null
  -   decrease B
  <-> decrease A
]     loop
<     go back to cell A

Minified version

>[-<->]<

Code for Eq

>>+        set else flag
<[         while B is not null
  -        decrease B
  <->      decrease A
]          loop
<[         while A is not null
  [-]>>-<< reset A and else flag
]          loop (on null value)
>>[        while else flag is not null
  <<+      set A to 1
  >>-      reset else flag
]          loop (on null value)
<<         go back to cell A

Minified version

>>+<[-<->]<[[-]>>-<<]>>[<<+>>-]<<

Final state

  • Memory: Neq(A) or Eq(A)
  • Cursor: on first cell
  • Input: unchanged
  • Output: unchanged

Test program

These programs read 2 chars, and print both if different, or just a unique one if equal.

,>,            read A and B
[-<->>+<]      double trick : computes A minus B on the left and copy B on the right
<[             A != B
  >>[-<+<+>>]  reconstruct A and B original values from B copy
  <<.[-]       print A and clean
  >.[-]        print B and clean
<]             loop (on null value)
>>[            go to B copy (if not deleted then it means A == B)
  .[-]         print B (aka A and print only once) and clean
]<<            cleansing

Details: memory is

  • When A == B:
    • A B 0 then subtract/copy B
    • 0 0 B as A == B
    • nothing done from first cell
    • B printed from third cell, then cleansing
    • Final state 0 0 0
  • When A != B: d=A-B
    • A B 0 then subtract/copy B
    • d 0 B with d not null
    • from first cell, B added back to d and 0
    • A B 0
    • A printed and clean from first cell
    • B printed and clean from second cell
    • nothing done from third cell
    • Final state 0 0 0 Hence, only unique values are displayed, with a final state 0 0 0 in both cases
Create your playground on Tech.io
This playground was created on Tech.io, our hands-on, knowledge-sharing platform for developers.
Go to tech.io