# Randomized Brainfuck Compiler

Joe is your average BF developer. He is about to check in his code changes to their repository when he gets a call from his boss. "Joe! The new client's machine is broken! The brainfuck interpreter sets all the cells to random values before program execution. No time to fix it, your code will have to deal with it." Joe doesn't think much of it, and is about to write a program to set the first million cells to zero, when his boss interrupts him again - "... and don't think about using brute force, the code has to be as small as possible." Now you have to help poor Joe!

## Specifications

• You will get some valid brainfuck code as input
• Your program will then modify the code so that it should work on a randomized brainfuck interpreter
• This means that before program execution, the cells can be set to any value.
• The new program should have the exact same behavior no matter the initial conditions.
• The interpreter will have max-cell value of 255 with wrapping, and an infinite length tape.

## Scoring

Your score is 10 times the compiler size in bytes plus the sum of the test case sizes. Lowest score obviously wins.To mitigate against test-case optimization, I reserve the right to change the test-cases around if I suspect anything, and probably will do so before picking a winner.

## Test Cases

(I got these from the esolangs page and this webpage: http://www.hevanet.com/cristofd/brainfuck/). Also thanks to @Sparr for the last test case.

• Hello World: ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
• Reverse Input: >,[>,]<[.<]
• Powers of Two (Infinite Stream): >++++++++++>>+<+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<]>.>[->[ <++>-[<++>-[<++>-[<++>-[<-------->>[-]++<-[<++>-]]]]]]<[>+<-]+>>]<<]
• Squares Under 10000: ++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+>>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]<<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]
• Fibonacci Stream: >++++++++++>+>+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>]<<<]
• ASCII Sequence till input: ,[.[>+<-]>-] (This one requires varying cell numbers based on the input)
• Comments are not for extended discussion; this conversation has been moved to chat. Apr 27, 2015 at 15:52

# sed, 46 byte compiler

s/</<</g
s/>/>[->[-]>[-]+<<]>/g
s/^/[-]>[-]+</


I didn't notice that the output was also supposed to be golf until after writing the program, so I will go for the short compiler. Also it was far too much work to test, so please notify if it does not function correctly :)

• I'm confused. Your third line replaces the empty string? What does the empty string match in sed? "sed: first RE may not be empty" Apr 24, 2015 at 23:23
• @Sparr All right, try with caret instead. Apr 24, 2015 at 23:36
• ok, let's see if I follow... zero the cell 0, set the cell 1 to one. replace all < with << and > with >X>. now any time the original program accessed cell n the new program accesses cell 2n, the even numbered cells. X zeros the odd cell being passed over, and if it's not zero then it zeros the next cell (an even cell) and sets the next odd cell to 1. do I have that right? Apr 25, 2015 at 0:03
• You know, if you're going for a short compiler, this would be only 35 bytes in Retina. ;) Apr 25, 2015 at 1:47
• @MartinBüttner shameless plug! :P Apr 25, 2015 at 6:35

## C++

Compiler size : 630 bytes ( -10 bytes thanks to Zacharý )
Hello World compile result size : 139
Square under 10000 : 319

Compiler :

#include<string>
#include<map>
#include<stack>
#define B break
#define C case
#define S 30000
#define R m[(p<0)?(p%S)+S:p]
using s=std::string;using P=std::pair<int,int>;s a(s c){char m[S];memset(m,0,S);int p=0,i=0;P r{0,0};std::map<int,int>j;std::stack<int>t;for(int d=0;d<c.size();++d){if(c[d]==91)t.push(d);if(c[d]==93){j[d]=t.top();j[t.top()]=d;t.pop();}}while(i<c.size()){switch(c[i]){C'>':++p;B;C'<':--p;B;C'+':++R;B;C'-':--R;B;C'[':if(!R)i=j[i];B;C']':i=j[i]-1;B;default:B;}++i;r.first=p<r.first?p:r.first;r.second=p>r.second?p:r.second;}s n;for(int i=r.first;i<r.second;++i){n+="[-]>";}n+="[-]"+s(r.second,60)+c;return n;}


The randomized brainfuck interpreter :

void interpret(const std::string& code) {
char memory[30000];
for (int i = 0; i < 30000; ++i)
memory[i] = std::rand()%256;
int memPtr = 0, insPtr = 0;
std::map<int, int> jump_map;

{
std::stack<int> jstack;
for (int i = 0; i < code.size(); ++i) {
if (code[i] == '[')
jstack.push(i);
if (code[i] == ']') {
jump_map[i] = jstack.top();
jump_map[jstack.top()] = i;
jstack.pop();
}
}
}
while (insPtr < code.size()) {
switch (code[insPtr]) {
case '>': ++memPtr; break;
case '<': --memPtr; break;
case '+': ++memory[memPtr]; break;
case '-': --memory[memPtr]; break;
case '.': std::cout << memory[memPtr]; break;
case ',': std::cin >> memory[memPtr]; break;
case ']': if (memory[memPtr] != 0) insPtr = jump_map[insPtr]; break;
case '[': if (memory[memPtr] == 0) insPtr = jump_map[insPtr]; break;
default:break;
}
++insPtr;
}
}


Some notes :

• The compiler will execute the program to determine the memory cells that are used. If your program is an infinite loop, the compiler will loop infinitely.
• You can reduce your score by changing the name of pii to P, and changing the definition of R to m[p<0?p%30000+30000:p], and modifying all the calls/references to them accordingly. Also, he modified the test cases. I haven't checked this, but it might save some bytes to define something to be 30000, since you use it so often. Nov 10, 2017 at 15:59
• Would changing R to m[p<0?p%S+S:p] work? Nov 13, 2017 at 16:39
• Removing the parentheses in the definition of R should save a few bytes. Nov 24, 2017 at 17:46
• 398 bytes Jan 9, 2021 at 8:07
• Fail on ,[[>++<-]>.](take an input, double and output till zero), get [-],[[>++<-]>.]
– l4m2
Mar 19, 2021 at 18:06

# rs, 33 bytes, Score: 2659

Mostly just a simple port of the sed answer.

</<<
>/>[->[-]>[-]+<<]>
[-]>[-]+<

• Did you publish this language prior to yesterday? Languages that postdate the creation of a question aren't valid for submitting answers. Apr 27, 2015 at 0:49
• @Sparr Well, I had, but then I wrecked my Git commit history and had to re-create the repo... Apr 27, 2015 at 0:49