Programming in Brainfuck: Part 1 — Common patterns & conditions

Sun 24 August 2014 by TWal

This post is part 1 of the "Brainfuck tutorial" series:

  1. Programming in Brainfuck: Part 0 — Introduction
  2. Programming in Brainfuck: Part 1 — Common patterns & conditions
  3. Programming in Brainfuck: Part 2 — Arrays
  4. Programming in Brainfuck: Part 3 — Using a preprocessor

Here are the corrections for the exercises of part 0:

To print “Brainfuck” followed by a new line, here is a solution:

The ASCII codes are: 66 114 97 105 110 102 117 99 107 10
++++++++++[>+++++++>+++++++++++>++++++++++>++++++++++>+<<<<<-]   setup the memory like this: 0 70 110 100 100 10
>----.>++++.>---.>+++++.<<----.>>---.<<+++++++.>++.++++++++.>>.  print "Brainfuck"

To print “Brainfuck” ten times, we can use the code from our previous exercise, modified a little bit:

++++++++++[>+++++++>+++++++++++>++++++++++>++++++++++>+<<<<<-]       setup the memory
++++++++++ [                                                         loop 10 time
    >----.>++++.>---.>+++++.<<----.>>---.<<+++++++.>++.++++++++.>>.  print "Brainfuck"
    <--<-------<-------<++++<                                        restore the memory
    -                                                                decrease the counter
]

Common patterns

In brainfuck, there are several patterns we use quite often.

Clear a cell

[-] set a cell to 0.

It works like this: “While the cell is not 0, decrease the value in the cell by one”.

It executes like this:

0 0 0 0 0               ++++[-]
^                       ^
4 0 0 0 0               ++++[-]
^                           ^
3 0 0 0 0               ++++[-]
^                             ^
2 0 0 0 0               ++++[-]
^                             ^
1 0 0 0 0               ++++[-]
^                             ^
0 0 0 0 0               ++++[-]
^                              ^

Move the value of the cell in another cell

[>+<-] moves the value of the current cell to the cell at its right.

It works like this:

0 0 0 0 0               ++++[>+<-]
^                       ^
4 0 0 0 0               ++++[>+<-]
^                           ^
3 1 0 0 0               ++++[>+<-]
^                                ^
2 2 0 0 0               ++++[>+<-]
^                                ^
1 3 0 0 0               ++++[>+<-]
^                                ^
0 4 0 0 0               ++++[>+<-]
^                                 ^

Of course, you can change it a little bit, to change its destination: [>>>+<<<-] or [<<+>>-].

Copy the value of the cell in another cell

[>+>+<<-]>[<+>-] is the pattern used to copy the value of a cell. The first loop moves the value of the cell in two cells: the destination cell, and a temporary cell. The second loop moves the value of the temporary cell to our first cell.

It works like this:

0 0 0 0 0               ++++[>+>+<<-]>[<+>-]
^                       ^
4 0 0 0 0               ++++[>+>+<<-]>[<+>-]
^                           ^
0 4 4 0 0               ++++[>+>+<<-]>[<+>-]
^                                    ^
4 0 4 0 0               ++++[>+>+<<-]>[<+>-]
  ^                                         ^

Search a 0 cell

[>] searches the next cell that is set to 0 to the right, [<] searches the next cell that is set to 0 to the left.

It works like this:

0 0 0 0 0               >>+>+>+[<]
^                       ^
0 0 1 1 1               >>+>+>+[<]
        ^                      ^
0 0 1 1 1               >>+>+>+[<]
      ^                          ^
0 0 1 1 1               >>+>+>+[<]
    ^                            ^
0 0 1 1 1               >>+>+>+[<]
  ^                               ^

Something in this loop in very different from the ones we saw earlier: it is unbalanced! It means that the code inside the loop doesn’t go back to the cell it started with.

Conditions

