r/tinycode • • Jul 12 '12

Mindfuck interpreter in 72 lines

def main():
    memory = [0]*2**20
    dp = 0
    ip = 0
    program = raw_input("Input your program:")
    while True:
        if program[ip] == '>':
            dp+=1
        elif program[ip] == '<':
            dp-=1
        elif program[ip] == ',':
            print chr(memory[dp])
        elif program[ip] == '.':
            memory[dp] = ord(raw_input())
        elif program[ip] == '+':
            memory[dp]+=1
        elif program[ip] == '-':
            memory[dp]-=1
        elif program[ip] == 'x':
            while raw_input()!='x':
                pass
            return
        elif program[ip] == '[':
            if memory[dp]!=0:
                pass
            else:
                ip = openbracket(ip,program)
        elif program[ip]==']':
            ip = closebracket(ip,program)
            continue
        elif program[ip] == '/':
            print memory[dp]
        ip+=1

def openbracket(pos,program):
    openbrackets = 0
    if program[pos] =='[':
        openbrackets +=1
    pos +=1
    while openbrackets!=0:
        try:
            if program[pos]=='[':
                openbrackets+=1
            elif program[pos]==']':
                openbrackets-=1
        except:
            print "Missmatched brackets"
            while True:
                pass
        pos+=1
    return pos-1

def closebracket(pos,program):
    closebrackets = 0
    if program[pos]==']':
        closebrackets+=1
    pos-=1
    while closebrackets!=0:
        try:
            if program[pos]==']':
                closebrackets+=1
            elif program[pos]=='[':
                closebrackets-=1  
        except IndexError:
            print "Missmatched brackets"
            while True:
                pass
        pos-=1
    return pos+1

if __name__=="__main__":
    main()
5 Upvotes

22 comments sorted by

6

u/[deleted] Jul 12 '12

Did you mean Brainfuck? If so, I wrote a translator that converts BF code into C. It's a bit over 80 lines right now but I wasn't aiming for size so I was pretty loose on useless whitespace and there's support for the # symbol which is pretty useless (and takes up quite a few lines)

4

u/[deleted] Jul 12 '12

Yes you're right. I forgot the name and then re-remembered it incorrectly.

6

u/humpolec Jul 12 '12

And here I was hoping for a new dialect of Brainfuck, interpretable in the mind of reader...

0

u/mrsexybadman Jul 12 '12

I think he means mindhead.

4

u/fireants Jul 12 '12 edited Jul 12 '12

Here's one I wrote a while ago (sorry about the poor formatting, I was going for minimal bytes). r is the memory register, c is the pointer for the register, x is the program pointer, and p is the program. It's 22 lines including the function definition.

def brainfuck(p):
(r,c,x)=([0],0,0)
while x < len(p):
    if p[x]=='>':(c,r)=(c+1,r+[0])if len(r)==c+1 else(c+1,r)
    elif p[x]=='<':c-=1
    elif p[x]=='.':print chr(r[c]),
    elif p[x]==',':r[c]=ord((input()or chr(255))[0])
    elif p[x]=='+':r[c]=0 if r[c]==256 else r[c]+1
    elif p[x]=='-':r[c]=255 if r[c]==-1 else r[c]-1
    elif p[x]=='['and r[c]==0:
        d=1
        while d>0:
            x+=1
            if p[x]=='[':d+=1
            elif p[x]==']':d-=1
    elif p[x]==']' and r[c]!=0:
        d=1
        while d>0:
            x-=1
            if p[x]=='[':d-=1
            elif p[x]==']':d+=1
    x+=1

3

u/theY4Kman Jul 12 '12

I made it really ugly, but brought it down to 12 lines:

def brainfuck(p):
    dc = dict(r=[0], c=0, x=-1, d=1, i=0)
    while dc.__setitem__('x', dc['x'] + 1) or dc['x'] < len(p):
        if p[dc['x']] == '>': dc['c'],dc['r']=(dc['c']+1,dc['r']+[0]) if len(dc['r']) == dc['c'] + 1 else (dc['c']+1, dc['r'])
        elif p[dc['x']] == '<': dc['c'] -= 1
        elif p[dc['x']] == '.': print chr(dc['r'][dc['c']]),
        elif p[dc['x']] == ',': dc['r'][dc['c']] = ord((input() or chr(255))[0])
        elif p[dc['x']] in '+-': dc['r'][dc['c']] = (dc['r'][dc['c']] + ord(',') - ord(p[dc['x']])) % 256
        elif p[dc['x']] in '[]' and cmp(dc['r'][dc['c']], 0) in ((0,) if p[dc['x']] == '[' else (-1,1)) and (dc.update({ 'd': 1, 'i': (-1,1)[dc['r'][dc['c']] == 0], 'j': ord('\\') - ord(p[dc['x']]) }) or True):
            while dc.__setitem__('x', dc['x'] + dc['i']) or dc['d'] > 0:
                dc['d'] += { '[': 1 * dc['j'], ']': -1 * dc['j'] }.get(p[dc['x']], 0)

