Random Brainfuck

From Esolang
Jump to navigation Jump to search

Random Brainfuck is an extension to Brainfuck. It supports all the operations that Brainfuck supports, but has one extra operation i.e. the question mark (?) which overwrites the current cell with a random number. This adds a grain of unpredictability to Brainfuck, which makes it a better language for creating simple games.

Language overview

Command Description
> Move one cell to the right
< Move one cell to the left
+ Increment the current cell by one
- Decrement the current cell by one
[ If the current cell is zero, jump program execution to the corresponding ]
] If the current cell is non-zero, jump program execution to the corresponding [
. Output the character in the current cell
, Read a character and store it in the current cell
? Generate a random byte and store it in the current cell

As with Brainfuck, all other characters are completely ignored and can be used to comment the program.

Implementation

The random number generator should be able to generate the numbers 0 (inclusive) to 255 (inclusive) with uniform probability. The generated number should either be truly random or be generated using a pseudorandom generator. However if an implementation does the latter, it should at least be seeded.

Java equivalent

Initialisation of the random number generator before interpreting the RB Program:

randomGenerator = Random();

Invocation of ? during execution of the RB program.

cell[ptr] = randomGenerator.nextInt(256)

Examples

Die from 1 to 6

Usually a number is wanted in a domain different from 0-255. To get a number in a different domain, it's often useful to perform a modulo operation.

; n = random byte
?
; cell 0| n

; Use the divmod golf trick
; Now we have a number from 1 to 6 in cell 1
>++++++<[->-[>+>]>[+[-<+>]>>]<<<<]#
; cell 0| 0
; cell 1| n minus (n mod 6)
; cell 2| n mod 6

; Add 48 to cell 1 for converting it to a decimal
++++++[->++++++++<]>

; Print the result
.

Random Uppercase Letter

; n (cell 1) = random byte
>?
; d (cell 2) = 26 
>>+++++[<+++++>-]<+
; Go back to n
<
; Using the modulus algorithm in brainfuck algorithms we store n mod d in cell3
[>->+<[>]>[<+>-]<<[<]>-]
; Add cell 3 by 65 (the ASCII value of A)
>>>++++++++[<++++++++>-]<+
; Output
.

Minimized form:

>?>>+++++[<+++++>-]<+<[>->+<[>]>[<+>-]<<[<]>-]>>>++++++++[<++++++++>-]<+.

Infinite random binary data

Prints random binary data, never terminates.

+[>?.<]

Output a random decimal number from 0 to 255

?>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-
<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++
<]>.[-]]<<++++++[-<++++++++>]<.

See also Brainfuck algorithms#Print_value_of_cell_x_as_number_(8-bit).

Interpreters

The following constitutes a Common Lisp implementation of Random Brainfuck:

