I stumbled over this funny site called CodeGolf.com and tried my luck on the first problem (actually it’s the sixth, but it was the last and therefore appeared first on their page – confused?) Writing a Brainfuck Interpreter:

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.

It didn't take me very long to write a running interpreter. My first version was more than a thousand characters. Even after renaming the variables and stripping all the whitespaces I still needed around 700 characters, which is huge compared to the best Ruby solution with only 142 characters.

Warning! Spoilers ahead - you might want to stop reading if you want to solve the problem, too

Brainfuck Interpreter Version 1 - a real interpreter

This was my very first idea. The algorithm is pretty obvious and nothing really fancy was done here. Two optimizations:

• aggregated the + and - operation and < and > into one when each to save space
• iterate over the input program to get the target addresses for the jump operations

But this code was still too slow. It passed the first 5 tests, but failed the rot13 performance test.

# Version 1 after a lot of rewrites

data = Array.new(30000,0)
datapointer = 0
codepointer = 0

(code,input) = STDIN.read.chomp.split '!'

# build a jump table to quickly access target address to jump to
stack = []
jmptbl = {}
(0..(code.size-1)).each {|i|
  case code[i]
    when 91: stack.push i
    when 93: m = stack.pop; jmptbl[i] = m; jmptbl[m] = i  
  end
}

while codepointer < code.size do
  x = code[codepointer]
  case x
# < >
    when 60, 62: datapointer = datapointer + x - 61 
# + - 
    when 43, 45: data[datapointer] = (data[datapointer] - x + 44) % 256
# [
    when 91: codepointer = (data[datapointer] == 0 ? jmptbl[codepointer] : codepointer)  
# ]             
    when 93: codepointer = (data[datapointer] != 0 ? jmptbl[codepointer] : codepointer)
# .
    when 46: print "#{data[datapointer].chr}" 
# ,    
    when 44: data[datapointer] = input.slice!(0)
             exit if data[datapointer].nil?   
  end
  codepointer = codepointer + 1  
end

# Version 1 obfuscated 
# 389 characters without this comment
d=Array.new(30000,0)
a=0
b=0
(c,k)=STDIN.read.chomp.split'!'
s=[]
j={}
(0..(c.size-1)).each{|i|
case c[i]
when 91:s.push i
when 93:m=s.pop;j[i]=m;j[m]=i  
end
}
while b<c.size do
x=c[b]
case x
when 60,62:a=a+x-61 
when 43,45:d[a]=(d[a]-x+44)%256  
when 91:b=(d[a]==0?j[b]:b) 
when 93:b=(d[a]!=0?j[b]:b)
when 46:print"#{d[a].chr}"
when 44:d[a]=k.slice!(0)
exit if d[a].nil?  
end
b=b+1  
end

Brainfuck Interpreter Version 2 - "optimize - don't do it"

This code contains many useless optimizations

• store the target address inside the program as the address for ] or address plus codesize for [
• store + and - as -255 and -257, so I can simply add the command to the data

But these optimizations didn't provide any significant speedup, the code was only about 10 percent faster on my machine which was still too slow to pass the performance test. And the program was even larger than my original version with 533 characters. I could perhaps squeeze out a few characters with a complicated formula for the first 6 lines of the case statement, but I didn't try this because this version was too slow anyway.

# version 2 - forget it, it sucks
data = Array.new(30000,0)
codepointer = 0
datapointer = 0

(code,input) = STDIN.read.chomp.split '!'

codesize = code.size
stack = []
opt = []
(0..(codesize-1)).each {|i|
  case code[i]
    when 60: opt << -3
    when 62: opt << -1
    when 43: opt << -255 
    when 45: opt << -257 
    when 44: opt << -5 
    when 46: opt << -6     
    when 91: stack.push opt.size; opt << 0 # just a placeholder
    when 93: m = stack.pop; opt[m] = opt.size + codesize; opt << m  
  end
}
while codepointer < opt.size do
  x = opt[codepointer]
  if x < -200
    data[datapointer] = (data[datapointer] + x) % 256
  elsif x < -3
    if x == -5
      data[datapointer] = input.slice!(0)
      exit if data[datapointer].nil?
    else
      print "#{data[datapointer].chr}"
    end   
  elsif x < 0
    datapointer = datapointer + x + 2  
  else 
    if x < codesize
      codepointer = (data[datapointer] != 0 ? x : codepointer)    
    else 
      codepointer = (data[datapointer] == 0 ? x % codesize : codepointer)
    end
  end
  codepointer = codepointer + 1  
end

Brainfuck Interpreter Version 3 - Brainfuck to Ruby

As I realized I wasn't going to pass the performance test with my other ideas I knew I had to generate Ruby code. The tricky part was how to simulate the commands "[" and "]". I started with the "Hello World!" Brainfuck program and rewrote it step by step in Ruby until I had an idea on how to replace every character of the input language with a chunk of Ruby code.

My translation table:
[	if currentCell != 0 begin
]	end while currentCell != 0 end
<	plus -1
>	plus 1
+	inc 1
-	inc -1
.	out
,	read

The definitions for the methods are shown below. The whole program was slightly larger than my version 1 but it is about 3 times faster, which was fast enough to pass the performance test.

# Version 3
def currentCell
  $data[$datapointer] || 0
end
def inc i
  $datapointer = $datapointer + i
end
def plus i 
  $data[$datapointer] = currentCell + i) % 256
end
def out
  print "#{currentCell.chr}"
end
def read
  $data[$datapointer] = $input.slice!(0)
  exit if !$data[$datapointer]
end
def append s
  $program << s << "
" 
end

$program = ''
$data = []
$datapointer = 0

($code,$input) = STDIN.read.chomp.split '!'

(0..($code.size-1)).each {|i|
  tmp = $code[i]
  case tmp
    when 60,62: append "inc #{tmp-61}"
    when 43,45: append "plus #{44-tmp}"
    when 91: append "if currentCell != 0
begin"
    when 93: append"end while currentCell != 0
end"
    when 46: append "out"
    when 44: append "read"
  end
}
eval $program 

# Version 3 obfuscated
# 401 characters without this comment
def x
$d[$a]||0
end
def y i
$a=$a+i
end
def v i 
$d[$a]=(x+i)%256
end
def t
print"#{x.chr}"
end
def u
$d[$a]=$k.slice!(0)
exit if !$d[$a]
end
def r s
$p<<s<<"
"
end
$p=''
$d=[]
$a=0
($c,$k)=STDIN.read.chomp.split'!'
(0..($c.size-1)).each{|i|
q=$c[i]
case q
when 60,62:r"y #{q-61}"
when 43,45:r"v #{44-q}"
when 91:r"if x!=0
begin"
when 93:r"end while x!=0
end"
when 46:r"t"
when 44:r"u"
end
}
eval $p

What's next?

I had a lot of fun writing these different versions. But now I'm stuck. I don't have the slightest clue on how to get to an even shorter piece of code. I already tried to add a method which generates the methods currentCell, inc, etc. but the overhead of one added method was more than what I gained by removing def and end.
I'm still thinking about other possible techniques to move towards the 142 byte by carldr. I believe there is a trick that uses special knowledge of the Brainfuck language I just don't have. If anybody has some generic hints on how to write shorter Ruby code, please leave a note