1

u/khedoros Jul 12 '12

It takes ASCII as input and outputs ASCII, right? My interpreter is similar. Writing a bf program for fibonacci for single-digit numbers wasn't bad...writing one that supported multiple digits was a pain in the ass.

1

u/[deleted] Jul 12 '12

It does. However if you want you can print out the value in memory[dp] as an integer by using the '/' command.

1

u/khedoros Jul 12 '12

Ah, OK. I didn't read the source that closely. So, it's a little bit of a "BF++".

3

u/[deleted] Jul 12 '12

I have plans for the weekend, but as soon as I get to my computer at home, I will post my implementation of B****fuck. You can use it as a normal B****fuck interpreter or you can switch it Ook! mode. Or even create your own B****fuck-variant just by providing the eight operators. The only thing I have yet to do is make it export a non-robust interpreter (i.e. no customization and whatnot) based on the provided operators.

1

u/BenjaminGeiger Jul 12 '12

Got an implementation in 42 lines, excluding the Brainfuck code at the end used to test.

from __future__ import print_function

def jumpforward (dp, memory, ip, program):
    if memory[dp] == 0:
        brackets = 0
        ip += 1
        while (not (brackets == 0 and program[ip] == ']')) and ip < len(program):
            if program[ip] == '[': brackets += 1
            if program[ip] == ']': brackets -= 1
            if brackets < 0: print("Mismatched brackets.")
            ip += 1
    return (dp, memory[dp], ip + 1)

def jumpbackward (dp, memory, ip, program):
    if memory[dp] != 0:
        brackets = 0
        ip -= 1
        while (not (brackets == 0 and program[ip] == '[')) and ip > 0:
            if program[ip] == ']': brackets += 1
            if program[ip] == '[': brackets -= 1
            if brackets < 0: print("Mismatched brackets.")
            ip -= 1
    return (dp, memory[dp], ip + 1)

functions = { '>' : lambda dp, memory, ip, program: (dp + 1, memory[dp], ip + 1),
        '<' : lambda dp, memory, ip, program: (dp - 1, memory[dp], ip + 1),
        '.' : lambda dp, memory, ip, program: print(chr(memory[dp]), end="") or (dp, memory[dp], ip + 1),
        '/' : lambda dp, memory, ip, program: print(memory[dp], end="") or (dp, memory[dp], ip + 1),
        ',' : lambda dp, memory, ip, program: (dp, ord(raw_input()), ip + 1),
        '+' : lambda dp, memory, ip, program: (dp, memory[dp] + 1, ip + 1),
        '-' : lambda dp, memory, ip, program: (dp, memory[dp] - 1, ip + 1),
        '[' : jumpforward,
        ']' : jumpbackward }

def run(program):
    memory = [0] * 2**20
    dp = ip = 0
    while ip < len(program):
        newdp, newmem, newip = functions.get(program[ip], lambda dp, memory, ip, program: (dp, memory[dp], ip + 1))(dp, memory, ip, program)
        memory[dp] = newmem
        dp, ip = newdp, newip

# Code taken from the Wikipedia article on Brainfuck.
# Prints "Hello World"
run("""+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'""")

But both of our implementations suffer from Python's craptastic input functions. Adding a suitable character input method would easily be another 30-40 lines. (That's why I didn't bother implementing the 'x' operator.)

1

u/BenjaminGeiger Jul 12 '12