In brainfuck, a condition is: “If this cell is different from 0, execute this piece of code”. We can use a loop: we enter in the loop if and only if the current cell is different from 0. But at the end of our condition, we must go outside the loop. One strategy can be to zero the cell at the end.

[           If we enter in the loop then the current cell is different from 0
    ???     (insert something here)
    [-]     Clear the "condition cell"
]           We are now outside

While this strategy is effective, sometimes we would like to keep the value in our condition cell. One way to solve this is to copy the value of the condition cell:

[>+>+<<-]>[<+>-]>   Copy the condition cell (using two cleared cells)
[                   Loop on the copy
    ???
    [-]             Clear the copy
] <<                We are now outside and the condition cell still contains its original value

This requires two temporary cells. We can use only one temporary cell. Without looking at the code below, can you guess how to do it?

[               Loop on the condition cell
    ???
    [>+<-]      Move the condition cell to a temporary cell
]               We are now outside the condition
>[<+>-]         Restore the value of the condition cell

We moved the value of our condition cell to a cleared temporary cell, so our condition cell is now set to 0, but its value is saved in the temporary cell. Then, we can restore its value.

The “else”

Sometimes, you want to execute a piece of code if the value in the cell was 0. This can be done like this:

>+<         Set the "else flag" to 1
[           Loop on the condition cell
    ???     (insert something)
    >-<     Set the else flag to 0 if the condition was true
    [-]     Clear the condition cell for simplicity
]
> [         Loop on the else flag
    ???     (insert something)
    -       Clear the else flag
]

As you can see, if we don’t enter in the “if” part, we enter in the “else” part, and vice-versa.

Equalities and inequalities

How to test if cell A is equal to cell B? Here is a way to do it:

Tape: a b elseFlag
[>-<-]      B = B minus A
>>+<        set the else flag to 1 and go to B
[           if B != 0
    ???     (insert code for A != B)
    >-<     Clear the else flag
    [-]     Clear B
]
> [         else
    ???     (insert code for A == B)
    -       Clear else flag
]

Now, how to test if A is less than B? That’s harder than the equality. We will implement the following algorithm in brainfuck:

while(A != 0 and B != 0) {
    A -= 1;
    B -= 1;
}
// if A == 0 then A <= B
// if A != 0 then A > B
// if B == 0 then A >= B
// if B != 0 then A < B

One way to do it is:

Tape: A B temp loopFlag
>>> + [                     Loop on loopFlag
    [-]                     Clear loopFlag
    <<< [                   if(A)
        > [>+>+<<-]>[<+>-]  Copy B to loopFlag using temp
        << [>>+<<-]         End the condition using temp
    ] >> [<<+>>-]           Restore A's value
                            Here loopFlag = B if A != 0 or 0 if A == 0
    < -                     Decrease B
    < -                     Decrease A
    >>>                     Go to loopFlag
] <<< + > +                 We "overshot" a and b and restore their value

Take some time to understand deeply how it works. Once you are familiar with it, you’ll only need one more tool to make brainfuck programs: arrays.

Exercises

It’s time to train!

In the first exercise, you’ll write a program that reads a string and outputs “1” if all characters are the same, “0” otherwise. For example:

  • brainfuck” -> “0”
  • aaab” -> “0”
  • aaaaa” -> “1”
  • ccc” -> “1”

In the second exercise, you’ll write a program that reads a string and outputs “1” if the characters in the string are in the alphabetical order, “0” otherwise. For example:

  • brainfuck” -> “0”
  • program” -> “0”
  • adept” -> “1”
  • begins” -> “1”

To read a string, you can do this:

,           Read the first character
[           While the character is not 0
    ???     Do something
    ,       Read the next character
]

It supposes “,” set the cell to “0” when the input is finished. Not all interpreters do this, but this one does.

The ASCII code for “0” is 48, the ASCII code for “1” is 49.

In the third exercise, there is a number in a cell, and you must print it in binary, digits reversed (for example, 8 is 0001).