Programming in Brainfuck: Part 2 — Arrays

Sat 28 May 2016 by TWal

This post is part 2 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 1:

Test if all characters are the same:

Tape: nb char otherchar temp flag
>+++++++[-<+++++++>] initialise nb to 49 ("1")
>> , [<+<+>>-] read in temp and  move to char and otherchar
< [ while otherchar
    >>+ set else flag
    <<< [->->+<<] check equality and keep the value in temp
    > [ if different
        >>-<< remove flag
        << - >> change nb to "0"
        [-] go out of the loop
    ]
    >> [ else
        <[-<<+>>] move temp to char
        < , read new char in otherchar
        >> - clear flag
    ]
    <<
]
<< . print nb
[-]++++++++++. print newline

Test if the characters are ordered:

Tape: nb copychar temp newchar char flag
>+++++++[-<+++++++>] initialise nb
>, [>+>+<<-] read in temp and move to newchar and char
> [ while newchar
    [<+<+>>-] < [>+<-] > copy newchar in copychar using temp
    >>>+[[-]<<<[>[>+>+<<-]>[<+>-]<<[>>+<<-]]>>[<<+>>-]<<->->>]<<+<+ inequality tester (see part 1)
    >> + set flag
    < [ if char (then char strictly greater than newchar and the string is not ordered)
        <<<<->>>> put 0 in nb
        >-< unset flag
        [-] go out of the loop
    ]
    > [ else
        <<<< [>>>+<<<-] move copychar to char
        >> , read newchar
        >> - clear flag
    ]
    <<
]
<<< . print nb
[-] ++++++++++ . print newline

Note that flag is also the temp of the inequality tester: we can do this because we know that flag is set to 0 at this moment. I also used the inequality tester as a “black box” but I don’t recommand you to do this: in real programs, the temp of the inequality tester may be in some other place…

Print a number in binary, digits reversed:

Tape: toprint div1 div2 divflag elseflag ascii0 ascii1
+++++ +++ put a number in toprint
>>>+++++++[>+++++++<-] >[>+>+<<-] > - initialise ascii0 and ascii1
<<<<<  [ while toprint != 0 (loop 1)
    >>> [-] + set divflag
    <<< [ while toprint != 0 (loop 2)
        >>>> + set elseflag
        < [ if divflag
            << + increment div1
            >>> - unset elseflag
            < -
        ]
        > [ else
            << + increment div2
            > + set divflag
            > -
        ]
        <<<< -
    ]
    >>>> + set elseflag
    << [<-<+>>-] subtract div1 to div2 and move div2 to toprint
    < [ if div1 (if the digit to print is 1)
        >>> - unset elseflag
        >> . print 1
        <<<<< -
    ]
    >>> [ else
        > . print 0
        < -
    ]
    <<<<
]
++++++++++. print newline

How does it works? Loop 1 does an euclidian division of toprint by two, print a digit, until toprint becomes 0. Loop 2 divides toprint by two, using div1 and div2. For example, if toprint = 5 then div1 = 3 and div2 = 2. The quotient is div2 and the remainder is div1-div2. This is done using divflag: if it is set we increment div1, otherwise we increment div2.

In python, it looks like this:

toprint = 19 #or any value
while toprint != 0:
    div1 = 0
    div2 = 0
    divflag = True
    while toprint != 0:
        if divflag:
            div1 += 1
            divflag = False
        else:
            div2 += 1
            divflag = True
        toprint -= 1
    print(div1-div2)
    toprint = div2 #because div2 contains the value of toprint // 2

Arrays

How do we represent arrays in brainfuck? To understand the difficulty, suppose you have in your memory tape a string you just read with ,[>,] (remember that , set to 0 the current cell if there is no more input to read). You can go after this array by doing [>], you can print its content by doing [.>], but for example, how can you compute its length?

We need another representation. A trick I found is to insert a flag initialized to 1 between each cell: before, the memory looked like data1 data2 data3 ..., now it looks like zero data1 flag1 data2 flag2 data3 flag3 tmp zero. The zero cells are there to indicate the end of the array. Now, the input looks looks like this:

, [ read the first value and loop
    >+ set the flag of the last cell
    >, read the next value
]

We can go at the end of the array by going on a flag and doing [>>], we can print the content of the array like this:

now we are on the first flag of the array
[ iterate on the array
    <.> print the current data
    >> go on the next flag
]
now we are at the zero cell after the array

Can you figure out how to compute the array length? (for example, in the tmp cell)

Here is how you can do: you can set a flag to 0 and then go at the cell tmp, and then go back to the cell you were. Starting on the tmp cell, it looks like:

[-] clear the tmp cell
< [<<] go at the beginning of the array
>> [ iterate on the array
    - set the flag to 0
    >> [>>] < go on tmp
    + increment tmp
    < [<<] go back to the cell we were at the beginning of the loop
    + >> go to the next cell
]

Now that you understand how it works, some natural questions arises. How can we do if we want two (or more) arrays? If we want array of arrays?

Sometimes, we initialize arrays and then they don’t change size. For example, if you are doing a brainfuck interpreter in brainfuck, you have one array containing the instructions and an other one containing the memory: the first array size don’t change. You can then go like this: zero data1,1 flag1,1 ... data1,n flag1,n tmp zero [...] zero data2,1 flag2,1 ... data2,n flag2,n tmp zero (in [...] you may have some cells that you can use when working on the second array).

Another way is to interleave the arrays: tmp1 zero1 ... tmpN zeroN data1,1 flag 1,1 ... dataN,1 flagN,1 data1,2 flag1,2 ... dataN,2 flagN,2 ... dataN,M flagN,M tmp1 zero1 ... tmpN zeroN

To make array of arrays, it’s the same as an array, but data is no more one cell, but is an array.

Exercises

Exercise 1: you are given an array of numbers, and you must compute the sum of its elements.

Exercise 2: in the input, you are given two strings separated by a new line, and you must output 1 if they are equal, or 0 otherwise.

brainfuck
brainfuck

must output 1 and

brainfuck
tomato

must output 0