7th July 2019
Brainfuck is an extremely minimal yet Turing complete programming language consisting of only 8 commands.
To explain the choice of name 'Brainfuck', consider the following example program which prints 'Hello!'.
++++++++++[->+++++++>++++++++++>++++++++++>++++++++++>++++++++++>+++>+<<<<<<<] >++>+>++++++++>++++++++>+++++++++++>+++<<<<<[.>]
There are many good introductions to Brainfuck on the web, e.g. on
Wikipedia,
Esolang, and this
Gist by GitHub user
roachhd.
Briefly, the Brainfuck model consists of a large array of bytes (the 'tape')
initialised to 0, and a pointer initialised to the first cell of the array. The
value at the pointer can be incremented or decremented with + and -, and
the pointer itself can be incremented or decremented with > and <. The .
command outputs the value at the pointer, and the , command reads and stores
a byte of input. Finally, [ and ] allows a section of code to be repeated
until the value at the pointer is 0. And that's the whole language!
I recently created a Connect Four
game in Brainfuck, which allows two players to play against each other. You
choose a column by typing a number 1-7, and alternating O and X pieces are
put down according to the usual Connect Four mechanics.
At the moment nothing happens when you actually get four in a row (implementing the win condition in Brainfuck proved too difficult...), so the game continues until the board is full.
Here's the code, which comes out at characters.
Of course one would have no hope of understanding the code in its above form,
and I certainly did not write it in one big chunk as shown. To make any sense
at all of a Brainfuck program I have found that extensive comments are
required; luckily any characters outside the 8 commands (+-><.,[]) are
treated as comments and ignored. The commented code is shown further down this
page.
I originally wrote the program to be run at the command line, so it probably
won't work in your favourite online Brainfuck interpreter. For example, it
prints the ANSI escape code <ESC>[2J to clear the screen at the start of
each move, and expects to consume a newline at the end of user input. To
demonstrate the game on this page, it was therefore necessary to create my own
Brainfuck implementation in JavaScript.
On this page it runs exactly the minified code shown above. The text box below the output area is the 'command-line', which is where you can enter the column number to play the game. The tape is also shown and updated each time the program waits for input. The colour of a cell represents its value, with white for 0 and black for 88 (the ASCII code for 'X'), which is the highest value used (except for temporary values used when working out where to place the next piece).
The full source code with comments, shown below, explains the tape layout and the gritty details.
The basic idea is to store the game grid as a flattened array of ASCII values, with cells separated by spaces and rows by carriage returns. An extra 'dummy row' at the start is not printed, but simplifies checking when a column is full later.
After the tape is set up, the main loop begins. First, the screen is cleared and the grid printed. User input is then read and some basic error-checking performed: we just check that the input lies between '1' and '7' (ASCII 49 and 55).
We then shift rightwards to the column in the dummy row where the piece should
be placed. This is more challenging than it appears at first glance, and was
probably the most difficult part to figure out. It is easy in Brainfuck to
shift a fixed number of cells by repeating the > command; it is also easy
to shift to the next 0-cell with [>]. Shifting a variable number of cells
is more involved, especially when we cannot afford to trash the tape between
the start and destination cells. In my case it involved carrying around a
0-cell and the number of positions n left to shift, and storing grid values
in a temporary cell at the start of the tape to avoid overwriting them. See the
comments in the code for details.
Once in the correct column, a fixed number of right shifts takes us to the same
column in the final row. It is then just a case of shifting left a row at a
time until we hit an empty cell (a hyphen: ASCII 45). Depending on whose turn
it is (the current player p, 0 or 1, is stored in cell 2), a O or X is
placed.
All that remains is to flip the current player p if the move was valid; that
is, if the piece we just placed was not in the dummy row. Even something as
simple as this requires careful organisation of the tape to allow a few extra
cells to be used as temporary flags.
[
connect 4
---------
tape organisation is as follows:
0 p 0 k 0 0 a1 ... an 0
p is the symbol for the current player
k is used to store column number to travel to (1-indexed)
a1 ... an is 7x7 grid flattened with each row separated by newline (ascii 10),
where each cell is followed by a space (ascii 32)
cells are all initialised to '-'
the game grid is 7x6 -- we use the first row as a dummy row that is always
empty, so that a piece can always be placed there (and cleared afterwards)
note that the program relies on cell values wrapping around when decreased
below 0 or past 255
]
init p = 1
>+
fill grid; hyphen is ascii 45; space is 32; newline is 10
>>>> ++++++++++ [ do the tens
->
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +>
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +>
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +>
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +>
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +>
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +>
++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> ++++>+++> +
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
+[ do the units
->
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> >
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> >
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> >
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> >
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> >
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> >
+++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++> +++++>++>
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
]
main loop: pointer on cell 4 (k)
<<+[
-
###################################[ tactical comment
1: send ansi code for clear screen: ESC [ 2 J
ESC = 27 = 9 * 3
'[' = 91 = 10*9 + 1
'2' = 50 = 10*5
'J' = 74 = 15*5 - 1
2: send ansi code for resetting cursor to first row and column: ESC [ ; H
';' = 59 = 10*6 - 1
'H' = 72 = 10*7 + 2
(balance brackets in this comment: ]]])
###################################]
1: +++++++++[ - <+++> ]<.[-]>
++++++++++[ - <+++++++++> ]<+.[-]>
++++++++++[ -<+++++> ]<.[-]>
+++++++++++++++[ -<+++++> ]<-.[-]>
2: +++++++++[ - <+++> ]<.[-]>
++++++++++[ - <+++++++++> ]<+.[-]>
++++++++++[ - <++++++> ]<-.[-]>
++++++++++[ - <+++++++> ]<++.[-]>
print column labels (numbers 1 to 7) separated by space; plus newline at
the end
+++++++[ - <+++++++> ]
>++++++++[ - <++++> ]<< store space (32) in k
.>.<+ .>.<+ .>.<+ .>.<+ .>.<+ .>.<+ .
[-]++++++++++.[-]>[-]
print current state of the cells
>>>
>>>>>>>>>>>>>>> skip dummy row
[.>]<[<]<<
[-]
###################################
get input
we need to read a value k between '1' and '7' (ascii 49 and 55)
1: set s flag to 1; we will use this to loop until input is valid
*
0 p s 1 0 0 etc
2: loop:
L1: read col number and subtract '1' = 49; also consume newline
*
0 p s k 0 0 etc
L2: we need 0 {= k {= 6; check this by successively subtracting 1 and
check when k gets to 0;
if we subtract 7 and still no zero then k is out of range;
use first cell as counter
*
7 p s k 0 0 etc
L3: loop: at each iteration we have
*
n p s k' 0 0 etc
LL1: copy k' to t
*
n p s k' t 0 etc
LL2: set s=0 if t=0 to break outer loop (note that we do not break
this loop); cell to the right of t is used as temporary flag
*
n p s k' t 0 etc
LL3: decrement n and k'
*
n' p s k'' 0 0 etc
L4: add 7 back to k and return to s
*
0 p s k 0 0 etc
3: move to start of data
*
0 p 0 k 0 0 a1 etc
###################################
1: <+
2: [
L1: >,
>+++++++[-<------->]
,[-]<
L2: <<<+++++++
L3: [
LL1: >>>[->+>+<<]>>[-<<+>>]
LL2: +
<
[[-]>-<]
>[
-<<<->>>
]
LL3: <<-<<<-
]
L4: >>>+++++++<
]
3: >>>>
###################################
find the correct column in the dummy row by shifting along 2*k cells (x2 to
account for spaces S between the cells)
start with
*
0 p 0 k 0 0 a1 S a2 etc
1: update k = 2*k
*
0 p 0 2k 0 0 a1 S a2 etc
2: set tape to
*
0 p 0 a1 0 0 k S a2 etc
3: loop: at each iteration we have
*
0 p 0 x 0 A 0 k B
where k is number of shifts left; x is the value that would normally be
at k's position; and A and B represent blocks of multiple cells
assuming k != 0 the aim is now to keep this same pattern but with k
shifted rightwards (so A grows and B shrinks) and to decrement k
L1: move k down:
*
0 p 0 x k A 0 0 B
L2: append x to A
*
0 p 0 0 k A x 0 B
L3: remove first char in B (call it y)
*
0 p 0 y k A x 0 0 B'
L4: move k to where y was
*
0 p 0 y 0 A x 0 k B'
L5: decrement k
*
0 p 0 y 0 A x 0 k' B'
loop finishes as
*
0 p 0 z 0 A 0 0 B
where z is the column in the dummy row according to the user's input
4: move z back up
*
0 p 0 0 0 A 0 z B
###################################
1: <<<[-<+>>+<]
<[->+<]
>>[-<+>]
>>
2: [-<+>]
<<<[->>>+<<<]
>>[-<<+>>]
>
3: [
L1: <<[<]+[>]>
[ -<<[<]>>+[>]> ]
<<[<]>>-
L2: [>]+[<]>
[ [>]<+ [<]>- ]
>[>]<-
L3: [<]+ [>]>
[ -<<[<]>+[>]> ]
<<[<]>-
L4: >[ [>]>+<<[<]>>- ]
L5: >[>]>-
]
4: <<[<]<
[ >>[>]>+ <<[<]< - ]
>>[>]>
###################################
place the piece
1: go to same column in bottom row by shifting 15 * 6 rightwards
(width x2 to account for spaces for padding; then plus one to account for
newline; plus one to height to account for dummy row)
2: travel up rows (shift 15 left) until get empty cell (ascii 45)
set to zero cell so as to partition B into C and D
*
0 p 0 0 0 A 0 z C 0 D
3: set cell to piece value q
if p is 1 then q is 'O'
else q is 'X'
*
0 p 0 0 0 A 0 z C q D
4: move A up to join cells together again
*
0 p 0 0 0 0 A z C q D
5: reset dummy row and return to cell 4
use cell 3 as a status flag: s = 1 if dummy row empty and 0 otherwise
*
0 p s 0 0 0 A z C q D
###################################
1: >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>
2: ---------------------------------------------
[
+++++++++++++++++++++++++++++++++++++++++++++
<<<<<<<<<<<<<<<
---------------------------------------------
]
3: <[<]<[<]<<<
[-<+>>+<]>[-<+>] back up p in cell 1
+ use cell after p as status; 1 means set to 'X'
<[
>>>>[>]>[>]
set to 'O' = 79
++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++
[<]<[<]<<<
- reset p
set flag to 0
>-<
]
>[
-
>>>[>]>[>]
set to 'X' = 88
++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++
[<]<[<]<<
]<
<[->+<]> restore p
4: >>>>[>]<[ [->+<]< ]
5: <<+>> s = 1
>> >>>>>>>>>>>> go to end of dummy row
[
subtract 45 (ascii hyphen)
---------------------------------------------
[
[-]
<[<]<<<- set s = 0
>>>>[>]
]
+++++++++++++++++++++++++++++++++++++++++++++
<< skip padding cell
]
<
###################################
1: if s = 1 then move was valid; switch player and return to cell 4
also clear s to 0
*
0 p' 0 0 0 0 A z C q D
###################################
1: <
[
-<
<+> use cell 1 as temp cell; temp = 1
[-<->] if p != 0 then set p = 0 and temp = 0
<
[->+<] if temp != 0 then p must have been 0; set p = 1
>>
]
>
+
]