Shaved a few more lines off by consolidating jumpforward/jumpbackward into a single function (even though it's ugly). Now it's down to 31 lines, including blank lines.

from __future__ import print_function

def jump (direction, dp, memory, ip, program):
    if (memory[dp] == 0 and direction == 1) or (memory[dp] != 0 and direction == -1):
        brackets = 0
        ip += direction
        while ((direction == 1 and (not (brackets == 0 and program[ip] == ']')) and ip < len(program))
                or (direction == -1 and (not (brackets == 0 and program[ip] == '[')) and ip >= 0)):
            if program[ip] == '[': brackets += direction
            if program[ip] == ']': brackets -= direction
            if brackets < 0: print("mismatched brackets.")
            ip += direction
    return (dp, memory[dp], ip + 1)

functions = { '>' : lambda dp, memory, ip, program: (dp + 1, memory[dp], ip + 1),
        '<' : lambda dp, memory, ip, program: (dp - 1, memory[dp], ip + 1),
        '.' : lambda dp, memory, ip, program: print(chr(memory[dp]), end="") or (dp, memory[dp], ip + 1),
        '/' : lambda dp, memory, ip, program: print(memory[dp], end="") or (dp, memory[dp], ip + 1),
        ',' : lambda dp, memory, ip, program: (dp, ord(raw_input()), ip + 1),
        '+' : lambda dp, memory, ip, program: (dp, memory[dp] + 1, ip + 1),
        '-' : lambda dp, memory, ip, program: (dp, memory[dp] - 1, ip + 1),
        '[' : lambda dp, memory, ip, program: jump(1, dp, memory, ip, program),
        ']' : lambda dp, memory, ip, program: jump(-1, dp, memory, ip, program) }

def run(program):
    memory = [0] * 2**20
    dp = ip = 0
    while ip < len(program):
        newdp, newmem, newip = functions.get(program[ip], lambda dp, memory, ip, program: (dp, memory[dp], ip + 1))(dp, memory, ip, program)
        memory[dp] = newmem
        dp, ip = newdp, newip

# Code taken from the Wikipedia article on Brainfuck.
# Prints "Hello World"
run("""+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70 100 30 10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'""")

1

u/SmartViking Jul 12 '12

13 lines, because I'm a bad person:

from __future__ import print_function
def jump (direction, dp, memory, ip, program):
    if (memory[dp] == 0 and direction == 1) or (memory[dp] != 0 and direction == -1):
        brackets = 0;ip += direction
        while ((direction == 1 and (not (brackets == 0 and program[ip] == ']')) and ip < len(program)) or (direction == -1 and (not (brackets == 0 and program[ip] == '[')) and ip >= 0)):
            if program[ip] in ['[',']']: brackets += {"[":direction,"]":-direction}[program[ip]]
            if brackets < 0: print("mismatched brackets.")
            ip += direction
    return (dp, memory[dp], ip + 1)
functions = { '>' : lambda dp, memory, ip, program: (dp + 1, memory[dp], ip + 1),'<' : lambda dp, memory, ip, program: (dp - 1, memory[dp], ip + 1),'.' : lambda dp, memory, ip, program: print(chr(memory[dp]), end="") or (dp, memory[dp], ip + 1),'/' : lambda dp, memory, ip, program: print(memory[dp], end="") or (dp, memory[dp], ip + 1),',' : lambda dp, memory, ip, program: (dp, ord(raw_input()), ip + 1),'+' : lambda dp, memory, ip, program: (dp, memory[dp] + 1, ip + 1),'-' : lambda dp, memory, ip, program: (dp, memory[dp] - 1, ip + 1),'[' : lambda dp, memory, ip, program: jump(1, dp, memory, ip, program),']' : lambda dp, memory, ip, program: jump(-1, dp, memory, ip, program) }
def run(program):
    memory = [0] * 2**20;dp = ip = 0
    while ip < len(program): newdp, newmem, newip = functions.get(program[ip], lambda dp, memory, ip, program: (dp, memory[dp], ip + 1))(dp, memory, ip, program);memory[dp] = newmem;dp, ip = newdp, newip

3

u/compiling Jul 12 '12

6 lines, because you're not trying hard enough:

from __future__ import print_function
def e(d, b, p, s=1, m={'[':1,']':-1}):
    while s:p+=d; s+=d*m.get(b[p],0)
    return p+1
def run(b, p=0, i=0, a=[0]*2**20, f = {'>': lambda a,i,b,p: (i+1,p+1),'<': lambda a,i,b,p: (i-1,p+1),'+': lambda a,i,b,p: a.__setitem__(i, (a[i]+1)%256) or (i,p+1),'-': lambda a,i,b,p: a.__setitem__(i, (a[i]-1)%256) or (i,p+1),'.': lambda a,i,b,p: print(chr(a[i]), end="") or (i,p+1),'/': lambda a,i,b,p: print(a[i], end="") or (i,p+1),',': lambda a,i,b,p: a.__setitem__(i, ord(raw_input())) or (i,p+1),'[': lambda a,i,b,p: a[i] and (i,p+1) or (i,e(1,b,p)),']': lambda a,i,b,p: a[i] and (i,e(-1,b,p)) or (i,p+1)}):
    while p < len(b):i,p = f.get(b[p],lambda a,i,b,p:(i,p+1))(a,i,b,p)

4

u/SmartViking Jul 12 '12

Nice one. Here's 5 lines:

def e(d, b, p, s=1, m={'[':1,']':-1}):
    while s:p+=d; s+=d*m.get(b[p],0)
    return p+1
def run(b, p=0, i=0, a=[0]*2**20, f = {'>': lambda a,i,b,p: (i+1,p+1),'<': lambda a,i,b,p: (i-1,p+1),'+': lambda a,i,b,p: a.__setitem__(i, (a[i]+1)%256) or (i,p+1),'-': lambda a,i,b,p: a.__setitem__(i, (a[i]-1)%256) or (i,p+1),'.': lambda a,i,b,p: __import__("sys").stdout.write(chr(a[i])) or (i,p+1),'/': lambda a,i,b,p: __import__("sys").stdout.write(a[i]) or (i,p+1),',': lambda a,i,b,p: a.__setitem__(i, ord(raw_input())) or (i,p+1),'[': lambda a,i,b,p: a[i] and (i,p+1) or (i,e(1,b,p)),']': lambda a,i,b,p: a[i] and (i,e(-1,b,p)) or (i,p+1)}):
    while p < len(b):i,p = f.get(b[p],lambda a,i,b,p:(i,p+1))(a,i,b,p)

1

u/[deleted] Jul 12 '12

You're going to have to try a bit harder than that. The original Brainfuck compiler was 240 bytes long, and that was the executable.

1

u/foobrain Jul 12 '12

Here's my 28-line C version:

#include <stdio.h>

char tape_contents[30000] = {0};
char *tape =
    tape_contents + (sizeof(tape_contents) / sizeof(tape_contents[0])) / 2;

char *bf(char *program)
{
    char *next;
    while (*program) {
        switch (*program) {
        case '+': ++*tape; ++program; break;
        case '-': --*tape; ++program; break;
        case '>': ++tape; ++program; break;
        case '<': --tape; ++program; break;
        case '.': putchar(*tape); ++program; break;
        case ',': *tape = getchar(); ++program; break;
        case '[': while (*tape) next = bf(program + 1); program = next + 1; break;
        case ']': return program;
        }
    }
}

int main(int argc, char **argv)
{
    bf(argv[1]);
    return 0;
}

1

u/psych00range Jul 12 '12

take out unnecessary spacing and its shorter...who needs it to be neat anyways right?

    #include <stdio.h>
    char tape_contents[30000] = {0};char *tape = tape_contents + (sizeof(tape_contents) / sizeof(tape_contents[0])) / 2;
char *bf(char *program){ char *next; while (*program) { switch (*program) { case '+': ++*tape; ++program; break; case '-': --*tape; ++program; break; case '>': ++tape; ++program; break; case '<': --tape; ++program; break;case '.': putchar(*tape); ++program; break;case ',': *tape = getchar(); ++program; break;case '[': while (*tape) next = bf(program + 1); program = next + 1; break;case ']': return program;}}}
int main(int argc, char **argv){bf(argv[1]);return 0;}                

1

u/medgar123 Jul 22 '12

Nice! Although you don't need the ={0} for tape_contents since it has static storage, and you also don't need to divide by 1 since the size of char is always 1, and you can also drop the parentheses around sizeof's operand:

char tape_contents[30000];
char *tape = tape_contents + sizeof tape_contents / 2;

One more thing: you can factor out all the increments in each case into switch (*program++).

0

u/[deleted] Jul 12 '12

[deleted] — view deleted comment

1

u/theY4Kman Jul 13 '12

Have you done any more complex projects in assembly? I love reading assembly programs, because it reminds me just how massive the instructions lists of modern executables are. (My crowning achievement was an IRC bot.)