Last active
June 7, 2018 23:52
-
-
Save andrewberls/5008788 to your computer and use it in GitHub Desktop.
Brainfuck Interpreter Challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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] | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The examples don't do anything in any brainfuck interpreter I've tried.