(deftype octet ()
  '(unsigned-byte 8))

(defun compute-jump-table (code)
  (declare (type string code))
  (let ((jump-table  (make-hash-table :test #'eql))
        (jump-starts NIL))
    (declare (type hash-table jump-table)
             (type list       jump-starts))
    (loop for position of-type fixnum from 0 below (length code) do
      (case (char code position)
        (#\[ (push position jump-starts))
        (#\] (unless jump-starts
               (error "Unmatched ']'."))
             (let ((start-position (pop jump-starts)))
               (declare (type fixnum start-position))
               (setf (gethash start-position jump-table) position)
               (setf (gethash position jump-table) start-position)))
        (otherwise NIL)))
    (the hash-table
      (if jump-starts
        (error "One or more unmatched '['.")
        jump-table))))

(defun cell-at (memory index)
  (declare (type hash-table memory)
           (type integer    index))
  (the octet (gethash index memory 0)))

(defun (setf cell-at) (new-value memory index)
  (declare (type integer    new-value)
           (type hash-table memory)
           (type integer    index))
  (the octet
    (setf (gethash index memory 0)
      (cond ((< new-value 0)   255)
            ((> new-value 255) 0)
            (T                 new-value)))))

(defun interpret-Random-Brainfuck (code &key (random-state (make-random-state T)))
  "Interprets the piece of Random Brainfuck CODE, utilizing the RANDOM-STATE as a random number generator, and returns NIL."
  (declare (type string       code)
           (type random-state random-state))
  (let ((position   0)
        (jump-table (compute-jump-table code))
        (memory     (make-hash-table :test #'eql))
        (pointer    0))
   (declare (type fixnum     position)
            (type hash-table jump-table)
            (type hash-table memory)
            (type integer   pointer))
   (symbol-macrolet ((character    (the character (char code position)))
                     (exhausted-p  (the boolean   (not (array-in-bounds-p code position))))
                     (current-cell (the octet     (cell-at memory pointer))))
     (setf *random-state* random-state)
     (loop until exhausted-p do
       (case character
         (#\+ (incf current-cell))
         (#\- (decf current-cell))
         (#\> (incf pointer))
         (#\< (decf pointer))
         (#\. (write-char (code-char current-cell)))
         (#\, (format T "~&>> ")
              (setf current-cell (char-code (read-char)))
              (clear-input))
         (#\[ (when (zerop current-cell)
                (setf position (gethash position jump-table))))
         (#\] (unless (zerop current-cell)
                (setf position (gethash position jump-table))))
         (#\? (setf current-cell (random 256)))
         (otherwise NIL))
       (incf position)))))

And a C++ implementation:

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <ctime>
unsigned char tape[1000000];
int p, tp, stack[1000000], matches[1000000];
struct node {
    char c;
    int num;
}opt[1000000];
inline void push(int x) {
    stack[tp++] = x;
}
inline int pop() {
    if (tp) return stack[--tp];
    else exit((puts("Unmatched ]"), 1));
}
int main(int argc, char* argv[])
{
    srand(time(0));
    FILE* f = fopen(argv[1], "r");
    int q = 0; // Length of optimized representation
    while (!feof(f)) {
        if (!feof(f)) {
            char c = fgetc(f);
            if (c != '+' && c != '-' && c != '>' && c != '<' && c != ',' && c != '.' && c != '[' && c != ']'&&c!='?') continue;
            if (q && (c == '+' || c == '-' || c == '>' || c == '<') && opt[q - 1].c == c) {
                opt[q - 1].num++;
            }
            else {
                opt[q++].c = c;
                opt[q - 1].num = 1;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (opt[i].c == '[') push(i);
        if (opt[i].c == ']') {
            int result = pop();
            matches[result] = i;
            matches[i] = result;
        }
    }
    if (tp) return puts("Unmatched ["), 1;
    int ip = 0;
    while (ip < q) {
        switch (opt[ip].c) {
        case '+': {
            tape[p] += opt[ip].num;
            break;
        }
        case '-': {
            tape[p] -= opt[ip].num;
            break;
        }
        case '>': {
            p += opt[ip].num;
            break;
        }
        case '<': {
            p -= opt[ip].num;
            break;
        }
        case ',': {
            tape[p] = getchar();
            break;
        }
        case '.': {
            putchar(tape[p]);
            break;
        }
        case '[': {
            if (!tape[p]) {
                ip = matches[ip];
            }
            break;
        }
        case ']': {
            if (tape[p]) {
                ip = matches[ip];
            }
            break;
        }
        case '?': {
            tape[p] = rand() & 255;
            break;
        }
        }
        ++ip;
    }
    return 0;
}

And a Python implementation:

import sys,random
def bf(code):
    s1=[]
    s2=[]
    matches={}
    tape=[0]*1000000
    for i,j in enumerate(code):
        if j=='[':
            s1.append(i)
        if j==']':
            m=s1.pop()
            matches[m]=i
            matches[i]=m
    cp=0
    p=0
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=(tape[p]+1)%256
        if code[cp]=='-':
            tape[p]=(tape[p]-1)%256
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=(ord(c) if c else 0)%256
        if code[cp]=='.':
            print(chr(tape[p]),end='')
        if code[cp]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='?':
            tape[p]=random.randint(0,255)
        cp+=1
bf(sys.stdin.read())

And a JavaScript implementation:

function rbf(program,input){
    var stack=[];
    var matches={};
    var ip=0;
    var tape=[];
    var p=0;
    var output='';
    for(let i=0;i<1000000;i++){
        tape.push(0);
    }
    for(var i=0;i<program.length;i++){
        if(program[i]=='['){
            stack.push(i);
        }
        if(program[i]==']'){
            if(stack.length==0){
                throw new Error('Right bracket does not match left bracket');
            }
            var mt=stack.pop();
            matches[mt]=i;
            matches[i]=mt;
        }
    }
    if(stack.length!=0){
        throw new Error('Left bracket does not match right bracket');
    }
    while(ip<program.length){
        if(program[ip]=='+'){
            tape[p]=tape[p]+1;
            if(tape[p]==256) tape[p]=0;
            ip=ip+1;
        }
        if(program[ip]=='-'){
            tape[p]=tape[p]-1;
            if(tape[p]==-1) tape[p]=255;
            ip=ip+1;
        }
        if(program[ip]=='>'){
            p=p+1;
            if(p>=1000000){
                throw new Error('Pointer overflow');
            }
            ip=ip+1;
        }
        if(program[ip]=='<'){
            p=p-1;
            if(p<0){
                throw new Error('Pointer underflow');
            }
            ip=ip+1;
        }
        if(program[ip]==','){
            if(input==''){
                tape[p]=0;
            }else{
                tape[p]=input.charCodeAt(0)%256;
                input=input.slice(1);
            }
            ip=ip+1;
        }
        if(program[ip]=='.'){
            output+=String.fromCharCode(tape[p]);
            ip=ip+1;
        }
        if(program[ip]=='['){
            if(tape[p]==0){
                ip=matches[ip];
            }else{
                ip=ip+1;
            }
        }
        if(program[ip]==']'){
            if(tape[p]!=0){
                ip=matches[ip];
            }else{
                ip=ip+1;
            }
        }
        if(program[ip]=='?'){
            tape[p]=Math.floor(Math.random()*256);
        }
        if(!('+-,.[]<>'.includes(program[ip]))){
            ip=ip+1;
        }
    }
    return output;
}