Brainfuck
(Challenge added almost 7 years ago.)
And you thought Perl looks like line noise ...
The Problem
The brainfuck language is an esoteric programming language noted for its extreme minimalism. It was designed to challenge and amuse programmers, and is not suitable for practical use. The brainfuck language itself is Turing-complete and has only 8 commands.
The language was created in 1993 by Urban Müller with the intention of designing a language which could be implemented with the smallest possible compiler. Fitting it is then that we should pick it as a subject for Codegolf.
This challenge asks you to write code which takes a brainfuck program (and optional input) and executes it, producing the appropriate output.
The brainfuck language uses a simple model of a computer consisting of an array of memory cells, a movable pointer into the array, an output stream, an input stream and the program itself. The program is formed from a sequence of the below commands :
>- Increment the pointer to point to the next cell to the right.<- Decrement the pointer to point to the next cell to the left.+- Increment the byte pointed to by the pointer.-- Decrement the byte pointed to by the pointer.[- Jump forward to the command after the corresponding]if the byte at the pointer is zero.]- Jump back to the command after the corresponding[if the byte at the pointer is non-zero..- Output the value of the byte at the pointer.,- Accept one byte of input, storing its value in the byte at the pointer.
The brainfuck program will be passed to your code on stdin and may be split across multiple lines using newlines. You will be expected to display any output on stdout.
For three of the tests we run against your code, input to the brainfuck program is required. To specify the data to be passed to the brainfuck program, we append it to the brainfuck code and seperate it from the brainfuck with an exclamation mark. See Run 5 for an example of this. You should ignore any trailing whitespace on this input.
For more information and a more thorough description of each command, see Wikipedia's brainfuck page.
More Information
- The brainfuck language defines the size of the array of memory cells as 30,000. We don't explicitly test the size of the array in the tests, but we'll leave it to you to determine how small you can make it.
- The brainfuck language usually uses 8 bits as the size of a cell, and wraps when a cell overflows. That is, decrementing a cell which holds the value of 0 which result in 255 being stored, and incrementing a cell holding 255 will result in 0 being stored. Again, you may determine if this is necessary to pass the tests we run.
- Once the brainfuck program you're executing has consumed all its input, you can cease execution of your code.
- If execution reaches the end of the brainfuck program, you should cease execution.
- You should take into account that your code will be forcibly killed after 4 seconds of execution (Measured in wall time.) The sixth test in particular may exceed this time limit unless you optimise your code for speed as well as size.
Examples
Your code will be ran 6 times against various brainfuck programs :
- Run 1 - Hello World!
- Run 2 - JABH.
- Run 3 - Squares. Lists all square numbers upto 10,000.
- Run 4 - Text2BF. Outputs a brainfuck program which outputs the text given to the original brainfuck program if executed.
- Run 5 - Rot-13.
- Run 6 - Rot-13 (Performance Test). The same as test 5 but with a longer string of characters to rot-13.
The last three examples have text which is to be passed to the brainfuck program you execute. The text will be different on each run of your code. Reload the relevant page to see different input.