Skip to content

Instantly share code, notes, and snippets.

@andrewberls
Last active June 7, 2018 23:52
Show Gist options
  • Save andrewberls/5008788 to your computer and use it in GitHub Desktop.
Save andrewberls/5008788 to your computer and use it in GitHub Desktop.
Brainfuck Interpreter Challenge
Brainfuck (http://en.wikipedia.org/wiki/Brainfuck) is an strange language noted for its extreme simplicity - programs are written using 7 commands in total, and executed sequentially.
An 'instruction pointer' starts at the first command, executes it, and normally moves forward to the next command (with one exception).
The program terminates when the instruction pointer moves past the last command.
For those familiar with Turing machines, this is a very similar concept. We'll have a 'tape' of cells holding our values, a pointer to the current cell, and an instruction pointer looping through the program.
The commands we'll be working with are as follows (here, 'pointer' refers to the current cell pointer):
> Move the cell pointer to the cell on the right
< Move the cell pointer to the cell on the left
+ Increment the value at the cell pointer by one
- Decrement the value at the cell pointer by one
. Output the value of the cell at the pointer
[ If the value at the cell pointer is zero, then jump the instruction pointer forward to the command after the matching ']'
] If the value at the cell pointer is nonzero, jump the instruction pointer back to the command after the matching '['
This is technically a subset of the language: we are excluding the ',' command for reading input.
The problem is to write a simple interpreter for this language, that reads in programs and executes them.
Some hints/specs:
- Read the program from stdin
- Since whitespace is meaningless, write for the simple case of single-line programs that you can pipe in
- e.g., `java Interpreter < input.txt`, where input.txt contains a simple line such as +++>--+->+++.
- Ouput to stdout
- As mentioned before, you'll need a data structure to store a 'tape' of cells, which default to a value of 0.
-----------------------------
EXAMPLES/TEST CASES
-----------------------------
Simple example program:
++>++-.
Say the pointer starts at cells[0]
The cell at the pointer is incremented twice
The pointer is shifted right to cells[1]
The cell at the pointer is incremented twice and decremented once
The cell at the pointer is outputted
Output: 1
Cells: [2, 1]
Example with if-jumps:
+->+++<[++]>+-<++>+.
When we encounter the first '[', we jump to the '>' following the matching ']' since the value of
the current cell is 0 when it is encountered.
So everything in between the '[' and ']' gets skipped over!
Output: 4
Cells: [2,4]
@rpdelaney
Copy link

The examples don't do anything in any brainfuck interpreter I've tried.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment