10
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Martin Ender Apr 27 '15 at 15:52
8
\$\begingroup\$

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 :)

\$\endgroup\$
  • 1
    \$\begingroup\$ 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" \$\endgroup\$ – Sparr Apr 24 '15 at 23:23
  • \$\begingroup\$ @Sparr All right, try with caret instead. \$\endgroup\$ – feersum Apr 24 '15 at 23:36
  • 3
    \$\begingroup\$ 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? \$\endgroup\$ – Sparr Apr 25 '15 at 0:03
  • 2
    \$\begingroup\$ You know, if you're going for a short compiler, this would be only 35 bytes in Retina. ;) \$\endgroup\$ – Martin Ender Apr 25 '15 at 1:47
  • 1
    \$\begingroup\$ @MartinBüttner shameless plug! :P \$\endgroup\$ – Optimizer Apr 25 '15 at 6:35
2
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Zacharý Nov 10 '17 at 15:59
  • 1
    \$\begingroup\$ Would changing R to m[p<0?p%S+S:p] work? \$\endgroup\$ – Zacharý Nov 13 '17 at 16:39
  • \$\begingroup\$ Removing the parentheses in the definition of R should save a few bytes. \$\endgroup\$ – Zacharý Nov 24 '17 at 17:46
1
\$\begingroup\$

rs, 33 bytes, Score: 2659

Mostly just a simple port of the sed answer.

</<<
>/>[->[-]>[-]+<<]>
[-]>[-]+<
\$\endgroup\$
  • 1
    \$\begingroup\$ Did you publish this language prior to yesterday? Languages that postdate the creation of a question aren't valid for submitting answers. \$\endgroup\$ – Sparr Apr 27 '15 at 0:49
  • \$\begingroup\$ @Sparr Well, I had, but then I wrecked my Git commit history and had to re-create the repo... \$\endgroup\$ – kirbyfan64sos Apr 27 '15 at 0:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.